浅析二叉搜索树的平衡性

由于整理该部分笔记的时候太忙，所以我暂未提供代码实现，若之后写了，你应该能在此处找到

一、二叉搜索树的平衡

1.1 产生背景

• 二叉搜索树章节我们提到，要将树保持为类完全（叶节点都在最后一行即可，不一定要像完全二叉树一样叶节点从左到右无缺排列）或完美二叉树才可以使得时间复杂度最小为

\[O(h)=O(\log{n})\]

• 由于二叉搜索树的插入或删除操作会导致搜索树脱离类完全/完美二叉树之列，所以二叉搜索树的平均高度会递增到$O(\sqrt{n})$，这是我们不愿意看到的
• 我们想要一直保持二叉搜索树是类完全/完美的二叉树，以保证最优的时间效率，也就是说我们需要在每次增删树节点的时候维持二叉树的平衡（Balance）

1.2 平衡的定义

• 二叉树的平衡有以下常见的三种
  • 高度平衡（Height Balance）：对比某节点的左右子树的高度，高度差不可大于$1$（AVL树）
  • 根节点到最近空指针的距离平衡（Null-Path-Length Balance）：对比某节点的左右子树的根节点到其最近的空后代节点的路径，二者的相对性质有所限制（红黑树）
  • 重量平衡（Weight Balance）：对比某根节点的左右子树分别可新增的节点数占该根节点总可新增的节点数的比例，二者相对大小关系有限制（BBalpha树）

二、AVL树

2.1 介绍与定义

2.1.1 形式

• AVL是其提出者的名字（Adelson-Velskii and Landis）的缩写，又称平衡二叉树（Balanced Binary Tree），AVL树是二叉搜索树的子类，其在此基础上满足以下条件
  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过$1$
  • 它的左右子树都是平衡二叉树

• 根据定义可知，所有的完全二叉搜索树都是AVL树

2.1.2 平衡因子

• 一个二叉搜索树节点的平衡因子（Balance Factor）等于其左子树高度减去其右子树高度

\[bf=h_{left}-h_{right}\]

• 对于AVL树来说，其所有节点都必须满足

\[bf\in\{-1,0,1\}\]

• 下图中这个二叉搜索树就不是AVL树

2.2 高度与节点总数

• 高度为$h$的AVL树的节点总数的最大值为$(2^{h+1}-1)$，即高度为$h$的完美二叉搜索树的节点总数；在已知总数$n$的条件下，可以求其能搭建的最小高度的AVL树（之前推导过，就不写过程了）

\[h_{min}=[\log_2{n}]\]

• 高度为$h$的AVL树的节点总数的最小值为$F(h),h\in N$，假设高度为$h$的AVL树的左子树高度为$(h-1)$，右子树高度为$(h-2)$，则有以下式子（最后加上的$1$是指根节点）

\[F(h) = F(h-1) + F(h-2) + 1\]

• 我们已知$F(0)=1$和$F(1)=2$，以此我们可以递归地推出后面的$F(h)$，可以看出$(F(h)+1)$是一个从$2、3$开始的斐波那契数列；空树高度定义为$-1$，不纳入讨论范围

• 该数列的通项可以近似为，其中黄金比例$\phi \approx 1.6180$

\[F(h) \approx 1.8944 \phi^h - 1\]

• 由此我们也可以得出在给定节点数$n$的情况下，可以搭建出的AVL树的最大高度

\[h_{max}=\log_{\phi}(\frac{n+1}{1.8944})=1.4404\lg(n+1)-1.3277\]

• 相同节点总数的AVL树，其最大高度和最小高度之间的差别会随着总数的增大而增大

2.3 新增节点

2.3.1 旋转重构

• 在介绍平衡的概念时便知道平衡的意义就是最优化时间效率为$O(\log{n})$，此处不赘述；为了维持AVL树节点的平衡性，我们需要对二叉搜索树的节点增删的函数进行重写，以保证每次增删节点时能检测经历了增删操作后的搜索树是否仍然符合AVL树，否则要对树进行旋转重构

2.3.2 左左型重构

• 往搜索树左子树上（以左左型）新增节点导致失衡时

• 通过直接右旋的方式恢复平衡

• 参考下面的实际例子

2.3.3 左右型重构

• 往搜索树左子树上（以左右型）新增节点导致失衡时

• 我们将子树$B_R$分解

• 此时先将左子节点$b$左旋（此时$D_R$和$D_L$脱出），再将根节点$f$右旋，即可得到下图第二个树，此时$d$变为新的根节点，$D_R$则附到$f$左子树位置、$D_L$则附到$b$右子树位置

• 参考下面的实际例子

2.3.4 右右型重构

• 往右子树上以右右型新增节点时，同理直接左旋

2.3.5 右左型重构

• 往右子树上以右左型新增节点时，同理先将右子节点右旋，再将根节点左旋

2.4 删除节点

• 删除节点也可能导致AVL树的（多处）失衡，从而变成普通的二叉搜索树，此时可以按照上面的左左、左右、右右、右左的四型情况进行匹配分析，然后采取对应旋转操作，如下例

• 上图中$1$的删除会导致$3、8、21$共三处的失衡，我们先处理最底层的$3$的右右型的失衡

• 恢复后会发现仍然存在$8、21$的失衡，依然遵循从下往上的顺序，先处理$8$的右左型的失衡

• 然后发现$21$仍然存在右右型的失衡，解决这个节点后就完成了平衡的恢复

2.5 空间利用率

• 之前的完全二叉树我们可以用数组来进行存储，因为其在节点数为固定$n$的条件下对空间的利用率十分高，而AVL树在给定$n$节点数的情况下，空间利用率最低的情况即高度最高的情况

\[h_{max}=\log_{\phi}(\frac{n+1}{1.8944})=1.4404\lg(n+1)-1.3277\]

• 这样的一棵树如果用数组按顺序存储每一行的话，需要的容量即高度为$h_{max}$的完美二叉树的节点总数的数量，数量级为$n^{1.44}$

\[V_{array}=2^{h_{max}+1}-1\approx0.7968n^{1.44}\]

• 对比完全二叉树，这是不理想的，参考下图曲线，所以不建议用数组存储AVL树

三、红黑树

3.1 介绍与定义

3.1.1 基本定义

• 红黑树（Red-Black Tree）属于二叉搜索树，其所有的节点被标记为红或黑（0或1），通过维持以下几个特性，以确保自身处于近似平衡的状态（红黑树并不是严格的AVL式的平衡）
  • 根节点必须为黑
  • 红节点的左右子节点如果存在，必须为黑
  • 从任意节点出发，向下抵达任意自身的空节点（注意不是叶节点，而是空节点，包括内部节点的可能存在的空子节点，或叶节点的两个空子节点）的路径中，途径黑节点的数量相同

3.1.2 易错误区

• 注意上述基本定义中的第三点条件，下面是针对其的一个很容易忽略的误区

• 下图的示例才是真正的红黑树，可以观察到两个有意义的点
  • 但凡是非满的黑色内部（Internal）节点，其子节点必然是红色的叶（Leaf）节点，这也保证了不会出现上面那种反例（也就是说可以通过观察黑色叶节点的父节点来快速判断其是否符合红黑树，若父节点非满，那就说明此树不符合红黑树）
  • 下图右侧的树满足红黑树，但不满足以平衡因子为判据形式的平衡，但其仍能保持$O(\log{n})$的时间效率，这是因为红黑树任意节点的左右子树的高度差不会超出$2$倍，所以红黑树平均的时间复杂度会多一个系数，而系数是可以被忽略的

3.1.3 定义衍生性质

• 第二定义衍生：红节点的父节点必然为黑节点
• 第三定义衍生：黑节点若只有一个子节点，那么这个子节点一定是红的
• 第三定义衍生：红节点要么是叶节点，要么是有两个黑子节点的满节点

3.2 高度与节点总数

3.2.1 最坏情况枚举

• 用最少的节点数搭出高度最高的红黑树，这就是最坏的情况，因为存储同样多的节点，却需要耗费最大的搜索时间
• 我们观察Null Path上的黑节点数$k$，其取值为$1、2、3$的红黑树的最大高度分别如下图（绿框即为前一棵树）所示，其节点总数分别为$n=2、6、14$，高度分别为$h=1、3、5$

• 下面是利用$k=3$的最坏红黑树造出的$k=4$的最坏红黑树，其节点总数为$n=30$，高度为$h=7$

• 对比AVL树在节点总数为$33$的时候能造出的最大高度为$6$

3.2.2 分析$k、n、h$

• 由于每棵$k=i$最坏高度的树都是由$k=i-1$的最坏高度树构造而来，高度每次稳定递增$2$，所以高度$h$和空路径黑节点数$k$之间的关系为

\[\begin{aligned} h_k&=h_{k-1}+2\\ \Rightarrow h_k&=2k-1 \end{aligned}\]

• 通过第$k$棵树的构造规则，每次都需要新增两棵高度为$k-2$、节点总数为$2^{(k-2)+1}-1$的纯黑完美搜索树，所以$k$的最坏红黑树的节点总数为

\[\begin{aligned} n_k&=n_{k-1}+2+2\cdot(2^{(k-2)+1}-1)\\ &=n_{k-1}+2^k\\ \Rightarrow n_k&=2^{k+1}-2 \end{aligned}\]

• 我们由上述两个式子消去$k$，可以算出给定节点数$n$的红黑树能造成的最大高度（即最坏情况）

\[\begin{aligned} h_{worst}&=2\cdot(\log_2(n+2)-1)-1\\ &=2\log_2(n+2)-3 \end{aligned}\]

3.3 与AVL树比较优劣

3.3.1 AVL树的优势

• 红黑树关于$n$的$h_{worst}$的函数增速比AVL树的$h_{worst}=1.4404\lg(n+1)-1.3277$要更快，所以在需要对树进行大量搜索的场景下，红黑树处于时间复杂度上的劣势

3.3.2 红黑树的优势

• AVL树增删节点需要进行比红黑树更多的旋转操作，复杂度较高，所以在需要较多插入和删除操作的场景下AVL树相比下处于时间复杂度的劣势
• 每个红黑树节点只需要1bit的布尔值来记录红黑颜色，而AVL树则需要花费更多空间记录取值可能为${-1,0,1}$的平衡因子，所以在空间复杂度上AVL树处于劣势

3.4 新增节点

新增节点后要确保红黑树满足定义中的三个条件，其中前两个条件是局部的，而第三点是全局的；对于新增节点或子树后如何维持树的平衡，有自下而上和自上而下两种处理方式

3.4.1 Bottom-Up附加新节点

• Bottom-Up指的是在叶节点处插入新节点或子树后，从插入处开始向上进行一系列递归操作的维持红黑树平衡的方式
• 若新节点A的父节点B为黑色，那么新节点就是作为红色而直接平衡；但若父节点B是红色的，那么就需要讨论如下图的两种情况
  • 第一种就是祖父节点C（一定是黑色）只有B一个子节点，那么直接旋转即可，同样分左左、左右、右右、右左四型来旋转处理
  • 第二种就是C有两个子节点B和D，那么此时可以如下图转换颜色，此时整个红黑树就是满足关于Null Path黑节点数相等的第三定义的，但是此时C的父节点若是红色，就会产生问题，相当于将C树作为新的子树以Bottom-Up形式添加到树上，参考下一小节的内容进行递归处理该问题

3.4.2 Bottom-Up附加新子树

• 上面小结的第二种情况涉及插入树的处理，如下图的左侧的A树（左左型）、右侧的D树（左右型，故将D树的左右子树拆分开来分析）都面临着自身为红，父节点也为红的情况，此时就采取和AVL树同理的翻转来平衡

• 上图中的两个连续的红节点的黑色父节点的字节点除了自己是红色的之外，另一个子节点是黑色的，下图则是讨论两个子节点均为红色的情况，需要采取颜色互换的方法来维系平衡；若互换后导致根节点为红，则进行递归处理即可

• 最终我们会递归至最根部的根节点，此时若其为红，则我们需要将其变为黑色

3.4.3 Bottom-Up综合例子

• 为了体会完整的处理流程，参考下面的一系列例子（绿色框为新加入的节点或子树，蓝色框为绿色框衍生的要操作的树区域，也可以表示操作完成后导致新的冲突时，作为递归处理起点的新插入的子树），首先从插入单个节点的情况一开始

• 然后是插入单个节点的情况二的无冲突情况

• 然后是插入单个节点的情况二的有冲突情况

• 再看一个直接插入子树的例子，其实此例和上一个例子（插入新节点后导致冲突，这才需要将树作为整体进行递归）一样，下面这个例子不过是直接用树作为附着物罢了

3.4.4 Top-Down介绍

• Top-Down指的是指的是在叶节点处插入新节点或子树后，从最根部的节点开始，沿着到达新插入的节点处的路径进行操作以维护红黑树的平衡，相比自下而上的好处就是无需向上递归
  • 每次插入新节点时（或新红黑树子树，只考虑此树的根节点），先从根节点开始，一路搜寻到达新节点的路径，在搜索过程中若发现路径上的黑节点拥有两个红色子节点的，则将父子颜色替换（黑根变红，红双子变黑），然后继续向下搜索
  • 路径的搜索自上而下，不会回头，若是某次颜色替换产生的已搜索出的路径的前端出现了新的有双红子节点的黑节点，无需管他
  • 最终只会需要至多一次的旋转操作，就可以使得此红黑树重新恢复平衡

3.4.5 Top-Down方法演示

• 新增单个节点46，从根节点20一路向下搜索到46途中并未发现拥有双红子节点黑节点

• 新增节点90，在搜索路径（下图中紫色的线即为路径标识）的过程中发现了85这个家伙，对其进行颜色转换后造成了红色冲突，我们将其通过Bottom-Up中同理的方法进行旋转即可解决

• 如果发现最根部根节点有两个红色子节点，那么就需要在转换颜色后再将根节点变黑，以符合红黑树定义的第一条

3.4.6 对比两种方法

• 对同一个流程，分别使用Bottom-Up和Top-Down两种方法进行处理，会发现最终得到的结果树是不一样的，但是都是合法的红黑树

3.5 删除节点

• 写累了，先参考这里吧

四、BB($\alpha$)树

4.1 介绍与定义

• 我们观察下面这个树，其右子树是不符合重量平衡的，因为两个比例之间的差距太大了

• BB($\alpha$)树的$\alpha=\frac{根节点某子树上的空节点数}{根节点后代中所有空节点数}$，显然左右子树的该比例之和为$1$，所以可用$\alpha$与$(1-\alpha)$分别来表示左右子树的这个比例
• 而BB($\alpha$)树要求任意一个节点的$\alpha\in(0,\frac{1}{3}]$以维持重量的平衡，也就是说任意一个节点的某子树的$\alpha$不能超过$\frac{1}{3}$，上图反例中的$\frac{4}{5}$就超了，所以不平衡

4.2 最优时间效率

• 比例$\alpha$在不超出$(0,\frac{1}{3}]$范围的同时，将其现在在$[\frac{1}{4},1-\frac{\sqrt{2}}{2}]$这个更严格的范围内有助于使得时间复杂度为最低的$O(\log{n})$