7.5 二叉平衡树
7.5 二叉平衡树
虽然在二叉排序树上实现的插入、删除和查找等基本操作的平均时间均为O(log2n)，但最坏情况下，这些基本运算的时间均会增至O(n)。为了避免这种情况发生，人们研究了许多种动态平衡的方法，使得往树中插入或删除记录时，通过调整树的形态来保持树的“平衡”，使之既保持BST性质不变，又保证树的高度在任何情况下均为O(log2n)，从而确保树上的基本运算在最坏情况下的时间均为O(log2n)。平衡的二叉排序树有很多种，较为著名的有AVL树，它是由两位前苏联数学家Adel'son-Vel'sii和Landis于1962年给出的，故用他们的名字命名。
若一棵二叉树中每个节点左、右子树的高度至多相差1，则称此二叉树为平衡二叉树。在算法中，通过平衡因子（Balancd Factor，BF）来具体实现上述平衡二叉树的定义。平衡因子的定义是：平衡二叉树中每个节点有一个平衡因子域，每个节点的平衡因子是该节点左子树的高度减去右子树的高度。从平衡因子的角度可以说，若一棵二叉树中所有节点平衡因子的绝对值小于或等于1，即平衡因子取值为1、0或-1，则该二叉树称为平衡二叉树。
图7-8是平衡二叉树和不平衡二叉树的例子，图中节点旁标注的数字为该节点的平衡因子。其中，图7-8（a）是一棵平衡二叉树，图中所有节点平衡因子的绝对值都小于1；图7-8（b）是一棵不平衡二叉树，图中节点3、4、5的平衡因子值分别为-2、-3和-2。
（a）平衡二叉树 （b）不平衡二叉树
图7-8 平衡二叉树和不平衡二叉树
如何将二叉树构造成一棵平衡二叉树，而不是一棵二叉排序树，关键是每次向二叉树中插入新节点时要保持所有节点的平衡因子满足平衡二叉树的要求。这就要求一旦有些节点的平衡因子在插入新节点后不满足要求就要进行调整。下面分析向一棵平衡二叉树中插入新节点后的几种情况。为方便讨论，定义HL为某节点左子树的高度，HR为某节点右子树的高度。
当向一棵平衡二叉树中插入一个新节点时，若插入后某些节点左、右子树的高度不变，则不会影响这些节点的平衡因子，也不会因为这些节点造成其他节点的不平衡；若插入后某些节点的左子树高度增加1，则可能影响这些节点的平衡因子，也可能会因为这些节点造成其他节点的不平衡。具体又分为3种情况：
（1）若插入前部分节点的左子树高度HL与右子树高度HR相等，即平衡因子为0，则插入新节点后将使平衡因子变为1，但仍满足平衡二叉树的要求，不需要对其进行调整。
（2）若插入前部分节点的HL小于HR，即平衡因子为-1，则插入新节点后将使平衡因子变为0，平衡情况更加改善，也不需要对其进行调整。
（3）若插入前部分节点的HL大于HR，即平衡因子为1，则插入新节点后将使平衡因子变为2，破坏了平衡二叉树的限制条件，需要对这些节点进行调整，使二叉树中的所有节点都重新满足平衡二叉树的要求。
若插入新节点后，某些节点的右子树高度增加1，同样也分为类似的3种情况：对于第（1）种情况，平衡因子将由0变为-1，不需要进行调整；对于第（2）种情况，平衡因子由-l变为-2，需要进行调整；对于第（3）种情况，平衡因子由1变为0，平衡情况更加改善，也不需要进行调整。
下面讨论如何进行调整。调整的原则有两点：一要满足平衡二叉树的要求；二要保持二叉排序树的性质。
假定向平衡二叉树中插入一个新节点后破坏了平衡二叉树的平衡性，那么首先要找出插入新节点后失去平衡的最小子树根节点的指针，然后再调整这个子树中有关节点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。
失去平衡的最小子树是指以离插入节点最近，且平衡因子绝对值大于1的节点作为根的子树。假设用A表示失去平衡的最小子树的根节点，则调整该子树的操作可归纳为下列4种情况。
1．LL型调整
这是由于在A节点的左孩子（设为B节点）的左子树上插入节点，使得A节点的平衡因子由1变为2而引起的不平衡问题。LL型调整的一般情况如图7-9所示。在图中，用长方框表示子树，用长方框的高度（并在长方框旁标有高度值h或h+1）表示子树的高度，用带阴影的小方框表示被插入的节点。调整的方法是：单向右旋平衡，即将A的左孩子节点B向右上旋转代替A成为根节点，将A节点向右下旋转成为B的右子树的根节点，而B的原右子树则作为A节点的左子树。因为调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。
图7-9 LL型调整过程
2．RR型调整
这是由于在A节点的右孩子（设为B节点）的右子树上插入节点，使得A节点的平衡因子由-1变为-2而引起的不平衡问题。RR型调整的一般情况如图7-10所示。调整的方法是：单向左旋平衡，即将A的右孩子节点B向左上旋转代替A成为根节点，将A节点向左下旋转为B的左子树的根节点，而B的原左子树则作为A节点的右子树。因为调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。
图7-10 RR型调整过程
3．LR型调整
这是由于在A节点的左孩子（设为B节点）的右子树上插入节点，使得A节点的平衡因子由1变为2而引起的不平衡问题。LR型调整的一般情况如图7-11所示。调整的方法是：先左旋转后右旋转平衡，即先将A节点的左孩子（即B节点）的右子树的根节点（设为C节点）向左上旋转提升到B节点的位置，然后再把该C节点向右上旋转提升到A节点的位置。因为调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。
图7-11 LR型调整过程
4．RL型调整
这是由于在A节点的右孩子（设为B节点）的左子树上插入节点，使得A节点的平衡因子由-1变为-2而引起的不平衡问题。RL型调整的一般情况如图7-12所示。调整的方法是：先右旋转后左旋转平衡，即先将A节点的右孩子（即B节点）的左子树的根节点（设为C节点）向右上旋转提升到B节点的位置，然后再把该C节点向左上旋转提升到A节点的位置。因调整前后对应的中序序列相同，所以调整后仍保持了二叉排序树的性质不变。
在平衡二叉树上进行查找的过程和在二叉排序树上进行查找的过程完全相同，因此，在平衡二叉树上进行查找关键字的比较次数不会超过平衡二叉树的深度。可以证明，含有n个节点的平衡二叉树的最大深度为O(log2n)，因此，平衡二叉树的平均查找长度也为O(log2n)。
图7-12 RL型调整过程
【例7-4】如图7-13所示为一棵二叉排序树。
图7-13 二叉排序树
（1）给出平衡因子值绝对值为2的节点。
（2）此树为何种类型的不平衡树？给出调整好的平衡二叉树。
解：
（1）如图7-14（a）所示是标有平衡因子的二叉排序树，其中bf绝对值为2的节点有e、l和j。
（2）不平衡的3个节点构成RL型，所以应进行RL型调整。调整好的平衡二叉树如 图7-14（b）所示。
哈希法（Hashing）的查找与一般的查找法（Searching）是不一样的。在哈希法中，键值（Key Value）或标识符（Identifier）在内存的地址是经由函数（Function）转换而来的，此种函数，一般称为哈希函数（Hashing Funciton）或键值对应地址转换（Key to Address Transfomation）。对于有限的存储空间，能够有效使用且在插入或删除时也能快速地完成，利用哈希法最为恰当，因为哈希表在查找没有冲突（Collision）及溢出（Overflow）的条件下，只要一次查找就可完成。
图7-14 平衡二叉树的调整过程