算法和数据结构: 红黑树
上篇文章 《重温数据结构：二叉排序树的查找、插入、删除》 我们提到，二叉排序树的性能取决于二叉树的层数：
- 最好的情况是
O(logn)，存在于完全二叉排序树情况下，其访问性能近似于折半查找； - 最差时候会是
O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行（见下图 b）。
1
2
3
4
5
6
7
8
45 12
/ \ \
24 55 24
/ \ / \ \
12 37 53 60 28
/ \ \ \
28 40 70 37
(a) (b)
为了改变排序二叉树存在的不足，Rudolf Bayer 在 1972 年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
本文介绍了红黑树的基本性质和基本操作。
定义
红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。
由于 TreeMap 就是由红黑树实现的，因此本文将使用 TreeMap 的相关操作的代码进行分析、论证。
黑色高度 : 从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。
特性
红黑树在原有的二叉查找树基础上增加了如下几个要求：
- Every node is either red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
中文意思是：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
注意：
-
性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
-
性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。 因此若给定黑色节点的个数
N，最短路径的情况是连续的N个黑色，树的高度为N - 1;最长路径的情况为节点红黑相间，树的高度为2(N - 1)。 -
性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。
红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。
左旋右旋
红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。
比如 X 左旋(右图转成左图)的结果，是让在 Y 左子树的黑色节点跑到 X 右子树去。
我们以 Java 集合框架中的 TreeMap 中的代码来看下左右旋的具体操作方法：
指定节点 x 的左旋 (右图转成左图)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//这里 p 代表 x
private void rotateLeft(Entry p) {
if (p != null) {
Entry r = p.right; // p 是上图中的 x，r 就是 y
p.right = r.left; // 左旋后，x 的右子树变成了 y 的左子树 β
if (r.left != null)
r.left.parent = p; //β 确认父亲为 x
r.parent = p.parent; //y 取代 x 的第一步：认 x 的父亲为爹
if (p.parent == null) //要是 x 没有父亲，那 y 就是最老的根节点
root = r;
else if (p.parent.left == p) //如果 x 有父亲并且是它父亲的左孩子，x 的父亲现在认 y 为左孩子，不要 x 了
p.parent.left = r;
else //如果 x 是父亲的右孩子，父亲就认 y 为右孩子，抛弃 x
p.parent.right = r;
r.left = p; //y 逆袭成功，以前的爸爸 x 现在成了它的左孩子
p.parent = r;
}
}
可以看到，x 节点的左旋就是把 x 变成 右孩子 y 的左孩子，同时把 y 的左孩子送给 x 当右子树。
简单点记就是：左旋把右子树里的一个节点（上图 β）移动到了左子树。
指定节点 y 的右旋（左图转成右图）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void rotateRight(Entry p) {
if (p != null) {
Entry l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
同理，y 节点的右旋就是把 y 变成 左孩子 x 的右孩子，同时把 x 的右孩子送给 x 当左子树。
简单点记就是：右旋把左子树里的一个节点（上图 β）移动到了右子树。
了解左旋、右旋的方法及意义后，就可以了解红黑树的主要操作：插入、删除。
平衡插入
红黑树的插入主要分两步：
- 首先和二叉查找树的插入一样，查找、插入
- 然后调整结构，保证满足红黑树状态
- 对结点进行重新着色
- 对树进行相关的旋转操作
红黑树的插入在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。
二叉查找树的插入
上篇文章 介绍过，二叉查找树的就是一个二分查找，找到合适的位置就放进去。
调整红黑树结构
红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。
同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。
因此我们需要在插入黑色节点后进行结构调整，保证红黑树始终满足这 5 条特征。
调整思想
前面说了，插入一个节点后要担心违反特征 4 和 5，数学里最常用的一个解题技巧就是把多个未知数化解成一个未知数。我们这里采用同样的技巧，把插入的节点直接染成红色，这样就不会影响特征 5，只要专心调整满足特征 4 就好了。这样比同时满足 4、5 要简单一些。
染成红色后，我们只要关心父节点是否为红，如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。
注：插入后我们主要关注插入节点的父亲节点的位置，而父亲节点位于左子树或者右子树的操作是相对称的，这里我们只介绍一种，即插入位置的父亲节点为左子树。
插入、染红后的调整有 2 种情况：
情况1.父亲节点和叔叔节点都是红色
假设插入的是节点 N，这时父亲节点 P 和叔叔节点 U 都是红色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，这时不管 N 是 P 的左孩子还是右孩子，只要同时把 P 和 U 染成黑色，G 染成红色即可。这样这个子树左右两边黑色个数一致，也满足特征 4。注：此处如果 G 不变为红色，则 G 的后代节点都将增加一个黑色节点，违反了特征 5,因为 G 的兄弟节点中黑色节点没有增加。
但是这样改变后 G 染成红色，G 的父亲如果是红色岂不是又违反特征 4 了？ 这个问题和我们插入、染红后一致，因此需要以 爷爷节点 G 为新的调整节点，再次进行调整操作，以此循环，直到父亲节点不是红的，就没有问题了。
情况2.父亲节点为红色，叔叔节点为黑色
假设插入的是节点 N，这时父亲节点 P 是红色，叔叔节点 U 是黑色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，但是直接把父亲节点 P 涂成黑色也不行，这条路径多了个黑色节点。怎么办呢？
既然改变不了你，那我们就此别过吧，我换一个更适合我的！
我们怎么把 P 弄走呢？看来看去，还是右旋最合适，通过把 爷爷节点 G 右旋，P 变成了这个子树的根节点，G 变成了 P 的右子树。右旋后 G 跑到了右子树上，这时把 P 变成黑的，多了一个黑节点，再把 G 变成红的，就平衡了！
上面讲的是插入节点 N 在父亲节点 P 的左孩子位置，如果 N 是 P 的右孩子，就需要多进行一次左旋，把情况化解成上述情况。
N 位于 P 的右孩子位置，将 P 左旋，就化解成上述情况了。
根据 TreeMap 的代码来验证这个过程：
下面是 TreeMap 在插入后进行调整的代码，可以看出来跟我们分析的一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private void fixAfterInsertion(Entry x) {
x.color = RED; //直接染成红色，少点麻烦
//这里分析的都是父亲节点为红色的情况，不是红色就不用调整了
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 插入节点 x 的父亲节点位于左孩子
Entry y = rightOf(parentOf(parentOf(x))); // y 是 x 的叔叔节点
if (colorOf(y) == RED) { //如果 y 也是红色，只要把父亲节点和 y 都变成黑色，爷爷节点变成红的，就 Ok 了
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //如果叔叔节点 y 不是红色，就需要右旋，让父亲节点变成根节点，爷爷节点去右子树去，然后把父亲节点变成黑色、爷爷节点变成红色
//特殊情况：x 是父亲节点的右孩子，需要对父亲节点进行左旋，把 x 移动到左子树
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else { //和上面对称的操作
Entry y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
平衡删除
红黑树的插入平衡需要好好理解下，如果前面没有理解，删除后的调整平衡更加难懂，前方高能，请注意！
红黑树的删除也是分两步：
- 二叉查找树的删除
- 结构调整
二叉查找树的删除
上篇文章 介绍了，二叉查找树的删除分三种情况：
- 要删除的节点正好是叶子节点，直接删除就 OK 了；
- 只有左孩子或者右孩子，直接把这个孩子上移放到要删除的位置就好了；
- 有两个孩子，就需要选一个合适的孩子节点作为新的根节点，该节点称为 继承节点。
三种情况的图片示意：
- 要删除的节点正好是叶子节点，直接删除就 OK 了
1
2
3
4
5
G G
| |
P P
\
C
- 有左孩子或者右孩子，直接把这个孩子上移放到要删除的位置就好了
1
2
3
4
5
P P
| |
N C
/
C
- 有两个孩子，就需要选一个合适的孩子节点作为新的根节点，该节点称为 继承节点(左子树的最大节点，或右子树的最小节点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
P
|
N <--- delete
/ \
L R
/ \ / \
A B C D
P P
| |
B 或 C
/ \ / \
L R L R
/ / \ / \ \
A C D A B D
删除后的结构调整
根据红黑树的第 5 个特性：
- 如果当前待删除节点是红色的，它被删除之后对当前树的特性不会造成任何破坏影响。
- 而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结构满足要求。
这里研究的是删除黑色节点的情况。
调整思想
为了保证删除节点父亲节点左右两边黑色节点数一致，需要重点关注父亲节点没删除的那一边节点是不是黑色。如果删除后父亲节点另一边比删除的一边黑色节点多，就要想办法搞到平衡，具体的平衡方法有如下几种方法：
- 把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少一个黑色
- 或者把另一边多的黑色节点转过来一个
删除节点在父亲节点的左子树还是右子树，调整方式都是对称的，这里以当前节点为父节点的左孩子为例进行分析。
调整方法
我们约定 X 为待删除的结点，P 为 X 的父结点，C 为 X 的孩子结点，B 为 X 的兄弟结点，BL 为 B 的左孩子结点，BR 为 B 的右孩子结点。
-
如果待删除结点
X是一个红色结点，则直接删除即可，不会违反定义。 -
如果待删除结点
X是一个黑色结点，且其孩子结点C是红色的，那么只需要将X替换成C，同时将C由红变黑即可。 -
如果需要删除的结点
X是黑色的，同时它的孩子结点C也是黑色的，这种情况需要进一步分场景讨论。
对于第三种情况我们首先将 X 替换成 C，并重命名其为 N，N 沿用 X 对于长辈和晚辈的称呼，需要清楚这里实际删除的是 X 结点，并且删除之后通过 N 的路径长度减 1。
场景1: N 是新的根
这种情况比较简单，不需要再做任何调整。
场景2： N 的父结点、兄弟结点 B，以及 B 的孩子结点均为黑色
如下图，此时只需要将 B 变为红色即可，这样所有通过 B 的路径减 1，与所有通过 N 的路径正好一致，但是此时通过 P 的路径都减少了 1 个长度，所以需要向上递归对结点 P 继续判定。
场景3: N 的兄弟结点 B 为红色，其余结点均为黑色
如下图，此时需要执行一次左旋转，然后将 P 和 B 的颜色互换。调整前后各个结点的路径没有变化，但是因为之前经过 N 的路径长度少了一个单位，所以此时仍然不满足定义，需要按照后面的场景继续调整。
场景4: N 的父结点 P 为红色，兄弟结点 B，以及 B 的孩子结点均为黑色
如下图，此时我们只需要简单互换 P 和 B 的颜色，这种情况下对于不通过 N 的结点路径没有影响，但是却让通过 N 的结点路径加 1，正好弥补之前删除操作所带来的损失。
场景5: N 的兄弟结点 B 为黑色，B 的左孩子为红色，B 的右孩子为黑色
如下图，此时我们需要先执行一次右旋转操作，然后互换 B 与 BL 的颜色，操作之后通过所有结点的路径长度并没有发生变化，却让 N 有了一个新的黑色兄弟结点，并且该兄弟结点的右孩子为红色，从而可以按照接下去介绍的一种场景继续调整。
注：白色结点表示该结点既可以是黑色也可以是红色，后续图示亦是如此。
场景6： N 的兄弟结点 B 为黑色，B 的右孩子为红色
如下图，此时我们需要先执行一次左旋转，并互换 P 和 B 的颜色，同时将 B 的右孩子结点变为黑色。变更之后，除 N 外其余结点的路径长度未发生变化，但是经过 N 的路径上却增加了一个黑色结点，这刚好弥补之前删除操作所带来的损失。
调整步骤
调整的4种情况:
- 情况1：当前节点和它的父节点是黑色的，而它的兄弟节点是红色的
这种情况下既然它的兄弟节点是红色的，从红黑树的属性来看，它的兄弟节点必然有两个黑色的子节点。这里就通过节点 x 的父节点左旋，然后父节点 B 颜色变成红色，而原来的兄弟节点 D 变成黑色。这样我们就将树转变成第二种情形中的某一种情况。在做后续变化前，这棵树这么的变化还是保持着原来的平衡。
- 情况2： 1） 当前节点的父节点为红色，而它的兄弟节点，包括兄弟节点的所有子节点都是黑色。
在这种情况下，我们将它的兄弟节点设置为红色，然后 x 节点指向它的父节点。这里有个比较难以理解的地方，就是为什么我这么一变之后它就平衡了呢？因为我们假定 A 节点是要调整的节点一路调整过来的。因为原来那个要调整的节点为黑色，它一旦被删除就路径上的黑色节点少了 1.所以这里 A 所在的路径都是黑色节点少 1.这里将 A 的兄弟节点变成红色后，从它的父节点到下面的所有路径就都统一少了1.保证最后又都平衡了。
当然，大家还会有一个担忧，就是当前调整的毕竟只是一棵树中间的字数，这里头的节点 B 可能还有父节点，这么一直往上到根节点。你这么一棵字数少了一个黑色节点，要保证整理合格还是不够的。这里在代码里有了一个保证。假设这里 B 已经是红色的了。那么代码里那个循环块就跳出来了，最后的部分还是会对 B 节点，也就是 x 所指向的这个节点置成黑色。这样保证前面亏的那一个黑色节点就补回来了。
2） 当前节点的父节点为黑色，而它的兄弟节点，包括兄弟节点的所有子节点都是黑色。
这种情况和前面比较类似。如果接着前面的讨论来，在做了那个将兄弟节点置成红色的操作之后，从父节点 B 开始的所有子节点都少了1.那么这里从代码中间看的话，由于 x 指向了父节点，仍然是黑色。则这个时候以父节点 B 作为基准的子树下面都少了黑节点1. 我们就接着以这么一种情况向上面推进。
- 情况3： 当前节点的父节点为红色，而它的兄弟节点是黑色，同时兄弟节点有一个节点是红色。
这里所做的操作就是先将兄弟节点做一个右旋操作，转变成第4种情况。当然，前面的前提是 B 为红色，在 B 为黑色的情况下也可以同样的处理。
- 情况4： 在当前兄弟节点的右子节点是红色的情况下。
这里是一种比较理想的处理情况，我们将父节点做一个左旋操作，同时将父节点 B 变成黑色，而将原来的兄弟节点 D 变成红色，并将 D 的右子节点变成黑色。这样保证了新的子树中间根节点到各叶子节点的路径依然是平衡的。大家看到这里也许会觉得有点奇怪，为什么这一步调整结束后就直接 x = T.root 了呢？也就是说我们一走完这个就可以把 x 直接跳到根节点，其他的都不需要看了。这是因为我们前面的一个前提，A 节点向上所在的路径都是黑色节点少了一个的，这里我们以调整之后相当于给它增加了一个黑色节点，同时对其他子树的节点没有任何变化。相当于我内部已经给它补偿上来了。所以后续就不需要再往上去调整。
前面讨论的这4种情况是在当前节点是父节点的左子节点的条件下进行的。如果当前节点是父节点的右子节点，则可以对应的做对称的操作处理，过程也是一样的。
根据 TreeMap 的代码来验证这个过程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
private void fixAfterDeletion(Entry x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry sib = rightOf(parentOf(x));
//左旋，把黑色节点移到左边一个
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { //处理的节点在 右边，相同逻辑，只不过旋转的方向相反
Entry sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
当调整的节点属于父亲节点的左子树时，调整方法对应的流程图如下：
当调整的节点属于父亲节点的右子树时，调整方法也类似，旋转的方向相对称。
这里列出删除后调整的全部逻辑流程图（右键新窗口打开图片更清晰）：
总结
红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。
红黑树的插入、删除调整逻辑比较复杂，但最终目的是满足红黑树的 5 个特性，尤其是 4 和 5。
在插入调整时为了简化操作我们直接把插入的节点涂成红色，这样只要保证插入节点的父节点不是红色就可以了。
而在删除后的调整中，针对删除黑色节点，所在子树缺少一个节点，需要进行弥补或者对别人造成一个黑色节点的伤害。具体调整方法取决于兄弟节点所在子树的情况。
红黑树的插入、删除在树形数据结构中算比较复杂的，理解起来比较难，但只要记住，红黑树有其特殊的平衡规则，而我们为了维持平衡，根据邻树的状况进行旋转或者涂色。
红黑树这么难理解，必定有其过人之处。它的有序、快速特性在很多场景下都有用到，比如 Java 集合框架的 TreeMap, TreeSet 等。
