数据结构，建立平衡二叉排序树

1. 数据结构，建立平衡二叉排序树

首先插入503、087、512、061、908、124如下图，树平衡
         503
        /       \
   087     512
   /      \         \
061  124      908
插入897之后，512节点不平衡，做RL型调整，先围着908右旋，然后围着897右旋
         503                              503                             503
        /       \                          /        \                      /             \
   087     512             ->     087    512        ->    087          897
   /      \         \                    /     \        \               /     \          /    \
061  124      908             061  124    897       061  124  512  908  
                    /                                       \
                897                                      908
指针变化就是897右子树变为908这个节点，左子树变为512这个节点，503右子树为897,908,左子树为NULL，512右子树为NULL
然后插入275,653,依旧平衡
           503
      /             \
   087          897
   /     \          /    \
 061  124  512  908  
            \        \
           275    653
然后插入426,087、124节点不平衡，做RR型调整
           503                                         503
      /             \                                /             \
   087          897                         124          897
   /     \          /    \                       /     \          /    \
 061  124  512  908   ->        087  275  512  908
            \        \                       /           \        \
           275    653              061        426    653 
                \   
               426  
指针变化是087右子树为NULL，503左子树为124,124左子树为087。

2. 二叉排序树的建立的过程中是如何实现平衡

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
　　常用算法有：红黑树、AVL树、Treap等。
　　平衡二叉树的调整方法
　　平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
　　⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
　　⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
　　⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
　　⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

3. 二叉排序树的建立的过程中是如何实现平衡

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
　　常用算法有：红黑树、AVL树、Treap等。
　　平衡二叉树的调整方法
　　平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
　　⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
　　⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
　　⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
　　⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

4. 二叉排序树的建立的过程中是如何实现平衡

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
　　常用算法有：红黑树、AVL树、Treap等。
　　平衡二叉树的调整方法
　　平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
　　⑴
每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
　　⑵
若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
　　⑶
判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
　　⑷
如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

5. 平衡二叉树是不是二叉排序树？

平衡树：平衡二叉树

6. 构造一个二叉排序树

二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

7. 平衡二叉树是二叉排序树吗？

平衡二叉树不一定是二叉排序树，平衡二叉树是为了避免二叉排序树高度增长过快，降低二叉排序树性能而设的树，二叉排序树当然不可能都是平衡二叉树。
首先平衡二叉树是特殊的二叉排序树，他的结点元素间存在着偏序关系；其次相对于一般的二叉排序树，平衡二叉树的左右子树的深度差也有不超过1层的约束，这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树，这可以减少二叉树元素查找的深度，从而提升平均查找效率。
应用
平衡树可以完成集合的一系列操作， 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。
二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值。
（2）若右子树不空，则右子树所有结点的值均大于或等于它的根结点的值。
（3）左、右子树也分别为二叉排序树。

8. 平衡二叉树是二叉排序树吗?

是的。
衡二叉树（balanced binary tree）是一种特殊的二叉排序树，它或者为空树，或者每个结点的左右子树都是平衡二叉树，也就是每个结点的左右子树的高度之差只能是－1,0,1三种情况。
平衡二叉树又称AVL树，是由苏联的Georgy Adelson-Velsky和E.M.Landis发明的，并以他们的名字命名。
平衡二叉树的平衡状况由平衡因子（Balance Factor,BF)来衡量。平衡因子定义为当前结点的左子树高度减去右子树的高度之差，其可能取值只有－1,0,1。叶结点的BF都是0。

平衡二叉树的应用价值：
如果能维持平衡二叉树的结构，检索操作就能在O(log n)时间内完成，实现高效检索。

最小不平衡子树：
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树。（指BF超出合法值）。

最小非平衡子树：
包含插入结点位置，其根结点的BF是1或－1的最小子树。（指BF非0，但BF在合法值范围内）。
以上内容参考：百度百科-平衡二叉查找树