BBtree Search（平衡二叉树）

1 平衡二叉树

为了防止二叉排序树高度的过度增长，我们规定在插入和删除结点时，保证任意结点的左，右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树。

定义结点左右，子树的高度差为该结点的平衡因子。

如下图：

平衡

不平衡

2 平衡二叉树的插入

每当插入一个结点时，检查插入路径上的结点是否因为这次插入操作导致不平衡，如果导致了，则找到插入路径上离插入结点最近的平衡因子大于1的结点，在对该结点进行调整，调整后应该保证二叉排序树的特性，最后二叉树达到平衡。

首先约定：

每次调整的都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子大于1的结点作为根的子树（下图虚线框中的子树）。⤵️

我们将插入结点后形成的最小不平衡子树的根结点记为A，调整不平衡子树有四种情况：

1. LL平衡旋转

   有如下一棵二叉排序树，

   

   在BL上插入了一个结点，使得A的平衡因子变为2:

   

   将这个最小不平衡子树分成三部分如下图：

   

   由于$A>BR>B$，所以BR结点可以连接在A的左边而不会影响排序树的性质：

   

   两个紫色的框内的子树，高度一样，将右边框内的子树作为B的右孩子，使得B的平衡因子变为0，最后树变为平衡状态：

   

   总结方法：

   情况：在结点A的左孩子的左子树上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡。

   做法：将A的左孩子B向右上旋转代替A结点，将A结点右下旋转成为B的右子树的根结点，B的原右子树变成A的左子树。

   

2. RR平衡旋转

   与LL平衡旋转正好镜像。

   总结方法：

   情况：在结点A的右孩子的右子树上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失 去 平衡。

   方法：将A的右孩子B向左上旋转代替A结点，将A结点左下旋转成为B的左子树的根结点，B的原左子树变成A的右子树。

   

3. LR平衡旋转

   假设有如下的一棵排序树：

   

   在B结点的右子树上插入一个结点：

   

   我们注意到方形框的四个子树$BL、CL、CR、AR$之间的高度差$h\leqslant 1$，所以它们一定要在 同 一层，我们将$A、B、C$三个结点之间的连接断掉，将这颗树进行划分：

   

   由于$B<CL<C$，所以CL也可以作为B的右子树。同理，由于$C<CR<A$，所以CR也可以作为A的左子 树：

   

   最后，由于$B<C<A$，所以A、B分别可以作C的右、左子树，最终排序树达到平衡：

   

   总结方法：

   情况：由于在A的左孩子的右子树上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去 平 衡。

   方法：先将A结点的左孩子的右子树根结点C向左上旋转提升至B结点的位置，然后再向右上旋转提升 至A结点的位置。

   

4. RL平衡旋转

   与RL平衡旋转正好镜像。

   总结方法：

   情况：由于在A的右孩子的左子树上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡。

   方法：先将A结点的右孩子的左子树根结点C向右上旋转提升至B结点的位置，然后再向左上旋转提升至A结点的位置。

   ⚠️ LR和RL旋转时，新结点究竟插入C的左子树还是右子树不影响旋转过程。

3 平衡二叉树的删除

与平衡二叉树的揷入操作类似, 以删除结点 w 为例来说明平衡二叉树删除操作的步骤:

1. 用二叉排序树的方法对结点 w 执行删除操作。
2. 从结点 w 开始, 向上回溯, 找到第一个不平衡的结点 $\mathrm{z}$ (即最小不平衡子树); $\mathrm{y}$ 为结点 $\mathrm{z}$ 的高度最高的孩子结点; $\mathrm{x}$ 是结点 $\mathrm{y}$ 的高度最高的孩子结点。
3. 然后对以 z 为根的子树进行平衡调整, 其中 x 、 y 和 z 可能的位置有 4 种情况:
   • $\mathrm{y}$ 是 $\mathrm{z}$ 的左孩子, $\mathrm{x}$ 是 $\mathrm{y}$ 的左孩子 (LL, 右单旋转);
   • $\mathrm{y}$ 是 $\mathrm{z}$ 的左孩子, $\mathrm{x}$ 是 $\mathrm{y}$ 的右孩子 (LR, 先左后右双旋转);
   • y 是 z 的右孩子, x 是 y 的右孩子 (RR, 左单旋转);
   • y 是 z 的右孩子, x 是 y 的左孩子 (RL, 先右后左双旋转)。

这四种情况与揷入操作的调整方式一样。不同之处在于, 揷入操作仅需要对以 $\mathrm{z}$ 为根的子测 进行平衡调整；而删除操作就不一样, 先对以 $\mathrm{z}$ 为根的子树进行平衡调整, 如果调整后子树的高度减 1, 则可能需要对 $\mathrm{z}$ 的祖先结点进行平衡调整，甚至回溯到根结点 (导致树高减 1)。

由于上述的平衡要求并不低，而且后续的插入很容易打破平衡，所以整理操作会很频繁的进行，并且整理多数情况需要操作树的整体，这使得它的性能不怎么好，在实际的场景中应用更广泛的是红黑树。