红黑树？看这篇就G(够)了！

简介

红黑树（Red Black Tree，RBT）是一棵二叉搜索树（BST），每个结点都拥有自己的颜色，红色（Red）或者黑色（Black）

通过一些条件进行约束，红黑树达到了近似平衡。

AVL 与红黑树的优缺点

• 红黑树使用非严格的平衡换取增删结点时的旋转次数降低，而 AVL 严格平衡，意味着在增加或删除结点时，根据情况的不同，旋转的次数比红黑树要多
• AVL 的结构相较于红黑树更为平衡，因此 AVL 的查询效率更高
• 总体来说，红黑树的统计性能高于 AVL，但如果是频繁查询而少次增删的场景，使用 AVL 更加合适

正文

1. 红黑树的性质

1.1 结点的结构

属性

红黑树的每个结点包含 5 个属性：

• color 结点的颜色
• key 结点的大小（这个大小并不是数值上的大小，而是比较的大小）
• left 左孩子结点
• right 右孩子结点
• p 父结点

相比于 AVL 树，红黑树的属性只增加了颜色 color

结构

他俩还有一个不同，AVL 以真实存在的结点作为叶子结点，而红黑树以空指针 NIL 作为叶子节点

如图所示，暂不考虑红黑树结点的颜色，只需明白 AVL 和红黑树在结构上的不同

由于叶子结点 NIL 是个空指针，所以我们在作图时可以隐藏叶子结点。并将 NIL 视为外部结点，其他带有关键字 key 的结点视为内部节点

因此，图 1.1.1 中的红黑树可以简化为 图 1.1.2

1.2 性质

性质

红黑树有以下五种性质

1. 每个结点只能是红色或者黑色的
2. 根节点是黑色的
3. 每一个叶子结点（NIL）都是黑色的
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的
5. 对任意结点，从该路径到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

红黑树没有那么神秘，只要符合了这五条性质，就是一棵红黑树

---

对于性质 1，只要你不发病去搞个五颜六色的结点，是不会被破坏的

而性质2和性质3，一来是不难记，二来的话在后面比较少提到（或者说已经默认了）

性质4和性质5需要好好理解并记住，在插入和删除部分会经常破坏这两个性质，只有理解了这两个性质才能更容易地阅读下文

黑高

黑高很重要，一定要充分理解了再往下看

图1.2.1就是一个红黑树的例子

图中的数字表示从当前结点 x 到叶结点路径上经过的黑色结点数目（不包括当前结点），称为该结点的黑高（black-height），记为 $bh(x)$

根据性质5，黑高的值是明确的，因为从该结点出发，下降到叶结点的任意简单路径的黑色结点个数都相同

tips: 简单路径的意思是一路往下走，不能往上去父节点绕一圈

---

例如：

• $bh(A) = 1$ ，因为只经过了一个 NIL。
• $bh(C) = 2$，因为经过了 A 和 NIL / 或是 B 和 NIL
• $bh(D) = 2$，因为不管走左边还是右边，都经过两个黑色结点

需要注意的是，计算黑高时不能将结点自身计算进去，这在黑高的定义中也明确声明了

---

由于我们通常将注意力放在红黑树的内部结点上，因为他们存储了关键字的值，所以在后面的图片中将忽略叶结点。如 图1.2.2

再给出几张红黑树的图片理解一下性质

1.3 引理

引理：一棵有 n 个内部结点的红黑树的高度至多为 $2\lg(n + 1)$

关于红黑树的高度与时间复杂度（查找）的计算

1.3.2 是《算法导论》中的严格证明，1.3.1 是我自己的理解方式。

因为我觉得书中的证明并不好记，所以写到了后面

1.3.1 个人理解

（本节中“结点”指代“内部结点”，不包括 NIL）

目标：求得一棵 N 结点红黑树的时间复杂度

红黑树与 AVL 一样，都是自平衡的 BST，所以查找效率的计算方式一致

一棵高度为 h 的二叉搜索树（BST）上的搜索时间为 $O(h)$

那么 AVL 树的高度 $h = \lg(n)$，所以搜索时间为 $O(\lg n)$

而红黑树与 AVL 不同，不是绝对平衡的，所以 h 并不是一个固定的值，但却因为保持性质5，而拥有最大值。（不妨动手画一棵10个结点以上的红黑树，会发现高度不是能无限扩展的，否则性质5将被破坏）

---

那么第一步，我们将问题“N 结点的红黑树的时间复杂度是多少”转化成了“N 结点的红黑树的最大高度是多少”

目标：求得 N 结点红黑树的最大高度

直接求N 结点的红黑树的最大高度是困难的，我们换个思路。

根据性质5我们可以知道，红黑树的平衡与树的高度没有直接关系，而是与黑高息息相关。

而根据性质4，极端情况下，树的高度等于两倍的黑高（红黑交替），即 $h(x)_{max} = 2bh(x)$

---

那么又可以把目标换一换，换成求 N 结点红黑树的最大黑高

N 个结点堆成一棵树，路子可多了去了，到底什么情况下才能拥有最大的黑高，好求吗？不好求。

但是把这句话反过来看就容易多了。

求 N 结点红黑树的最大黑高，等价于，求黑高为 $bh(x)$ 的红黑树所包含的最少结点数

理解一下吧

下面开始计算

---

考虑到读者应该是初学红黑树，我再提示一下，黑高 $bh(x)$ 的计算并不包括 x 结点自身。

如下图中 $bh(c) = 1$ 不是因为 C 结点是黑结点，而是因为它的子节点 NIL 是黑色

以 x 为根，黑高为 $bh(x)$ 的子树所包含的最少结点数

首先需要明确一个概念，虽然《算法导论》中没有指出，但是我们可以根据性质5自行证明：一棵全黑的红黑树必定是满二叉树

基于此，开始我们的计算过程

在这里，我把红黑树分为两种情况：

1. 全黑
2. 包含红色结点

那么我们需要分别计算这两种情况并取最小值

1. 全黑

   上面指出了一棵全黑的红黑树必定是完全二叉树，所以黑高为 $bh(x)$ 的子树如果是全黑，那么它的结点数量是可以定量计算的。

   一棵高度 $h = bh(x)$ 的完全二叉树的结点数量 $N = 2^{bh(x) } - 1$

2. 包含红色结点

   假设在第 k 层（k > 1，性质2) 出现了第一个红色结点

   

   • 那么这时 $bh(x) \ge k - 1$ ，同时结点数量 $N \ge 2^{k - 1}$ (当第 k 层只有一个内部结点且为红色时取等号)

   • 而如果是全黑的情况，在 $bh(x) = k - 1$ 的条件下，

     结点数量 $N = 2^{bh(x)} - 1 = 2^{k - 1} - 1$ ，一定小于上面的 2^{k - 1}

所以可以得出结论：一棵黑高为 bh(x) 的树的结点数量 $N \ge 2^{bh(x)} - 1$

或许上面对于包含红色结点的情况描述的不容易理解，那么我再换一种方式：

• 首先画出一棵 $bh(x) = k$ 的全黑 红黑树，在这里我将 k 取为 3

  

  如果想要保持黑高不变，并且添加红色结点

  要么在底层添加新的结点，要么将上面某个结点染红

  在底层添加红色结点势必增加结点数量，所以我们仅讨论染色的情况：

  任意挑选一个结点（不能是根节点 X）染红

  

  这时候黑高已经失衡了，所以我们需要向结点 6 和结点 9 添加黑色子节点才能保证黑高的平衡，而这也将增加结点的数量

  所以得出结论：一棵黑高为 $bh(x)$ 的树只有在结点全黑时拥有的结点数最少

  进而可以推断出：一棵黑高为 $bh(x)$ 的树的结点数量 $N \ge 2^{bh(x)} - 1 $

有了这个结论，我们就可以计算N 结点的红黑树的最大高度了

---

$$已知：N \ge 2^{bh(x)} - 1 \\ 极端情况下，一条最长的路径红黑交替，那么\\ bh(x) = {h \over 2}\\ 代入上面的式子\\ N \ge 2^{h \over 2} - 1\\ N + 1 \ge 2^{h \over 2}\\ 两边取对数\\ \lg{(N + 1)} \ge {h \over 2} \\ h \le 2\lg{(N + 1)}$$

得出结论：N 结点的红黑树最大高度是 $2\lg{(N + 1)}$

所以红黑树的搜索时间复杂度是 $O(\lg n)$

1.3.2 严格证明

以下内容出自（照搬） 《算法导论》第三版（机械工业出版社）

证明：一棵有 n 个内部结点的红黑树的高度至多为 2lg(n + 1)

先证明以任一结点 x 为根的子树中至少包含 $2^{bh(x)} - 1$ 个内部结点。要证明这点，需要对 x 的高度进行归纳。

如果 x 的高度为0，则 x 必为叶结点 NIL，且以 x 为根节点的子树至少包含 $2^{bh(x)} - 1 = 2^0 - 1 = 0$ 个内部结点。

对于归纳步骤，考虑一个高度为正值且有两个子结点的内部结点 x。每个子结点有黑高 $bh(x)$ 或 $bh(x) - 1$，其分别取决于自身的颜色是红还是黑。由于 x 子结点的高度比 x 本身的高度要低，可以 利用归纳假设得出每个子结点至少有 $2^{bh(x)} - 1$ 个内部结点的结论。

于是，以 x 为根的子树至少包含 $(2^{bh(x) - 1} - 1) + (2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$ 个内部结点，因此得证。

---

为完成引理的证明，设 h 为树的高度。根据性质4，从根到叶结点（不包括根节点）的任何一条简单路径上都至少有一半的结点为黑色。因此，根的高度至少为 h / 2；于是有

$$n \ge 2^{k / 2} - 1$$

把 1 移到不等式的左边，再对两边取对数，得到 $\lg(n + 1) \ge h / 2$，或者 $h \le 2\lg(n + 1) $

由该引理可知，SEARCH 操作可在红黑树上在 $O(\lg n)$ 时间内执行，因为这些操作在一棵高度为 h 的二叉搜索树上的运行时间为 $O(h)$

2. 旋转

INSERT（插入）和 DELETE（删除）在含 n 个关键字的红黑树上，运行花费时间为 $O(\lg n)$。由于这两个操作对树做了修改，结果可能违反红黑树的性质。为了维护这些性质，必须要改变树种某些结点的颜色以及指针结构。

修改结点的颜色，称为染色，将在下面的插入和删除部分细讲

关于旋转的操作，红黑树与 AVL 树一致，可以参考下面这篇文章

AVL平衡二叉树如何旋转 | Cimoc

3. 插入

3.1 纯纯的插入

单纯的插入很简单，和 BST 没什么区别，而修复平衡才是难点

不过这里有一个问题，插入的结点是什么颜色呢？

答案是红色，原因是，红色的“容错率”高

插入红色结点可能会破坏性质4，而插入黑色结点一定会破坏性质5

同时，红色结点在修复平衡时能起到非常大的作用

不多bb，我直接把插入的伪代码贴上来，同样出自《算法导论》，不过我会加上注释

/* 
 * 这部分代码的函数调用（方法名）是 RB-INSERT(T, z)
 * T 表示这棵树，z 是插入的结点
 * 由于是本文首次贴代码，所以声明一下，任一结点都包含以下5个属性
 * p: 父结点
 * left: 左子结点
 * right: 右子结点
 * key: 结点的关键值
 * color: 结点的颜色
 */

// y 用来指向我们插入 z 的位置的父节点
y = T.nil

// x 用来找我们要插入的位置，当然最后一定是指向 NIL的，与 BST 插入大同小异
x = T.root

// 都学红黑树了，不会不知道 BST 的插入是插到叶子结点吧，不会吧不会吧
while x ≠ T.nil
	// 既然 x 还没走到底，那么 y 也要同步走
	y = x
	
	// 根据关键值判断 x 到底走左子树还是走右子树
	if z.key < x.key
		x = x.left
	else 
		x= x.right

/* 
 * 跳出循环时，x 已经是 NIL 了，不参与接下来的操作
 * 不过 y 作为父节点还是需要参与一些指针的修改的
 * 首先是将 z 的父节点设置为 y
 */ 
z.p = y

// 如果 y 是 NIL，说明根本就没进上面的循环，即树 T 是空的
if y == T.nil
	// 那么这时候就得将树的根节点设置为 z
	T.root = z

// 否则的话根据关键值判断，z 是 y 的左节点还是有结点
elseif z.key < y.key
	y.left = z
else
	y.right = z

// z 是新插入的结点，所以两个孩子结点都得是 NIL
z.left = T.nil
z.right = T.nil

// 新插入的结点设置为红色
z.color = RED

// 虽然没破坏性质5，但是可能会破坏性质4，即出现连续的红色结点
// 所以要调用平衡的修复算法，见下一节 3.2 平衡修复
RB-INSERT-FIXUP(T, z)

3.2 平衡修复

叔节点与祖父结点

父节点是什么意思不用我多讲了，这里我再给出两个名词：叔结点 和 祖父结点

叔结点：父节点的兄弟结点

祖父结点：父节点的父节点

失衡原因

根据 3.1 中的伪代码，应该不难发现造成失衡的原因只有一个就是破坏了性质4，出现了连续的红色结点。也就是当前结点与父节点同时为红色

根据性质4，可以确定的是这时候祖父节点一定为黑色，那么不确定的只有叔结点

根据性质1，结点只有两种颜色，所以我们可以简单地将情况分为以下两种：

1. 叔结点为红色

   

2. 叔结点为黑色

   

• 不要再问没有叔结点怎么办啦！！！

  没有作为“内部结点”的叔结点，那叔结点不就是 NIL 吗，还是黑色呀

• 也不要再问父节点是黑色怎么办啦！！！

  父节点是黑色又没有失衡，那不是最好吗，一个性质都没有打破

• 更不要再问没有祖父结点怎么办啦！！！没有祖父结点就意味着父节点是根节点，那父节点一定是黑色，这次插入不会失衡

接下来来讨论这两种情况的处理方案，如何重新维护红黑树的平衡

由于二叉树的对称性，反转左右后的代码几乎相同，下面只介绍父节点是祖父结点的左孩子的情况。

3.2.1 case 1 叔结点为红色

这种情况的处理方式十分简单，也很好理解。我们先梳理一下目前的信息：

1. 父节点与叔结点为红色
2. 祖父结点为黑色

那么不是就简单了吗，将这两层（不是指整棵树，仅仅是这棵子树的两层）颜色互换不就好了。

这样的话不仅黑高没有变化，连当前结点与父节点的颜色冲突也解决了。

不过新的问题也随之而来，祖父结点突然变成红色了，万一它的父节点也是红色，那不是又违反性质4了？

所以我们的 z 不能仅仅指向新增的结点，只要树还没平衡，我们的 z 就得移动到导致树失衡的点，上图中经过变换后，z 应该移动到结点 7

如果 z 移动后新的父节点是黑色，那么平衡修复成功

否则继续根据 z 的叔结点的颜色判断是 case 1 还是 case 2 进行平衡修复。

case 1 的解决方案治标不治本，除非你运气好，刚好没产生连续两个红色结点的冲突，但只要你还在往红黑树里插入结点，总会遇到这种情况的。

---

这种方法也是有它的作用的，它类似于递归，不断地向上层寻找 case 2 的情况，直到寻找到 case 2，那么就会进入我们的下一小节 3.2.2

然而，case 2 并不一定会出现，如果你的运气真的非常非常好，递归上去走到了根节点还是 case 1 的情况，那不就修复了树的平衡？

细心的你可能发现了，case 1 可能会把根节点 染红 ，又或者是在上面的插入过程中，插入的结点就是根节点，那它同样是红色的

根据性质2，无论何时，根节点一定是黑色的

由于根节点不参与黑高的计算，所以我们重新把根节点染黑也不会破坏红黑树的性质

就算，在另一个世界里的红黑树要计算根节点的黑高，那你说，我把根节点染黑了，左右子树新增的黑高还能不一样不成

用一段伪代码再来感受一下这个过程：

y = z.p.p.right
if y.color == RED
	z.p.color = BLACK
	y.color = BLACK
	z.p.p.color = RED
	z = z.p.p

3.2.2 case 2 叔结点为黑色

case 2 可比 case 1 复杂多了，不能用那种 “取巧“ 的方式来修复平衡，得实打实的用旋转了，既然要旋转，那么根据 z 的位置又得分两种情况

大家都知道 AVL 树有四种旋转方式：LL、LR、RR、RL

我们这里只讨论“父节点是祖父结点的左孩子”的情况，所以第一个方向一定是 L，那么还剩下两种旋转：LL、LR

另外两种刚好对称，不写了

tips: 旋转会影响黑高，对于可能拥有子树的结点，我会用希腊字母表示子树，同时 z 是会移动的，表示造成失衡的红色结点，而不单单是我们刚插入的结点

3.2.2.1 case 2.1—LL

已知：

• LL 代表父节点是祖父结点的左孩子，同时，当前结点 z 是父节点的左孩子
• 父节点是红色，祖父结点与叔结点是黑色

如下图 3.2.1 所示，是 case 2.1 情况下的失衡子树

图中的黑高看起来失衡了，这是由于我们没有画出子树。

如果结点 z 是新插入的，那么原本的树就是平衡的，黑高也是平衡的。

如果结点 z 是通过 case 1 染红的，那么也没有影响黑高。

---

那么现在的问题就是，如何在不影响这棵子树的黑高的情况下，修复性质4。

理论阶段

BST 中我们不能任意移动结点，只能通过旋转的方式改变结点的相对位置。这也就意味着这两个红色结点无论如何都是相连的

（除非，你把他们的孩子结点转上来放俩人中间，直接破坏黑高，那可以当我没说。再说了，他们的子树也是我们在 case 1 中一步步平衡过来的，别想着去动了）

既然他俩是连体的，而 z 被染红是为了其子树的平衡，那么我们只有一条路可以走了，那就是将父节点 f 染黑

可这时候结点 g 的左右黑高就不平衡了，破坏了性质5，我们就需要借助旋转来修复了

开始修复

首先我们染黑结点 f，这一步不管早晚我们都得做，接下去就是解决左子树的黑高多了 1 的这个问题

接下来

不要再有染红祖父结点的冲动啦，这和 case 1 不一样

如果我们染红了祖父节点 g，不仅没有解决树的黑高问题，还使结点 g 可能与其父节点又产生了性质4上的冲突。

这样一来，哪怕我们修复了黑高，还得递归上去，这可不行。

所以我们要对结点 g 来一次 LL 旋转

这时候左子树的黑高问题被转移到了右子树，并且新的根节点 f 与原来一样是黑色，不会向上冲突。

接下来解决最后一个问题：右子树的黑高问题

右子树的这一部分结点可没有红色的，那就好办了

既然黑高多了 1，那找一个结点染红就行了，说的轻松，但是还是要注意细节

图中关于这几个内部结点的子树我并没有画出，但是我们也得考虑到它们

对比初始态（1）与状态（3），不难发现经过 LL 旋转后，只有子树 α 变动了相对位置

它的简单路径从 黑->红->α 变成了 黑->黑->α，由于红色不参与黑高计算，相当于是多了一个黑

所以我们需要染红的结点是原本的祖父结点 g

染红了 g 之后，对于 y 来说，g 可以看做是不存在的，那么 y 的状态也和初始态相同

到这里，我们不仅修复了性质4，同时也保持了原有的黑高，并且不会继续向上产生冲突，可以直接退出修复流程

再放张图对比下效果

说了这么多，总结起来其实就一句话

结论

如果祖孙三代连成一条向左的直线，且叔叔比较黑，那么我们染黑父节点，染红祖父结点，对祖父结点进行一次LL旋转

伪代码

z.p.color = BLACK
z.p.p.color = RED
LL(T, z.p.p)
// 算法导论中旋转方法的名称是 RIGHT-ROTATE，意为向右旋转
// 而我用 LL 这个名称表示路径的方向，实际的内部实现也是向右旋转

3.2.2.2 case 2.2—LR

开局一张图，内容全靠编

已知：

• LR 代表父节点是祖父结点的左孩子，同时，当前结点 z 是父节点的右孩子
• 父节点是红色，祖父结点与叔结点是黑色

和 3.2.2.1 中说的一样，父节点 f 是无论如何都得染黑的

区别在于我们怎么旋转而已

对 AVL 旋转熟悉的读者应该记得，LR = RR + LL

试想一下，如果我们对父节点 f 进行一次 RR 旋转会发生什么

RR

由于父节点 f 迟早都得染黑，我们不急于一时，这样能更清晰地看到整棵子树的黑高变化

转之前我们分析一下：

由于结点 z 与结点 f 都是红色，那么它俩的子树 α、β、γ 在不考虑 BST 规则（左 < 中 < 右）的情况下，互换位置对于树的平衡没有任何影响

而旋转是符合 BST 规则的

那么也就是说，我们对结点 f 进行一次 RR 旋转，其实相当于无事发生，任何性质都没有发生变化。

接下来就大胆地旋转吧！

到这一步感到熟悉吗，这就是 3.2.2.1 中的 LL 情况了

不过上图中 z 需要移动到 f 的位置（我还没有画出。真正旋转后的状态是 z 指向结点 5），记得在旋转前进行移动，因为代码实现简单。

完整的旋转过程如下图：

剩下的应该就不用我再讲一遍了

结论

如果祖孙三代形成一个小于号（LR），且叔叔比较黑，那么我们对父节点进行一次 RR 旋转，就变成了 LL 的情况。

接下来只要 LL 的操作就能修复树的平衡了

伪代码

z = z.p
RR(T, z)
// 接下来就与 3.2.2.1 相同了
z.p.color = BLACK
z.p.p.color RED
LL(T, z.p.p)

3.2.3 整合

流程图

经过 3.2.1 和 3.2.2 的学习，可以整理流程图如下

还是老样子，只画一半，对称的另一半请自行研究

伪代码

/* 
 * 循环的条件是当前结点 z 与其父节点同为红色
 * 因为 case1 只能将问题向上抛
 * 直到以下3种情况
 * 要么遇到黑色结点，那么就平衡了
 * 要么遇到根节点，不能向上递归了，这时候根节点被染红，所以伪代码的最后一定要把根节点染黑
 * 要么遇到 case 2
 */
while z.p.color == RED
	// 由于对称，这里只给出一半代码
	if z.p == z.p.p.left
	
		// y 是叔结点
		y = z.p.p.right
		
		// case 1
		if y.color == RED
			z.p.color = BLACK
			y.color = BLACK
			z.p.p.color = RED
			z = z.p.p
			
		// case 2
		else 
			// case 2.2-LR
			if z == z.p.right
                z = z.p
                RR(T, z)
                
            // case 2.1-LL 的代码与 case 2.2-LR 共用
            z.p.color = BLACK
            z.p.p.color = RED
            LL(T, z.p.p)
            
	else (对称的另一部分仅仅是将 left 与 right 互换)
T.root.color = BLACK

最后再贴张《算法导论》里的图巩固一下

图中浅灰色的结点代表红色

3.3 时间复杂度

插入

插入部分的时间复杂度与 BST 一致，$O(\lg n)$

平衡

AVL 的平衡修复是 $O(\lg n)$

而红黑树平衡性修复的时间复杂度，在最坏的情况下是 $O(\lg n)$，也就是“红黑相间”导致的 case 1 递归到根节点

但这毕竟是极端情况，大多数情况下，平衡性修复不会递归这么多次

虽然在形式上与 AVL 的平衡时间复杂度相同，但 AVL 的 $O(\lg n)$ 是固定不变的，红黑树在有的情况下甚至可以是 $O(1)$

4. 删除

删除比插入要更加复杂

开始之前，我们先来复习一下 BST 的删除

BST 的删除有 3 种情况：

• Case 1：要删除的结点，本身是一个叶子结点，直接删除即可
• Case 2：要删除的结点，只有一个孩子，让其父结点指向其孩子结点即可
• Case 3：要删除的结点 z，有两个孩子，先将其与后继结点 y 交换，随后删除那个后继结点（这时候的后继节点已经是 z 了）

注：后继结点即右子树中的最小数据结点，这个结点是一定没有左孩子的

---

在红黑树中，叶子节点是 NIL，所以我们要删除的内部结点永远不可能为叶子结点，只能是“两个孩子都是 NIL 的结点”，这种情况可以与 Case 2 一并处理

因此我们只需要考虑 Case 2 和 Case 3

而这两种情况的核心就是替换（不熟悉的话可以先去看看 BST 是如何删除结点的）

先定义一个删除结点的方法

同样是伪代码

/*
 * T 是整棵红黑树，a 是要删除的结点，b 是用来替换的结点
 * 这个方法只是将 b 替换 a 连到了其父结点。而他们的孩子之间的引用关系不在这里实现。
 * 要说为什么的话，因为如果 a 和 b 就是相连的，那么 b 替换 a 后不用管孩子结点，孩子还在它身上
 * 而 a 和 b 不相连，才会出现 b 的孩子失去父亲的情况，那时候需要自己实现引用关系的修改。
 * 说白了这一部分代码就是把反复重用的代码拎出来减少代码量的
 */
TRANSPLANT(T, a, b) {
	if T.root == a
		T.root = b
		b.p = nil
	else
		if a == a.p.left
			a.p.left = b
		else
			a.p.right = b
		b.p = a.p
}

当然删除结点可能引起红黑性质的破坏

接下来我们将分别介绍删除与平衡

4.1 纯纯的删除

4.1.1 Case 2 只有一个孩子

这种情况最简单，直接让孩子顶替自己的位置就好了

伪代码：

/* 
 * 记录要被删除的结点的颜色
 * 之所以取 original 这个名字，是因为另外一种情况下结点会被染色
 * 所以在这部分代码中不用深究
 * 记录这个变量的作用是，判断是否影响了树的平衡，在代码最后才用到
 */
original-color = z.color

if z.left == T.nil
	x = z.right // x 记录失去平衡的结点，见下图
	TRANSPLANT(T, z, z.right)
	
else
	x = z.left
	TRANSPLANT(T, z, z.left)

/* 
 * 只有当删除的结点是黑色时才会引起失衡
 * 1. 因为在只有一个孩子的情况下，若删除的是红色结点不会破坏性质4和性质5
 *    而删除黑色结点会影响黑高从而破坏性质5
 * 2. 在有两个孩子的情况下
 *    我们是先与后继节点交换位置，删除时实际删的是原本后继节点的那个位置，也是只有一个孩子，与上面的情况相同
 */
if original-color == BLACK
    // FIX-UP 是修复平衡的方法，将在后面介绍
    FIX-UP(T, x)

图中 z 代表要删除的结点，灰色结点代表实际被删除的结点，x 是灰色结点的唯一孩子。当前情况下刚好重合。

读起来怪怪的，解释一下：

BST 的删除，例如要删除结点 z，如果 z 有两个孩子，那么删除 z 之后这棵子树就缺少了根节点，这时候就得找到子树中的后继节点来替换 z，否则这棵子树就没有根节点了。这种情况下，从逻辑上讲，我们删除的确实是结点 z，但是从树的物理结构上来看，我们删除的其实是那个后继结点，至于 z，相当于只是值变动了

而上图中，或者说现在我们讨论的情况，是 z 只有一个孩子，那么自然不存在缺少根节点的情况了，直接让那个唯一的孩子移动过来就行。所以灰色结点与 z 重合

删除伴随着移动，而移动就容易导致失衡（黑高变动，或者两个红色结点相互连接）

所以 x 指向的是实际被删除的结点的孩子结点

所幸的是，不管是 case 2 还是 case 3，实际删除的结点都只有一个孩子结点

Case 2 根据情况，可能是左孩子或右孩子作为 x

Case 3 只可能是右孩子

4.1.2 Case 3 有两个孩子

有两个孩子，我们就得去找要删除的结点的后继结点进行替换

这种情况下要删除的结点 z 就不一定会和实际删除的结点重合了，注意了是不一定

下面分 一般情况 和 特殊情况 分别探讨

一般情况

删除后

删除的过程比较抽象。

我们找到 z 的后继节点 y 来替换 z，这时候 z 的本体已经被删除了。

而用 y 替换 z 的这一过程，在树的结构中，删除的是 y 原本位置的结点。

那么此时 x 指向结点 5

y 的移动会导致 x 失去父亲

所以在 y 被移走（“删除”）前，我们需要将 x 与 y 的父节点 4 连起来。或者说，这里是用结点 x 替换 结点 y

然后才能用结点 y 替换结点 z

特殊情况

当后继节点 y 就是结点 z 的右孩子时，只要用 y 替换 z 即可，x 依旧是 y 的孩子

伪代码

y = TREE-MINIMUN(z.right) // TREE-MINIMUN 用来寻找子树中最小的结点，应该不难实现

/*
 * original-color 记录 y 原本的颜色
 * 因为 y 去替换 z 了，所以 y 被染成 z 的颜色
 * 而我们在树的整体结构中删除的是 y 原本的位置
 * 所以我们要记录那一时刻 y 的颜色
 */
original-color = y.color
y.color = z.color

// 为什么 x 是 y 的右孩子，通过上面几张图应该说明了
x = y.right

// 如果 p 不是 z 的右孩子，才需要处理 x 失去父亲的问题
if y.p ≠ z
    /*
    * 用后继节点 y 的唯一的孩子替换后继结点 y
    * 因为 y 被拿去替换 z 了
    * 当然 y.right 就是 x，这里这样写是为了更高的可读性
    */
	TRANPLANT(T, y, y.right)
	
	// 替换后，y 失去了原本的右孩子，并即将获得 z 的右孩子
    y.right = z.right
    y.right.p = y


// 用 y 替换 z
TRANSPLANT(T, z, y)

// 替换后 y 就拥有了 z 原本的左孩子
y.left = z.left
y.left.p = y

if original-color == BLACK
	FIX-UP(T, x)

4.1.3 合并

y = z
original-color = y.color
if z.left == T.nil
	x = z.right
	TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
	x = z.left
	TRANSPLANT(T, z, z.left)
else
	y = TREE-MINIMUM(z.right)
	original-color = y.color
	y.color = z.color
	x = y.right
	if y.p ≠ z
        TRANPLANT(T, y, y.right)
        y.right = z.right
        y.right.p = y
    TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y
if original-color == BLACK
	FIX-UP(T, x)

删除部分到这里就结束了。目前，我们成功地删除了结点 z ，同时用 x 标记了可能失衡的子树的根节点

下一步就是修复平衡了

4.2 平衡修复

4.2.0 理论

理论部分

上面的伪代码中的注释应该写了，当 original-color 为黑色才会破坏平衡。

细想一下也能明白，删除红色结点既不会破坏性质4，也不会破坏性质5

确定了 original-color 为黑色后，就可以明确的声明：性质5被破坏了，因为黑高少了 1

而性质4是否被破坏取决于结点 x 的颜色和其父节点的颜色是否均为红色

黑高缺失 1，这个概念比较抽象，在图上不好表示，所以我们再次给 x 结点染上一层黑色，这可不是张口就来的，请看下面的解释

1. 若 x 结点原本为红色，那么这次染黑不仅合法地修复了性质5，还顺带解决了可能存在的性质4问题。一举两得，属实是妙啊

   这也就是删除中最简单的情况，x 为红色，直接将其染黑，平衡就被修复了

   如果只有这种情况就好了，没有后面这么多内容了，可惜，后面的很复杂

2. 若 x 结点原本为黑色，那么这次染黑又给他镀上去了一层黑皮，我们在这里定义其为“双黑结点”

   

   双黑结点拥有值为 2 的黑色，这样，我们也能成功修复性质5，然而，红黑树中并不存在所谓的“双黑结点”

   所以我们的问题：从“黑高缺失 1，变成了”结点 x 多了一层黑皮“

黑 + 黑 = 双黑，黑 + 红 = 黑

那么我们现在的目标，就是找机会弄一个红色结点过来，把黑皮套给它，让它变为黑色结点

思考一个问题，如果 x 的父节点是红的，能把它染黑吗，当然不能，把它染黑，那不是另外一边的子树也被影响了黑高？

✨下面这句话非常重要

所以我们要从另外一边的子树偷一个红色结点放入 x 与 x 的父节点中间，而父节点的颜色已经不在乎了，我们不能去动它

学过了之前的插入平衡修复，应该对红黑树的旋转不这么陌生了吧，我们肯定有办法在不破坏平衡的前提下，转一个红色结点过来

当然还有种特殊情况：X 是根节点。

既然是根节点，不管它有几层皮，我们都给它去了也不会影响平衡。

所以这是一个特例

那么根据上面这两种情况，可以写出简单的伪代码

while x ≠ T.root and x.color == BLACK
	...
	找机会偷个红色结点来修复平衡，最终 x 会指向红色结点或根节点
	...
x.color = BLACK

你以为原理结束了？不，还有很多呢。

下面是 X 为黑的细致原理，结合图文更好理解

需要提醒的是，从这一节开始，我们不能再忽略叶子结点 NIL

在这里，规定：

• x 为失衡的“双黑结点”
• v 为实际被删除的结点，
• p 为 v 的父节点，也可以说是删除 v 后，x 的父节点
• s 为 v 的兄弟结点，也可以说是删除 v 后，x 的兄弟结点

---

如下图所示，虽然我全画了黑色，但是能确定为黑色的只有 X

V 是要删除的结点 z 的后继结点，所以 V 的左孩子不可能是内部结点，而右孩子有可能是内部结点。我们选择右孩子。

X 是内部结点的情况不用我画了，下图画出 X 是 NIL 的情况，为了体现 NIL 的重要性

注：方块代表 NIL。另外，不要被图里的表象给骗了，虽然看起来删的是 v，但是实际上删的是 z，原本的 v 已经替换了 z

可以很清楚的看到，成为双黑结点的并不一定是内部结点，NIL 不再可以被忽视

分类讨论

首先，失衡是从 X 结点开始的，所以 X 的子树（或者说它的孩子）是怎样已经无关紧要了，它们本来就是相对平衡的，后面的图中我将直接省略

剩下需要讨论的只有，结点 x、p、s 及 s 的子树的颜色情况

---

我们唯一能确定的颜色就是 X 为双黑，因为我们就是在讨论这种情况

而上面的“理论部分”我提到：这棵子树的根节点 p 的颜色我们不在乎

---

X 为双黑意味着，在删除操作之前，这里的黑高起码就是 2 了，既然之前是符合性质5的，那么另一边的黑高也起码是 2。

黑高至少为 2，意味着结点 s 一定是内部结点，而 s 的孩子结点可能全是 NIL，也可能是两个内部结点。不过关于 s 的孩子是什么结点已经不重要了，因为在这一节中 NIL 也一视同仁，我们只关注颜色。

---

所以只剩下三个结点的颜色需要讨论：结点 s 及其两个孩子

1. 全黑
2. s 为红色（两个孩子只能为黑色）
3. s 为黑色，孩子有红色（应该能猜到吧，左红还是右红又得分开讨论）

下面我将分 3 个小节介绍这三种情况，为了节省篇幅，我只介绍 x 为 p 的左孩子的情况，剩下对称的另一种情况请自行探讨

4.2.1 全黑

全黑不包括结点 p，上面提到过，p 的颜色不是我们要关心的，所以全黑有两种情况：

1. 
2. 

全黑怎么办，兄弟那边没有红色结点可以偷了，所以我们要想办法往上走，偷别人的去。

这和插入中的 case 1 一样，是一个递归的过程，所以我放在第一个讲，因为你只能递归上去，不能做复杂处理，容易理解

既然我们要往上找，那么双黑的这层黑皮也得传递过去，可传递给 p 之后，左边没有问题，右边的黑高变化了怎么办？

显而易见，将 s 染红

因为这一部分是全黑的，不会破坏性质4，同时又巧妙的把黑高降下来了

看图前为防止产生歧义先声明一点：图中的 NIL 只是特例，因为我们只需要关注他们的颜色，所以我把可能是 NIL 的结点标成了 NIL，不代表它们一定是 NIL

1. p 为黑

   

   只要新的 x、s、s 的两个孩子是全黑的就继续递归上去

2. p 为红

   

   思考一下，这时候平衡了吗？

   我刻意没有直接将 p 涂黑，你应该想到了，这时候已经平衡了。

   所以递归的截止条件之一就是 p 为红，当然在退出递归时要记得将它染黑。这在之前的伪代码中已经存在了，不需要我们重新编写

当然，我不涂黑 p 的原因还有一个，在代码实现中可没有“双黑”或者“黑红”，所以我们的递归判断条件仅仅是看 x 是黑色还是红色

下面给出伪代码

// 外层循环条件这样写的原因在 4.2.0 理论中已经有了
while x ≠ T.root and x.color == BLACK
	
	// 只给出一半代码，剩下一半是对称的
	if x == x.p.left
	
		s = x.p.right
		// 三点全黑
		if s.color == BLACK and s.left.color = BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
	
		...
		找机会偷个红色结点来修复平衡，最终 x 会指向红色结点
		...
	else （刚好对称，只是将 left 与 right 互换而已）
	
x.color = BLACK

4.2.2 s 为黑色且拥有红色孩子

在这一小节中，我们定义，s 的红色孩子为 r

同时，不确定颜色的结点以白色表示，虽然图中可能有多个白色结点，但是它们的颜色并不一定相同，白色仅表示颜色不确定

根据红色孩子是左孩子还是右孩子，又可以分为两种情况

4.2.2.1 s 的右孩子是红色

终于出现 p 以外的红色结点了，这边建议直接偷。

当然是偷不是抢，不能直接暴力地把 r 移过去，得通过旋转加染色，不知不觉中将 r 染黑修复平衡，那才叫偷

结点 10 与结点 11 不确定颜色，但是无论他们是什么颜色都无所谓，最终都能平衡

由于结点 r 是红色结点，对于它的子树来说，他们的简单路径相当于是 p白->黑

同样，结点 11 的简单路径也是 p白->黑

高端操作来了，既然红色不参与黑高计算，那么如果我们把 p 和 s 的颜色往红色那边拉过去（或者理解为红色结点冒泡上去，每一次冒泡，相当于和父节点互换颜色），再把结点 p 变成红色，也不会影响 r 的子树黑高计算，顶多影响了结点 11 和结点 x 的黑高

这是唯一能把红色移动过去的方法，至于结点 11 和结点 x 的黑高？抱歉，老实待着吧，先偷个红过来再说

对于 γ 和 ζ，简单路径依旧是 p白->黑（s 的颜色现在是 p白了）

好了，接下来该思考结点11 和结点 x 的黑高问题了，或者说它们的路径怎么恢复

想一想，我们偷个红孩儿过来是干什么？还不是为了把 X 的黑皮给他套上，但之前又分析过一般情况下 P 不能直接染黑，容易影响右边的黑高。

那就转呗，让结点 s 当这棵子树的根节点。转完就可以把 p 染黑了

发现了吗，树平衡了，是不是很突然。

实际上一点都不突然

在一开始，结点 11 的简单路径是 p白->黑

而 s 复制了 p 的颜色，在旋转之后我们又把 p 染黑（也就是变成了 s 的颜色）

所以这时候结点 11 的简单路径又等于 color(p) + color(s) = p白->黑

同时，双黑结点 X 也成功把黑皮套到了偷来的红色结点上面，一切都大功告成。

至于 p白 和 11白 究竟是什么颜色并不重要，我们已经证明了他们的简单路径前后一致。

写成伪代码是这样：

s = x.p.right
if s.color == BLACK and s.right.color == RED
	s.color = x.p.color // s 变成 p 的颜色
	s.right.color = BLACK // r 变成 s 的颜色，s 一开始就是黑色
	x.p.color = BLACK // 在上面文字部分其实 p 改变了两次颜色，但是最终都会变成 s 的颜色，也就是黑色
	RR(T, x.p)

4.2.2.2 s 的左孩子是红色

经典的 RL 形状，不用猜都知道这次我们要用 RL 旋转了。但是怎么记呢，怎么理解呢？

如果你熟悉 AVL 的旋转的话，应该知道不管是 RL 还是 LR，在旋转过程中都会将一个结点插入两个结点之中

现在 r 是红色结点，将它插入 p 和 s 之中会影响平衡吗？试试就知道了

我们对 RL 旋转进行拆分，先进行一次 LL

当然转完之后 r 应该改名变成 s（图中还没改）， 毕竟我们定义的 s 就是 x 的兄弟结点，后面的伪代码就是用 s 表示这时候的结点 11 的。

现在来看看子树的相对位置变化：

• 对于子树 α，简单路径变化了，从 p白->黑 变成了 p白
• 而对于其他结点或者子树，没有产生任何变化

阅读上面这两句话，同时结合图片，有没有发现：

这相当于是 4.2.2.1 中，右边的红色的结点进行了第一次冒泡。所以我们与 4.2.2.1 可以共用一部分代码

接下来应该怎么做，也不难想到了，那就是继续让红色结点冒一次泡上去，然后进行 RR 旋转：

1. 将 r 染成 p 的颜色
2. 将 p 染成 s 的黑色
3. RR(p)

如果你觉得这样太快了，可以将上面 3 步进行一个简单的拆分：

1. 将 r 与 p 颜色互换，r 变成 p白，p 变成红
2. RR(p)，这时候根节点还是 p白，而红色结点被偷到左边，同时整棵子树状态与最初相同
3. 染黑红色结点，修复平衡

写成伪代码是这样：

s = x.p.right
if s == BLACK and s.left == RED
	LL(T, s)
	s = x.p.right // 实际上就是 s = r，但是我们的代码没有 r 的指针，所以要从 x 寻找 r

// 下面就是与 4.2.2.1 一样的代码
// 上图为了好理解没有修改结点 11 的名称，实际上应该已经是 s 了
s.color = x.p.color
x.p.color = BLACK
s.right.color = BLACK // 这一步在 4.2.2.2中没有作用，因为本来就是黑的
RR(T, x.p)

4.2.2.3 合并

上面两种情况都有共用的代码，所以可以合并为：

s = x.p.right
if s.right.color == BLACK // 这样判断是为了在左右都是红色时优先判断为右边为红，可以少执行一点代码
	LL(T, s)
	s = x.p.right
s.color = x.p.color
x.p.color = BLACK
s.right.color = BLACK // 这一步在 4.2.2.2中没有作用，因为本来就是黑的
RR(T, x.p)

结合 4.2.1 的递归，我们可以写出一段较为完整的伪代码

while x ≠ T.root and x.color == BLACK
	if x == x.p.left
		s = x.p.right
		
		if s.left.color == BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
		else
			if s.right.color == BLACK
                LL(T, s)
                s = x.p.right
            s.color = x.p.color
            x.p.color = BLACK
            s.right.color = BLACK
            RR(T, x.p)
            x = T.root // 因为 4.2.2 一定能修复平衡，这里是为了退出循环
	else （刚好对称，只是将 left 与 right 互换而已）
x.color = BLACK

4.2.3 s 为红色

s 为红色的情况，根据性质4，p 一定为黑色

那么这时候 x、p、s、s 的两个孩子，这 5 个结点的颜色全部确定

这时候还能偷红吗，不行了吧。把 s 和 p 互换颜色转一下？还是不行。如果不信的话可以在草稿纸上试试。

当前这种情况，我们可以通过对 p 进行一次 RR 左旋，加上几步染色操作，将其变为 4.2.1 全黑 或者 4.2.2 s 为黑色且拥有红色孩子

1. 将结点 s 染黑
2. 将结点 p 染红
3. RR(p)

这种情况说实话没什么特别好记或者容易理解的方法，起码我是想不到。

不过你可以看做 s 和其左子树一起搬迁到 p 的左子树。

因为 s 是红色结点，不管放在 p 的左边还是右边，都不影响黑高，再加上这种情况下所有结点的颜色确定，也不会破坏性质4

当然咯，说是说搬迁，实际上是旋转加染色，看图就知道结点的相对位置是变动了的

伪代码如下：

s = x.p.right
if s.color == RED
	// 这种情况下颜色是确定的
	s.color = BLACK
	x.p.color = RED
	// 旋转
	RR(T, x.p)
	// s 需要重新定位了
	s = x.p.right

4.2.4 合并

while x ≠ T.root and x.color == BLACK
	if x == x.p.left
		s = x.p.right
		if s.color = RED
			s.color = BLACK
			x.p.color = RED
			RR(T, x.p)
			s = x.p.right
		if s.left.color == BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
		else 
			if s.right.color == BLACK
                LL(T, s)
                s = x.p.right
            s.color = x.p.color
            x.p.color = BLACK
            s.right.color = BLACK
            RR(T, x.p)
            x = T.root
	else （刚好对称，只是将 left 与 right 互换而已）
x.color = BLACK

乞讨环节

能点文章下方的打赏按钮给我个 5 毛钱吗

5. 手撕红黑树

红黑树 (gitee.com)

6. 参考文章

• 《算法导论》第三版（机械工业出版社）
• 30张图带你彻底理解红黑树
• 图解：红黑树删除篇（一文读懂）