7.3 平衡二叉树
平衡因子与 AVL 树的定义，插入后的 LL、RR、LR、RL 四种旋转调整，删除操作，以及高度与结点数的关系。
定义
为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），也称 AVL 树。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 −1、0 或 1。
插入
二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
四种调整方式
| 类型 | 插入位置 | 调整方式 |
|---|---|---|
| LL | 在 A 的左孩子 B 的左子树上插入 | 右单旋转：B 向右上旋转代替 A 成为根结点，A 成为 B 的右子树的根，B 原右子树作为 A 的左子树 |
| RR | 在 A 的右孩子 B 的右子树上插入 | 左单旋转：B 向左上旋转代替 A 成为根结点，A 成为 B 的左子树的根，B 原左子树作为 A 的右子树 |
| LR | 在 A 的左孩子 B 的右子树上插入 | 先左后右双旋转：先将 B 的右孩子 C 向左上旋转提升到 B 的位置，再把 C 向右上旋转提升到 A 的位置 |
| RL | 在 A 的右孩子 B 的左子树上插入 | 先右后左双旋转：先将 B 的左孩子 C 向右上旋转提升到 B 的位置，再把 C 向左上旋转提升到 A 的位置 |
下面的动画中，依次插入 15, 3, 7, 10, 9, 8，会先后遇到 LR、LL 和 RL 三种情况（徽标上的数字是平衡因子）。你也可以输入自己的序列：
动画演示平衡二叉树（AVL）的插入与旋转
失衡结点（徽标为平衡因子）旋转后上升的结点新插入
1/30依次插入序列：15, 3, 7, 10, 9, 8
删除
与平衡二叉树的插入操作类似，以删除结点 w 为例来说明平衡二叉树删除操作的步骤：
- 用二叉排序树的方法对结点 w 执行删除操作；
- 若导致了不平衡，则从结点 w 开始向上回溯，找到第一个不平衡的结点 z（即最小不平衡子树）；y 为结点 z 的高度最高的孩子结点；x 是结点 y 的高度最高的孩子结点；
- 然后对以 z 为根的子树进行平衡调整，其中 x、y 和 z 可能的位置有 4 种情况（LL、LR、RR、RL），与插入时的调整类似。
查找效率
在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，进行关键字的比较次数不超过树的深度。
即时练习
即时练习4 题
点击选项即可作答
- 1在任意一棵非空平衡二叉树（AVL 树）T₁ 中，删除某结点 v 之后形成平衡二叉树 T₂，再将 v 插入 T₂ 形成平衡二叉树 T₃。下列关于 T₁ 与 T₃ 的叙述中，正确的是（ ）。
Ⅰ. 若 v 是 T₁ 的叶结点，则 T₁ 与 T₃ 可能不相同
Ⅱ. 若 v 不是 T₁ 的叶结点，则 T₁ 与 T₃ 一定不相同
Ⅲ. 若 v 不是 T₁ 的叶结点，则 T₁ 与 T₃ 一定相同 - 2含有 20 个结点的平衡二叉树的最大深度为（ ）。
- 3现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
- 4在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作（ ）型调整以使其平衡。
学完了吗？
标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。