1、平衡二叉树的定义
为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称平衡树(AVL树)。定义结点左子树和右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1、0或1。
因此平衡二叉树可定义为它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度差的绝对值不超过1.
2、平衡二叉树的插入
二叉排序树保证平衡的基本思想:每当在二叉树中插入(或删除)一个结点时,首先要检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡,则先找到插入路径上离结点最近的平衡因子绝对值大于1的结点A,再对以A为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。
注意:每次调整的对象都是最小不平衡子树,即在插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。
平衡二叉树的插入过程前半部分与二叉排序树相同,但是在新结点插入后,如果造成了查找路径上不再平衡,需要做出相应的调整。一般可将失去平衡后进行调整的规律归纳为以下4种情况: 1)LL平衡旋转(右单旋转)
由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A称为根结点,将A结点向右下旋转称为B的右子树的根结点,则B的原右子树则作为A结点的左子树。
2)RR平衡旋转(左单旋转)
由于在结点A的右孩子(R)的右孩子(R)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则称为A结点的右子树。
3)LR平衡旋转(先左后右双旋转)
由于在A的左孩子(L)的右子树(R)上插入新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。现将A结点的左孩子B的右子树的根结点C向上旋转提升到B结点的位置,然后再把该C结点向右上旋转提升到A结点的位置。
4)RL平衡旋转(先右后左双旋转)
由于在A的右孩子(R)的左子树(L)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。现将A结点的右孩子B的左子树的C向右上旋转提升到B的位置,然后再把该C结点向左上旋转提升到A结点的位置。
3、平衡二叉树的查找
在平衡二叉树上进行查找的过程和二叉排序树相同,因此,在查找的过程中和给定值进行比较的关键字的个数不超过树的深度。
假设以Nh表示深度为h的平衡树中含有最少的结点树。显然N0=0,N1=1,N2=2,并且有Nh=N(h-1)+N(h-2)+1.
可以证明,含有n个结点的平衡二叉树的最大深度为O(log2 n).因此平衡二叉树的平均查找长度为O(log2 n)。