红黑树

第02部分 红黑树

一、定义

AVL树尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多达O(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。在AVL树“适度平衡”标准的基础上，进一步放宽条件，适度平衡：任一节点左、右子树的高度，相差不得超过两倍。

首先，如下图所示统一引入 $n + 1$ 个外部节点，以保证原树中每一节点（现称作内部节点，白色八角形）的左、右孩子均非空：

由红、黑两色节点组成的二叉搜索树若满足以下条件，即为红黑树。

• 树根始终为黑色
• 外部节点均为黑色
• 其余节点若为红色，则其孩子节点必为黑色
• 从任一外部节点到根节点的沿途，黑节点的数目相等

info

定义解读：

• 基于前两个条件，红色节点都是内部节点，且其父节点及左、右孩子必然存在。
• 基于条件三，红节点之父必为黑色，因此树中任一通路都不含相邻的红节点。
• 从任一节点通往其任一后代外部节点的沿途，黑节点的总数亦必相等。
• 除去（黑色）外部节点，沿途所经黑节点的总数称作该节点的黑高度（black height）。如此，所有外部节点的黑高度均为0

二、2-4 B-树

定义：2-4树的含义是，一个树节点的子节点数量范围是2-4之间。那就是说：

1. 节点内部有一个数据项的节点总是有两个子节点；
2. 节点内部有二个数据项的节点总是有三个子节点；
3. 节点内部有三个数据项的节点总是有四个子节点；

每棵红黑树都等价于一棵(2,4)-树。（在完全彩色版尚未出版前本书约定，分删以圆形、正方形和八角形表示红黑树的红节点、黑节点和颜色未定节点，以长方形表示B-树节点）可以发现(2,4)-树中的每个节点应包含且仅包含一个黑关键码，同时红关键码不得超过两个。

三、平衡性

包含 $n$ 个内部节点的红黑树 $T$ 的高度 $h$ 满足下面的条件：

$$log_2(n+1) \leq h \leq 2 \times log_2(n+1)$$

• 左边的等号考虑的是完全二叉树的情况，显然这种高度是最小的
• 右边等号证明如下：

若将 $T$ 的黑高度记作 $H$ ，则 $H$ 也是 $T$ 所对应(2,4)-树 $T_B$ 的高度，故由8.2.4节关于B-树高度与所含关键码总数关系的结论，有：

$$H \leq log_{2} \lfloor \frac{n+1}{2} \rfloor + 1 \leq 2 \times log_2(n+1)$$

另一方面，既然任一通路都不含相邻的红节点，故必有：

$$h \leq 2H \leq 2 \times log_2(n+1)$$

尽管红黑树不如完全树理想平衡，不如AVL树的适度平衡，其高度仍控制在最小高度的两倍以内。依然保证了适度平衡。

四、基本算法

个人觉得交大的数据结构P276讲解的更好，两个书思路都是一致的，但是清华这个书硬是把转换的结果化成一个B-树，整的人看起来不知所以然。但是看熟悉了之后就决定一目了然了。

（一）插入算法

插入首先需要经过查找过程，调用接口search(e)做查找之后，确认目标节点尚不存在，在查找终止的位置x处创建节点，并随即将其染成红色。（除非此时全树仅含一个节点）。现在只需要解决一个问题：此时x的父亲也可能是红色。称作“双红缺陷”。

将x的父亲与祖父分别记作p和g。此前的红黑树合法，故作为红节点p的父亲，g必然存在且为黑色。g作为内部节点，其另一孩子（即p的兄弟、x的叔父）也必然存在，将其记作u。u的颜色不同，分两类情况分别处置。

a）双红修正（RR-1）

标题里面说的RR是Red Red的意思。考查u为黑色的情况。此时，x的兄弟、两个孩子的黑高度，均与u相等。图8.25(a) 和(b)即为此类情况的两种可能（另两种对称情况，对此考虑即可）。

• A图解释：把 $P$ 的右儿子绑到 $g$ 的左儿子，然后把 $P$ 提起来，作为新的根节点（交大数据结构P277）
• B图解释：把 $X$ 的左儿子绑定到 $P$ 的右儿子，然后把 $X$ 提升到 $g$ 的左儿子（相当于经过一次左旋转）然后把 $X$ 的右儿子绑到 $g$ 的左儿子，把 $X$ 提升到根节点。（相当于经过一次左旋转）
• C图解释：上面说的AB两个图的情况，仅仅旋转完还不够，需要把旋转后的根节点设为黑色（图C里面的B），根节点B的两个儿子设置为红色。（为什么要这样设置？如果B设为红色？那万一B是整根树根节点呢？如果B设为黑色，AC也全部设置黑色，那这一条路径上的黑色节点的数量增加了一个！所以不对）
• 当然，关于AB两个图的对称情况，这里就没有画了。需要自行考虑。

b）双红修正（RR-2）

节点u为红色的情况。此时，u的左、右孩子非空且均为黑色，下图里面的最底层的那五个子树黑色高度一定都相等。

• 以上图A为例子，只需要把 $P,U$ 变成黑色节点，$G$ 节点变成红色节点，$X$ 保持不变
• 以上图B为例子，只需要把 $P,U$ 变成黑色节点，$G$ 节点变成红色节点，$X$ 保持不变
• 那么问题就是，如果G的父亲节点是红色，有可 在更高层再次引发双红现象，那就再次根据情况调整（无论是按照双红的1情况还是双红的2情况调整）。

（二）删除算法

（三）查找算法

五、完整代码