6.6 平衡二叉树（AVL树）★3◎4

6.6 平衡二叉树（AVL树）★3◎4

　　平衡二叉树、一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差（平衡因子）的绝对值不超过1。在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下4种情况：
　　（1）左单旋转（LL）型调整（在a的右孩子的右子树上插入结点，使得a结点的平衡因子从﹣1变成﹣2）
　　如图6-5（a）为插入前的子树。其中，B为结点a的左子树，D、E分别为结点c的左右子树，B、D、E三棵子树的高均为h。图6-5（a）所示的子树是平衡二叉树。
　　在图6-5（a）所示的树上插入结点x，如图6-5（b）所示。结点x插入在结点c的右子树E上，导致结点a的平衡因子绝对值大于1，以结点a为根的子树失去平衡。

　　【调整策略】
　　调整后的子树除了各结点的平衡因子绝对值不超过1外，还必须是二叉排序树。由于结点c的左子树D可作为结点a的右子树，将结点a为根的子树调整为左子树是B，右子树是D，再将结点a为根的子树调整为结点c的左子树，结点c为新的根结点，如图6-5(c)所示。
　　【平衡化调整操作判定】
　　沿插入路径检查三个点a、c、E，若它们处于与“\”直线同一个方向，则要作左单旋转，即以结点c为轴逆时针旋转。
　　（2）右单旋转（RR）型调整（在a的左孩子的左子树上插入结点，使得a结点的平衡因子从1变成2）
　　RR型调整与LL型调整类似，沿插入路径检查三个点a、c、E，若它们处于与“/”直线同一个方向，则要做右单旋转，即以结点c为轴顺时针旋转，如图6-6所示。

　　（3）先左后右双向旋转（LR）型调整（在a的左孩子的右子树上插入结点，使得a结点的平衡因子从1变成2）
　　如图6-7（a）为插入前的子树，根结点a的左子树比右子树高度高1，待插入结点x将插入到结点b的右子树上，并使结点b的右子树高度增加1，从而使结点a的平衡因子的绝对值大于1，导致结点a为根的子树平衡被破坏，如图6-7（b）、图6-7（c）所示。

　　沿插入路径检查三个点a、b、c，若它们呈“<”字形，需要进行先左后右双向旋转：
　　① 首先，对结点b为根的子树，以结点c为轴，向左逆时针旋转，结点c成为该子树的新根，如图6-7（c）所示。
　　② 由于旋转后，待插入结点x相当于插入到结点b为根的子树上，这样a、c、b三点处于与“/”直线同一个方向，则要做右单旋转，即以结点c为轴顺时针旋转，如图6-7（d）所示。
　　（4）先右后左双向旋转（RL）型调整（在a的右孩子的左子树上插入结点，使得a结点的平衡因子从-1变成-2），RL型调整和LR型调整对称。
　　【平衡树的查找分析】
　　在平衡树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较的关键码个数不超过树的深度。那么，含有n个关键码的平衡树的最大深度是多少呢？为解答这个问题，我们先分析深度为h的平衡树所具有的最少结点数。

　　假设以表示深度为h的平衡树中含有的最少结点数。显然，，并且这个关系和斐波那契序列极为相似。利用归纳法容易证明：

　　反之，含有n个结点的平衡树的最大深度为，因此，在平衡树上进行查找的时间复杂度为