二叉树06.从2-3-4树到红黑树

作者：刘涛 2022-02-18 V1.0.0

1. 前言

红黑树是一种自平衡二叉查找树（Self-balancing binary search tree）。
如前文所述，根据红黑树的定义去理解其设计思想是非常困难的，但借助 B 树我们却可以更好地理解它，因为红黑树本就是由4阶B树推导而来。
全文较长，但为了完整的阅读体验，所以没有拆分为多篇文章，读者可以自行挑选阅读感兴趣的章节。

代码仓库：https://github.com/patricklaux/perfect-code
系列文章
(1) 深度优先遍历之递归和非递归遍历
(2) 深度优先遍历之 Morris 遍历
(3) 一种无需队列的层序遍历算法 IDDFS
(4) 深度分析AVL树的实现与优化
(5) B树详解与实现
(6) 从2-3-4树到红黑树【本文】

2. 由来

(1) 1972 年，Rudolf Bayer 提出了 “symmetric binary B-tree”，这是B 树的 4 阶情形，也就是 2-3-4树（或称为 2-4 树）[1]。
(2) 1978 年，Leonidas J. Guibas 和 Robert Sedgewick 从 “symmetric binary B-tree” 推导出红黑树[2]。
(3) 1993 年，Arne Andersson 引入 “right leaning tree(右倾树)” 的概念来简化插入和删除操作[3]。
(4) 1999 年，Chris Okasaki 展示了如何使插入操作成为纯函数，只需处理 4 种失衡类型和 1 种默认平衡类型[4]。
(5) 2001 年，Cormen 等人将原算法的 8 个失衡类型减少为 6 个失衡类型[5]。
(6) 2008 年，Sedgewick 根据 Andersson 的思想，提出了 “Left leaning red black tree(左倾红黑树)”，这是 2-3 树的等价转换[6]。

因此，红黑树现在主要有两个流行版本：
版本一：根据 4 阶 B 树( 2-3-4 树)转换而来的红黑树；
版本二：根据 3 阶 B 树( 2-3 树)转换而来的左倾红黑树。

因为 Java 中的 TreeMap 是版本一的实现，所以我将介绍版本一。
不过，道理是相通的，理解了版本一，也就理解了版本二，版本二只是通过增加 “红链接均为左链接” 这一性质来简化实现而已。

另外，Java 中的 TreeMap 在 JDK1.2 时就已存在(1998年)，因此插入和删除的实现其实并不那么简洁优美。
所以，我根据《算法导论.第3版[7]》又重新实现了一遍，并且再稍稍优化了部分逻辑，使之更加清晰可读。

3. 性质与概念

性质

红黑树是一棵二叉查找树，有五个基本性质：
(1) 节点要么是红色，要么是黑色；
(2) 根节点是黑色的；
(3) 每个外部节点(nil 节点)是黑色的；
(4) 每个红色节点的两个子节点都是黑色的；
(5) 从任一个节点到其外部节点的所有路径包含相同数量的黑色节点。

概念

外部节点
外部节点没有键和子节点，即图3.1中的NIL节点（见参考资料[1]）。
红黑树中通常用空指针或一个特殊的哨兵节点来指代。

内部节点
内部节点包含一个键和两个子节点，这两个子节点可以是外部节点（见参考资料[1]）。

叶子节点
叶子节点指的是包含键的最底层节点。
《算法导论.第3版[7]》中关于红黑树的描述：叶子节点即外部节点。
这里与前文 B 树介绍中的概念保持一致：叶子节点并非是外部节点。

高度
红黑树的高度最大为 \(2log_2(n+1) \)。
性质4 和 5 限制了红黑树高度的最大值，因此这两点是关键性质，后面介绍的插入和删除后的修复，几乎都是为了维护这两点。
我们先理解红黑树及相关操作，最后再来证明这个命题。

黑高(black height)
黑树的黑高是指从根到外部节点的任一路径上的黑色节点的数量。
根据性质 5 ，根到任一外部节点的路径上的黑色节点数都必定是相等的。
如图3.1，以 H 为根的红黑树其黑高为 4，以 P 为根的子树的黑高为3，以 T 为根的子树的黑高也为3……

黑深(black depth)
一个节点的黑色深度是指从根到该节点的黑色节点的数量（即其黑色祖先数量）。
如图3.1，H 的黑深为0，P 的黑深为1，L 的黑深为2，W的黑深为3，Z的黑深为4，所有外部节点的黑深均为4。

红色违规
违反性质4。

黑色违规
违反性质5。

4. 等价转换

4-节点：4 个孩子 3 个键；3-节点：3 个孩子 2 个键；2-节点：2 个孩子 1 个键。

5. 节点定义

class Node<K, V> {
    K key;  // 键
    V val;  // 值
​
    Node<K, V> left;    // 左孩子
    Node<K, V> right;   // 右孩子
    Node<K, V> parent;  // 父节点
    boolean red = RED;  // 颜色，默认红色
​
    Node(K key, V value, Node<K, V> parent) {
        this.key = key;
        this.val = value;
        this.parent = parent;
    }
​
    Node(K key, V value, boolean red) {
        this.key = key;
        this.val = value;
        this.red = red;
    }
}

6. 插入

6.1. 流程

插入操作相对复杂，因此分为两个流程：主流程描绘整体逻辑；子流程描绘性质修复。

6.1.1. 主流程

6.1.2. 子流程

流程说明：
1.  根节点由红变黑，红黑树的黑高加 1；
2. 父节点为黑色，这是默认平衡情形，无需调整；
3. 父节点为红色，叔叔节点为黑色，最多两次旋转即恢复平衡；
4. 只有父节点和叔叔节点都为红色，才需要再次迭代。

具体可以先看下图，然后再结合代码和流程图来理解。

6.1.3. 情形分析

6.2. 性质修复

(1) 当前节点为根节点

(2) 父节点为黑色

(3) 父节点为红色，叔叔节点为红色

父节点 P 和当前节点 X 均为红色，违反性质4。
演化：
首次迭代：(3)
再次迭代：(3) —> (3)
操作：
父节点 P 染黑色，性质4被满足，但又违反了性质5：从根节点到经过 P 的路径上的黑色节点数比其它路径多1；
再将祖父节点 G 染红色，叔叔节点 U 染黑色，性质5 被满足；
最后将祖父节点设为当前节点，未结束。
后续：
如果新 X 已是根节点，那么就会演变成情形 1。
如果新 X 仍有父节点，那么就会演变成情形 2、情形 3 或情形 4；
最坏的情况下，一直都是情形3，那么需要递归向上处理直到根节点才结束。

(4) 父节点为红色，叔叔节点为黑色

(4-1) LR：父节点为祖父节点的左孩子，当前节点为父节点的右孩子

(4-2) LL：父节点为祖父节点的左孩子，当前节点为父节点的左孩子

(4-3) RL：父节点为祖父节点的右孩子，当前节点为父节点的左孩子

(4-4) RR：父节点为祖父节点的右孩子，当前节点为父节点的右孩子

6.3. 操作等价性

这一小节，我们来探讨红黑树和4 阶 B 树关于插入操作的等价关系。
看完这些示例，相信会对为什么要考察父节点和叔叔节点的颜色有更深的理解。

无上溢

4 阶 B 树的一个内部节点最多有3个键，2-节点再插入一个键，3-节点再插入一个键，都不会出现上溢。
4 阶 B 树的 2-节点再插入一个键变成 3-节点，对应到红黑树是默认平衡情形，肯定不用调整。
4 阶 B 树的 3-节点再插入一个键变成 4-节点，则需看插入的先后顺序，对应红黑树中的旋转。
（中 —> 小 —> 大）或（中 —> 大 —> 小）：红黑树中，父节点为黑色，默认平衡情形，无需调整；
（大 —> 中 —> 小）或（小 —> 中 —> 大）：红黑树中，父节点为红色，叔叔节点为黑色，对应需要 1 次旋转 (LL，RR)；
（大 —> 小 —> 中）或（小 —> 大 —> 中）：红黑树中，父节点为红色，叔叔节点为黑色，对应需要 2 次旋转 (LR，RL)；

这里只画了（小 —> 中 —> 大）( G H I ) 这种插入顺序，其它情形略。

上溢

4 阶 B 树的 4-节点再插入 1个键，会出现上溢问题，需通过分裂来修复。
等价于红黑树新节点的父节点和叔叔节点均为红色，需通过变色来修复。
最坏情况下，两者都需要递归向上处理直到根节点才结束。
如果递归到根节点，那么，4 阶 B 树的高度会加 1，相应地红黑树的黑高也加 1。

接上图，继续插入 J。

6.4. 代码实现

代码逻辑与流程图一致，可与之相互印证理解。

6.4.1. 插入

public void put(K key, V value) {
    Assert.notNull(key);
    Assert.notNull(value);
    // 情形1：新插入节点为根节点
    if (root == null) {
        size.increment();
        root = new Node<>(key, value, BLACK);
        size.set(1);
        return;
    }
    Node<K, V> p = root;
    // 先查找，并将新节点添加为叶子节点
    while (true) {
        int cmp = compare(p.key, key);
        if (cmp > 0) {
            if (p.left == null) {
                size.increment();
                p.left = new Node<>(key, value, p);
                // 修复红黑树性质
                fixAfterInsertion(p.left);
                return;
            }
            p = p.left;
        } else if (cmp < 0) {
            if (p.right == null) {
                size.increment();
                p.right = new Node<>(key, value, p);
                // 修复红黑树性质
                fixAfterInsertion(p.right);
                return;
            }
            p = p.right;
        } else {
            p.val = value;
            return;
        }
    }
}

6.4.2. 修复性质

/**
 * 插入节点后修复红黑树性质
 *
 * @param x 当前节点
 */
private void fixAfterInsertion(Node<K, V> x) {
    // 1. 情形2：父节点为黑色，无需调整，不进入循环
    // 2. 父节点为红色，需要修复，进入循环
    while (isRed(x.parent)) {
        Node<K, V> p = x.parent;
        Node<K, V> g = p.parent;
        Node<K, V> u = (p == g.left) ? g.right : g.left;
        if (isBlack(u)) {
            // 情形4：父节点为红色，叔叔节点为黑色（或叔叔节点不存在）
            setColor(g, RED);
            if (p == g.left) {
                if (x == p.right) {
                    rotateLeft(p);  // 4-3：LR
                    p = x;          // 4-3：LR
                }
                setColor(p, BLACK); // 4-1：LL
                rotateRight(g);     // 4-1：LL
            } else {
                if (x == p.left) {
                    rotateRight(p); // 4-4：RL
                    p = x;          // 4-4：RL
                }
                setColor(p, BLACK); // 4-2：RR
                rotateLeft(g);      // 4-2：RR
            }
            return;
        }
        // 情形3：父节点是红色，叔叔节点是红色
        setColor(p, BLACK);
        setColor(u, BLACK);
        if (g == root) return;  // 情形1：已经递归到根节点(省略变色过程)
        setColor(g, RED);
        x = g;  // 再次迭代
    }
}

6.4.3. 旋转

/**
 * 左旋
 *
 * @param p 节点
 */
private void rotateLeft(Node<K, V> p) {
    Node<K, V> r = p.right;
    p.right = r.left;
    if (r.left != null) {
        r.left.parent = p;
    }
    Node<K, V> g = r.parent = p.parent;
    if (g == null) {
        // 祖父节点为空，r设为根节点
        root = r;
    } else if (g.left == p) {
        g.left = r;
    } else {
        g.right = r;
    }
    r.left = p;
    p.parent = r;
}
​
/**
 * 右旋
 *
 * <pre>
 *     以 p 节点的左孩子 l 为轴进行旋转：
 *     p 变成 l 的右孩子；
 *     lr 变成 p 的左孩子；
 *     p 的 父节点变成 l；
 *     l 的父节点变成 p 的父节点 g；
 *           g                   g
 *          /                   /
 *         p                   l
 *       /   \               /   \
 *      l     r             ll    p
 *    /  \                      /  \
 *   ll   lr                   lr   r
 * </pre>
 *
 * @param p 节点
 */
private void rotateRight(Node<K, V> p) {
    Node<K, V> l = p.left;
    p.left = l.right;
    if (l.right != null) {
        l.right.parent = p;
    }
    Node<K, V> g = l.parent = p.parent;
    if (g == null) {
        // 祖父节点为空，l设为根节点
        root = l;
    } else if (g.left == p) {
        g.left = l;
    } else {
        g.right = l;
    }
    l.right = p;
    p.parent = l;
}

7. 删除

大多数算法书对删除操作的介绍都令人难以理解，原因在于省略了演化过程。
所以，除了流程图之外，我会用表格来枚举所有可能的情形并推演各种变化。

7.1. 流程

删除操作相对复杂，因此分为两个流程：主流程描绘整体逻辑；子流程描绘性质修复。

7.1.1. 主流程

流程说明：
(1) 如果待删除节点有两个子节点，需先与其前驱交换；
(2) 只有待删除节点为黑色时，才需修复红黑树的性质。

7.1.2. 情形分析

7.1.3. 子流程

流程说明：
(1) 修复性质需根据父节点、兄弟节点和两个侄子节点的颜色来分别作出不同的处理；
(2) 只有父节点、兄弟节点、两个侄子节点均为黑色，即情形B6，才会进入再次迭代。

为方便与流程对照，我先将这 6 种情形放在一张图中，如下图所示：

7.2. 删除示例

对于首次迭代，其实是很容易理解的。
比较复杂的是：一种情形会转换为哪一种情形？是如何转换的？什么情况下还需再次迭代？
通过流程图，我们已建立了一个整体概念。接下来，我们就通过操作示例来验证流程逻辑。

7.2.1. 删除示例1

先看一个最简单的例子。

7.2.1. 删除示例2

再看一个稍复杂的例子。

(a)：
1. A 设为当前节点 ，标记删除 A。
2. 经过 B 的左孩子(A)的路径上的黑色节点数变为 2，比其它路径少 1，违反性质5。
3. A 的父节点 B 和 兄弟节点 C 都为黑色；C 的两个孩子为空，所以也是黑色（根据性质3），符合情形 B6。
(b)：
1. 兄弟节点 C 染红色。
2. 经过 B 的路径上的黑色节点数都变成了 2，比其它路径少 1，违反性质5。
3. 当前节点 X 变为其父节点 B，此时 B 是局部平衡的，第一次迭代结束。
4. B 的父节点 D 和兄弟节点 F 都为黑色，F 的两个孩子 E 和 G 也是黑色，又再次符合情形B6。
(c)：
1. 兄弟节点 F 染红色。
2. 经过 D 的路径上的黑色节点数都变成了 2。
3. 当前节点 X 变为其父节点 D，此时 D 是局部平衡的，第二次迭代结束。
4. D 为根， 符合情形B1。
(d)：
1. 无需调整：由于 D 为根，因此 D 平衡即整棵树平衡。
2. 黑高由 3 变为 2。
(e)：正式移除 A。

7.2.2. 删除示例3

最后一个更复杂的例子。

(a)：
1. A 设为当前节点 ，标记删除 A。
2. 经过 B 的左孩子(A)的路径上的黑色节点数为 2，比其它路径少 1，违反性质5。
3. A 的父节点 B 和 兄弟节点 C 都为黑色，C 的两个孩子为空也是黑色（根据性质3），符合情形 B6。
(b)：
1. 兄弟节点 C 染红色。
2. 经过 B 的路径上的黑色节点数都变成了 2，比其它路径少 1，违反性质5。
3. 当前节点变为其父节点 B，此时 B 是局部平衡的，第一次迭代结束。
4. B 的兄弟节点 H 为红色，符合情形B2。
(c)：
1. 父节点 D 染红色，兄弟节点 H 染黑色，父节点 D 左旋；
2. 旋转完成后，B 的兄弟节点变成了 F。
3. 经过 B 的路径上的黑色节点数还是 2，比其它路径少 1，违反性质5。
4. 当前节点还是 B，B 依然是局部平衡的，第二次迭代还未结束。
5. B 的父节点 D 为红色， 兄弟节点 F 为黑色，F 的两个孩子 E 和 G 都为黑色，符合情形B3。
(d)：
1. 父节点 D 染黑色，兄弟节点 F 染红色。
2. 经过 B 的路径上的黑色节点数加 1 变为3，与其它路径相等，恢复平衡。
3. 第二次迭代结束。
4. 黑高不变还是 3。
(e)：正式移除 A。

小结

1. 所有情形的修复操作都是为了维护性质 5。
2. 如果性质修复流程结束于情形 B1 ，那么黑高减 1，其它情形则黑高不变。
3. 每一种情形处理完成后，当前节点都是局部平衡的。
4. 除非当前节点为根，否则当前节点所在路径上的黑色节点数总是比其它路径少 1。
5. 首次迭代时当前节点是待删除节点；再次迭代时变为原当前节点的父节点。
6. 如果每次迭代都进入情形 B6，那么迭代过程需到根节点才结束。

7.3. 性质修复

看完示例，我们继续来具体分析每一种情形。

B1：当前节点为根节点

B6：父节点、兄弟节点、两个侄子节点都是黑色的

首次迭代时，移除待删除节点 X 后，经过原 X 所在的路径上的黑色节点数会比其它路径少 1。
再次迭代时，上次迭代必定结束于 B6，因此当前节点 X 的路径上的黑色节点数也必定比其它路径少 1。
所有情形都是如此，后面不再提示。

演化：
首次迭代：B6
再次迭代：B6 —> B6
操作：
兄弟节点 S 黑变红：父节点 P 达到局部平衡，如果 P 不是根节点，那么 P 所在路径上的黑色节点数比其它路径少 1。
父节点 P 设为当前节点 X：由于新 X 的父节点、兄弟节点、侄子节点都不确定，所以下次迭代时六种情形都有可能。
如果新 X 已经是根节点，那么就会演变成情形 B1。
如果新 X 仍然有父节点，那么就会演变成 B2 至 B6；
最坏的情况下，一直都是情形B6，那么需要递归向上处理直到根节点才结束。
后续：仍可能违反性质5，未结束。

B2：兄弟节点为红色

当兄弟节点 S 为红色时，S 的两个孩子 C 和 D 必不为空且一定是黑色，P 也必定为黑色。
演化：
首次迭代：B2
再次迭代：B6 —> B2
操作：
兄弟节点 S 染黑色，父节点 P 染红色，父节点 P 左旋。
调整之后，当前节点 X 不变，父节点变为红色，黑色的远侄节点 D变成了其新兄弟节点 ，这可能演化成 B3，B4，B5 这三种情形。
后续：经过 X 的路径上的黑色节点还是少1，仍违反性质5，所以未结束。

B3：父节点为红色，兄弟节点及两个侄子节点都为黑色

B4：兄弟节点为黑色，远侄节点为红色

B5：兄弟节点为黑色，近侄节点为红色

特别说明：
以上图例，X 都是父节点 P 的左孩子。
当 X 为父节点 P 的右孩子时的操作恰好相反，具体处理可看代码及注释。

7.4. 操作等价性

这一小节，我们来探讨红黑树和4 阶 B 树关于删除操作的等价关系。

非叶节点

4 阶 B 树中删除非叶节点中的键，先与前驱（或后继）交换，转换成删除前驱（或后继）的情形。
红黑树中删除有两个孩子的节点，先与前驱（或后继）交换，转换成删除前驱（或后继）的情形 (A1 —> A2 或 A3)。
两者是等价的。

无下溢

4 阶 B 树的 4-节点有3个键，3-节点有2个键，因此删除一个键都不会出现下溢问题。

4-节点删除中间的键：等价于红黑树中待删除节点为黑色，有两个红色子节点 (A1 —> A3)。
4-节点删除两边的键：等价于红黑树中待删除节点为红色 (A3)。

3-节点删除一个键，根据插入顺序不同，也对应这两种情形：
红黑树中待删除节点为红色 (A3)；
红黑树中待删除节点为黑色，有一个红色子节点 (A2)。

下溢

4 阶 B 树的 2-节点删除一个键，会出现下溢问题，可以根据兄弟节点的情况，使用不同的方式来处理：
兄弟节点有富余：旋转——等价于红黑树中侄子节点至少有一个为红色(B4，B5)。
兄弟节点无富余：合并——等价于红黑树中侄子节点全部都为黑色(B2，B3，B6)。

4 阶 B 树中，如果当前节点一直是2-节点，而兄弟节点也一直无富余，那么下溢问题会递归向上处理到根节点才结束。
相对应的，红黑树中如果父节点、兄弟节点和侄子节点一直都是黑色 (B6)，那么也需要递归向上处理到根节点才结束。

如果出现下溢的节点是根节点，等价于红黑树中当前节点 (待删除节点) 为根节点(B1)。

类比示例

具体看以下示例，我们会看到4阶B树 和红黑树的删除操作是等价的。
看完这些示例，相信会对为什么要考察父节点、兄弟节点和侄子节点的颜色有更深的理解。

​

​图7.13 删除类比示例2

7.5. 删除情形枚举

有一个很常见的疑问：删除是不是真的只有 6 种情形？我可以肯定地答：是！
通过上一小节的描述其实已经可以推导出只有 6 种情形。
这里我再穷举所有情形，彻底打消这个疑虑，具体看下表。

7.6. 代码实现

代码参照《算法导论.第3版 [7]》伪码实现并简化了部分逻辑，代码逻辑与流程图一致，可以参照流程图来印证理解。

7.4.1. 删除

@Override
public V remove(K key) {
    Node<K, V> x = search(key);
    if (x == null) {
        return null;
    }
    V oldVal = x.val;
    delete(x);
    return oldVal;
}
​
private void delete(Node<K, V> x) {
    size.decrement();
    // 是否有两个孩子
    if (x.left != null && x.right != null) {
        // 情形A1：与前驱交换
        x = predecessor(x);
    }
    // 获取待删除节点的子节点，用以接替待删除节点的位置
    Node<K, V> replacement = x.left != null ? x.left : x.right;
    if (replacement != null) {
        // 情形A2：待删除节点 X 有一个孩子（X 必为黑色，r 必为红色）
        // 子节点设为黑色
        setColor(replacement, BLACK);
    } else {
        if (isBlack(x)) {
            fixAfterDeletion(x);
        }
    }
    // 移除待删除节点
    transplant(x, replacement);
}
​
/**
 * 与前驱交换
 *
 * @param x 待删除节点
 * @return 前驱
 */
private Node<K, V> predecessor(Node<K, V> x) {
    Node<K, V> pred = x.left;
    while (pred.right != null) {
        pred = pred.right;
    }
    x.key = pred.key;
    x.val = pred.val;
    return pred;
}
​
/**
 * 移除节点（父节点中指向删除节点的链接变成指向其子节点）
 *
 * @param x 待删除节点
 * @param r 待删除节点的子节点
 */
private void transplant(Node<K, V> x, Node<K, V> r) {
    Node<K, V> p = x.parent;
    if (p == null) {
        // 如果待删除节点为根节点，根变成其子节点
        root = r;
        return;
    }
    if (r != null) {
        r.parent = p;
    }
    if (x == p.left) {
        p.left = r;
    } else {
        p.right = r;
    }
}

7.4.2. 修复性质

/**
 * 删除节点后修复红黑树的性质
 *
 * @param x 当前节点（待删除节点或其唯一子节点）
 */
private void fixAfterDeletion(Node<K, V> x) {
    // 情形 B1：如果x 为根，退出
    while (x != root) {
        if (x == x.parent.left) {
            Node<K, V> s = x.parent.right;
            if (s.red == RED) {
                // 情形 B2：兄弟节点S 染黑色，父节点P 染红色，父节点P 左旋，未结束
                setColor(s, BLACK);         // B2
                setColor(x.parent, RED);    // B2
                rotateLeft(x.parent);       // B2
                s = x.parent.right;         // B2
            }
            if (isBlack(s.left) && isBlack(s.right)) {
                // 情形 B3 或 B6：兄弟节点S 染红色，未结束
                setColor(s, RED);               // B3 或 B6
                if (isRed(x.parent)) {
                    setColor(x.parent, BLACK);  // B3
                    return;                     // B3
                }
                x = x.parent;                   // B6 再次迭代 Δh+1
            } else {
                if (isBlack(s.right)) {
                    // 情形 B5：近侄节点C 染黑色，兄弟节点S 染红色，兄弟节点S 右旋，S:=P.r，未结束
                    setColor(s.left, BLACK);    // B5
                    setColor(s, RED);           // B5
                    rotateRight(s);             // B5
                    s = x.parent.right;         // B5
                }
                // 情形 B4：兄弟节点S 染父节点P 的颜色，父节点P 染黑色，远侄节点D 染黑色，父节点P 左旋，结束
                setColor(s, x.parent.red);      // B4
                setColor(x.parent, BLACK);      // B4
                setColor(s.right, BLACK);       // B4
                rotateLeft(x.parent);           // B4
                return;                         // B4
            }
        } else {
            Node<K, V> s = x.parent.left;
            if (s.red == RED) {
                // 情形 B2：兄弟节点S 染黑色，父节点P 染红色，父节点P 右旋，未结束
                setColor(s, BLACK);             // B2
                setColor(x.parent, RED);        // B2
                rotateRight(x.parent);          // B2
                s = x.parent.left;              // B2
            }
            if (isBlack(s.left) && isBlack(s.right)) {
                // 情形 B3 或 B6：兄弟节点S 染红色，未结束
                setColor(s, RED);               // B3 或 B6
                if (isRed(x.parent)) {
                    setColor(x.parent, BLACK);  // B3
                    return;                     // B3
                }
                x = x.parent;                   // B6 再次迭代 Δh+1
            } else {
                if (isBlack(s.left)) {
                    // 情形 B5：近侄节点C 染黑色，兄弟节点S 染红色，兄弟节点S 左旋，S:=P.l，未结束
                    setColor(s.right, BLACK);   //B5
                    setColor(s, RED);           //B5
                    rotateLeft(s);              //B5
                    s = x.parent.left;          //B5
                }
                // 情形 B4：兄弟节点S 染父节点P 的颜色，父节点P 染黑色，远侄节点D 染黑色，父节点P 右旋，结束
                setColor(s, x.parent.red);      // B4
                setColor(x.parent, BLACK);      // B4
                setColor(s.left, BLACK);        // B4
                rotateRight(x.parent);          // B4
                return;                         // B4
            }
        }
    }
}

8. 红黑树的高度

8.1. 最大高度的证明

引理：一棵有 n 个内部节点的红黑树的高度最大为 \(2log_2(n+1) \)。

证明：
首先证明以任一节点 x 为根的子树至少包含 \(2^{bh(x)}-1\) 个内部节点（\( bh(x)\) 表示以 x 为根的子树的黑高）。
先考虑 x 的黑高等于 0 时的情况：以 x 为根的子树至少包含 \(2^{bh(x)}-1=2^0-1=0\) 个内部节点。
再考虑 x 的黑高大于 0 时的情况：
当 x 为黑色时，x 的两个子节点的黑高比 x 的黑高少 1，其每个子节点至少包含 \(2^{bh(x)-1}-1\) 个内部节点；
当 x 为红色时，x 的两个子节点的黑高与 x 的黑高相等，其每个子节点至少包含 \(2^{bh(x)}-1\) 个内部节点；
两者比较，当 x 为黑色时，内部节点数较少。
因此可得，以 x 为根的子树至少包含 \((2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1=2^{bh(x)}-1\) 个内部节点，由此得证。

现在继续证明引理。

设 h 为树的高度，根据性质 4，从根到外部节点的任何一条路径上至少有一半的节点为黑色，那么，根的黑高至少为 h/2。于是有：

\(n \geqslant 2^{h/2}-1\)

1 移到不等式左边，再两边取对数，最后两边乘以 2，可得：

\(h \leqslant 2log_{2}(n+1)\)

证毕。

参考《算法导论.第3版7》

另一种证明：
设红黑树的黑色节点数为 m ，高度为 h。
根据性质 5，从根到其外部节点的所有路径包含相同数量的黑色节点，所以移除所有红色节点后就是一棵高度为 \(log_{2}(m+1)\)  的完美二叉树。
根据性质 4，从根到外部节点的任何一条路径上至少有一半节点为黑色，因此可得： \(h \leqslant 2log_{2}(m+1)\)。
又因为 \(m \leqslant n\) ，所以： \(h \leqslant 2log_{2}(n+1)\)

这个证明利用了已知的完美二叉树的高度计算公式，所以会更简洁一些。

8.2. 与 AVL 比较

红黑树的平衡条件可以看作是：任意节点的左右子树的高度，相差不超过 2 倍。
AVL 树的平衡条件比红黑树更严格：任意节点的左右子树的高度之差不超过 1 。
理论上红黑树的查询性能会略差，AVL 树的修改性能会略差，但实际应用中两者差别非常细微。

9. 小结

红黑树算是二叉树结构当中较难理解的结构：一是为什么设计成这样，二是删除的各种情形推理。
写文章比写代码难太多，因为无法预知读者会哪里不理解，所以画了很多图，希望能真的能对读者有所有帮助。
关于二叉树，写完这篇文章就基本完结了，后面再继续聊字典树。

PS：有根有据有态度的分享，如果觉得不错，请点赞收藏哦！

参考资料