6.2 红黑树

前一节：AVL 与旋转｜下一章：堆

AVL 保存精确高度，红黑树改为维护颜色与黑高度。本节先固定 NIL 约定，再推导高度上界，随后跟完插入的变色与旋转，并用父链接和验证器检查实现。

1. AVL 之后，为什么还要学颜色

AVL 在每个节点限制左右高度差，得到很紧的形状上界。更新代码要维护精确高度；删除后，多个祖先可能继续失衡。

AVL 与红黑树维护不同的不变量。颜色规则允许更宽的形状；真实性能仍取决于工作负载和实现。

2. 先统一 NIL 叶子

代码常用 None 表示不存在的孩子。红黑树的定义把每个空孩子视为一个黑色 NIL 叶子。NIL 不保存用户键，但参与颜色和黑高度推理。

本节采用常见的五条性质：

每个实际节点是红色或黑色。
根是黑色。
每个 NIL 叶子是黑色。
红色节点的两个孩子都是黑色；因此根到叶路径上不会出现连续红节点。
从任一节点到其后代 NIL 叶子的所有路径，黑节点数量相同。

不同教材可能把根黑、NIL 黑合并进其他规则，或把“节点颜色”改写成“父链接颜色”。只要约定完整，证明和实现可以互相转换。回答问题时先说清使用哪一套。

3. 黑高度怎样限制整棵树

本节把节点 x 的黑高度定义为：从 x 出发到任一后代 NIL 的路径上，不计 x 本身，但计入末端 NIL 的黑节点数。性质 5 保证选哪条向下路径都得到同一个值。约定 NIL 自身黑高度为 0。

设以实际节点 x 为根的子树黑高度为 b。它的两棵子树黑高度都至少为 b-1：黑孩子会消耗一个黑节点，红孩子不会。以 NIL 含 0 个实际节点为归纳起点，两边各至少有 2^(b-1)-1 个节点，加上 x，总数至少为：

text

2^b - 1

对整棵树，令 n 为实际节点数、b 为根的黑高度，就有 b <= log2(n + 1)。根为黑色且红节点不能相邻，因此实际节点中黑节点至少占一半。树高 h 按最长路径上的实际节点数计，不含 NIL；空树高度为 0。于是：

text

h <= 2b <= 2 log2(n + 1)

搜索沿一条根到叶路径行走，时间为 O(log n)。插入和删除先做 BST 定位，再修复颜色与连接，总时间也为 O(log n)。

“最长路径不超过最短路径两倍”若没说明路径是否包含 NIL、如何计数，就容易含糊。黑高度推导更稳，也直接给出关于 n 的上界。

4. 新节点为什么先染红

在非空树的一个 NIL 位置插入黑节点，会让经过该位置的路径多一个黑节点，其他路径不变，性质 5 因而失效。先染红不会改变黑高度。向空树插入第一个根是例外：所有路径同时增加一个黑节点，根可以直接染黑。

红色新节点可能遇到红色父节点，违反性质 4。插入修复只在这种“双红”出现时运行。根没有父节点，最后统一染黑。

每轮修复先找三个角色：

node：当前冲突中的下层红节点；
parent：红色父节点；
uncle：祖父的另一个孩子，空孩子按黑色处理。

5. 三种修复形状

图中 B 表示黑色，R 表示红色。

红叔叔：只变色，冲突向上走

插入 1 到已有的 10、5、15：

text

      10B                 10R
     /   \               /   \
    5R   15R     ->      5B   15B
   /                    /
  1R                   1R

父亲和叔叔染黑，祖父染红。祖父若是根，循环结束后再染黑；若祖父的父亲也是红色，下一轮继续向上检查。

黑叔叔，外侧形状：旋转祖父

[10, 5, 1] 形成 LL 外侧形状：

text

      10B               5B
      /                /  \
     5R      -->      1R  10R
    /
   1R

父亲染黑、祖父染红，再右旋祖父。RR 是镜像操作。

黑叔叔，内侧形状：先拉直

[10, 5, 7] 形成 LR：

text

      10B           10B              7B
      /             /               / \
     5R    -->     7R      -->     5R 10R
       \          /
       7R        5R

先左旋父节点，把 LR 转成 LL；再按外侧规则处理。RL 是镜像。

6. 完整红黑树插入

下面的实现使用父指针向上修复。父指针让迭代代码更直观，但不是红黑树定义的一部分；递归实现也可以在返回时维护祖先连接。它保存唯一整数键，插入前检查 int 类型，重复键返回 False；与前节一样，bool 沿用 Python 的整数相等规则。

is_valid() 检查：

严格 BST 上下界；
根颜色和根父指针；
每个孩子的 parent 是否指回当前节点；
红节点是否有红孩子；
左右黑高度是否相同；
实际节点数是否等于 size。

python

RED = "RED"
BLACK = "BLACK"

def require_int_key(key):
    if not isinstance(key, int):
        raise TypeError("key must be an integer")

class RBNode:
    def __init__(self, key, color=RED):
        require_int_key(key)
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.root = None
        self.size = 0

    @staticmethod
    def _color(node):
        return BLACK if node is None else node.color

    def _rotate_left(self, old_root):
        new_root = old_root.right
        middle = new_root.left

        old_root.right = middle
        if middle is not None:
            middle.parent = old_root

        new_root.parent = old_root.parent
        if old_root.parent is None:
            self.root = new_root
        elif old_root is old_root.parent.left:
            old_root.parent.left = new_root
        else:
            old_root.parent.right = new_root

        new_root.left = old_root
        old_root.parent = new_root

    def _rotate_right(self, old_root):
        new_root = old_root.left
        middle = new_root.right

        old_root.left = middle
        if middle is not None:
            middle.parent = old_root

        new_root.parent = old_root.parent
        if old_root.parent is None:
            self.root = new_root
        elif old_root is old_root.parent.left:
            old_root.parent.left = new_root
        else:
            old_root.parent.right = new_root

        new_root.right = old_root
        old_root.parent = new_root

    def insert(self, key):
        require_int_key(key)
        parent = None
        current = self.root

        while current is not None:
            parent = current
            if key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                return False

        node = RBNode(key)
        node.parent = parent
        if parent is None:
            self.root = node
        elif key < parent.key:
            parent.left = node
        else:
            parent.right = node

        self.size += 1
        self._fix_insert(node)
        return True

    def _fix_insert(self, node):
        while node.parent is not None and node.parent.color == RED:
            parent = node.parent
            grandparent = parent.parent

            if parent is grandparent.left:
                uncle = grandparent.right
                if self._color(uncle) == RED:
                    parent.color = BLACK
                    uncle.color = BLACK
                    grandparent.color = RED
                    node = grandparent
                else:
                    if node is parent.right:
                        node = parent
                        self._rotate_left(node)
                    parent = node.parent
                    grandparent = parent.parent
                    parent.color = BLACK
                    grandparent.color = RED
                    self._rotate_right(grandparent)
            else:
                uncle = grandparent.left
                if self._color(uncle) == RED:
                    parent.color = BLACK
                    uncle.color = BLACK
                    grandparent.color = RED
                    node = grandparent
                else:
                    if node is parent.left:
                        node = parent
                        self._rotate_right(node)
                    parent = node.parent
                    grandparent = parent.parent
                    parent.color = BLACK
                    grandparent.color = RED
                    self._rotate_left(grandparent)

        self.root.color = BLACK

    def inorder(self):
        result = []

        def walk(node):
            if node is None:
                return
            walk(node.left)
            result.append(node.key)
            walk(node.right)

        walk(self.root)
        return result

    def height(self):
        def measure(node):
            if node is None:
                return 0
            return 1 + max(measure(node.left), measure(node.right))

        return measure(self.root)

    def is_valid(self):
        if self.root is None:
            return self.size == 0
        if self.root.parent is not None or self.root.color != BLACK:
            return False

        def check(node, low, high, expected_parent):
            if node is None:
                return True, 1, 0  # 隐式 NIL 是黑色
            if node.parent is not expected_parent:
                return False, 0, 0
            if node.color not in {RED, BLACK}:
                return False, 0, 0
            if (low is not None and node.key <= low) or (
                high is not None and node.key >= high
            ):
                return False, 0, 0
            if node.color == RED and (
                self._color(node.left) == RED or self._color(node.right) == RED
            ):
                return False, 0, 0

            left_ok, left_black_count, left_count = check(
                node.left, low, node.key, node
            )
            right_ok, right_black_count, right_count = check(
                node.right, node.key, high, node
            )
            if not left_ok or not right_ok or left_black_count != right_black_count:
                return False, 0, 0

            black_count = left_black_count + (node.color == BLACK)
            return True, black_count, left_count + right_count + 1

        valid, _, count = check(self.root, None, None, None)
        return valid and count == self.size

tree = RedBlackTree()
values = [10, 5, 15, 1, 7, 12, 18, 6, 8, 11, 13, 17, 20]
for value in values:
    assert tree.insert(value)
    assert tree.is_valid()

assert tree.inorder() == sorted(values)
assert tree.insert(10) is False
assert tree.size == len(values)

ordered = RedBlackTree()
for value in range(1, 101):
    ordered.insert(value)
    assert ordered.is_valid()

assert (1 << ordered.height()) <= (ordered.size + 1) ** 2

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

check() 返回的 black_count 计入当前节点和末端 NIL，所以空孩子返回 1。它与第 3 节排除当前节点的黑高度差一个当前节点的颜色贡献：黑叶子的 black_count 是 2，黑高度是 1。比较左右子树时，两边使用同一约定即可。

验证器假定向下的孩子链接无环、无共享节点。它会检查父链接、颜色、顺序和计数，但不负责遍历任意损坏的对象图。这里的 height() 实际遍历整棵树，为 O(n)；AVL 示例中的同名方法读取缓存，为 O(1)。height()、inorder() 和完整验证的递归栈均为 O(h+1)，合法树时为对数上界；中序列表另占 Θ(n) 输出空间。插入使用父指针迭代修复，辅助空间为 O(1)。这些成本把整数 key 的比较当作常数操作。

最后一个断言把 h <= 2 log2(n+1) 改写成 2^h <= (n+1)^2，无需浮点取整。

为什么父链接必须一起更新

旋转不只改局部的三条向下连接。新根还要接回旧根原来的父节点：

中间子树改父指针。
新根继承旧根的父节点。
旧根原父节点的 left 或 right 改指向新根；旧根原来是整棵树根时，更新 self.root。
旧根挂到新根下面，并改父指针。

内部旋转要更新原父节点的孩子指针；整棵树根发生旋转时则要更新 self.root。遗漏任一种位置，都可能使部分节点从根不可达。

7. 插入旋转次数与总时间

Linux 内核 rbtree 文档给出经典红黑树重平衡的界限：插入最多两次旋转，删除最多三次旋转。这是经典修复算法的界限，不能直接套到所有左倾等变体上。

这里的“最多两次”只数旋转：

找插入位置仍要走一条 O(log n) 路径；
红叔叔情况可能向上重复变色；
每轮颜色读写是常数工作，但轮数可能达到 O(log n)。

所以“旋转是常数次”和“插入总时间是 O(log n)”并不冲突。

AVL 插入也最多两次基础旋转。两者更明显的差异出现在删除：AVL 可能在多个祖先处旋转，经典红黑树删除把旋转数限制在三次以内。真实速度还受比较器、缓存和实现质量影响。

8. 删除为什么更难

先用 BST 删除步骤，把操作归结为移除一个至多有一个实际孩子的节点。这里讨论的是最终被移除节点的颜色：双孩子目标可能只被替换 key，实际移除的是它的后继。

移除红叶不会减少黑节点数。移除黑节点时，若唯一孩子为红，可把这个孩子染黑来补回；否则可能留下少一个黑节点的路径，通常用“额外黑”或“双黑”标记这个缺口。修复再检查兄弟及其孩子的颜色，通过变色和旋转恢复各条路径的黑高度。

本页实现插入，删除部分先说明修复的来源：

text

删除黑节点 -> 某些路径黑高度少 1 -> 向兄弟借结构或把缺口向上传递

工作中应优先使用经过测试的容器实现。若要学习完整删除，测试至少要覆盖红叶、黑叶、一个孩子、根、红兄弟、黑兄弟的两个孩子都为黑，以及近侄/远侄为红的镜像情况。兄弟的两个孩子中，靠近缺口的一侧是近侄，另一侧是远侄；NIL 也按黑色计算。

9. 红黑树和多路树的关系

红链接可以把多个二叉节点编码成一个多键节点，不过变体名称要写清楚：

经典红黑树更自然地对应 2-3-4 树。黑节点和它的红孩子可以合并成 2、3 或 4 节点。
Princeton 的 RedBlackBST明确实现 2-3 版本：完成操作后，红链接只向左且不连续，与 2-3 树一一对应。

这里的 2-3 对应特指上述变体。普通五性质红黑树允许黑节点拥有两个红孩子，对应 2-3-4 树中的 4 节点。比较算法时应核对它实际维护的不变量，不能仅凭“红黑树”或“左倾”这个名字互换修复代码。

10. 标准库到底承诺什么

Java `TreeMap`

Oracle Java 21 文档明确写明 TreeMap 基于红黑树，并保证 containsKey、get、put、remove 的时间是 O(log n)。文档还说明键顺序来自自然顺序或构造时传入的 Comparator。

可以说“TreeMap 使用红黑树”。Oracle 的公开文档没有说明选型时如何衡量读写成本，因此不能替它补写理由。

C++ `std::map`

C++ 有序关联容器要求规定排序语义、迭代顺序和对数复杂度。标准没有规定节点颜色，也没有要求某种树形。

许多标准库实现使用红黑树，这属于具体实现事实。专业文档应标明实现和版本，不能把它升级成语言标准保证。

Linux rbtree

Linux 提供通用 rbtree 接口，内核子系统可用它管理有序对象。引用当前内核文档比写“某个调度器一定使用红黑树”更稳，因为具体子系统会随内核版本变化。

11. 元数据占多少空间

从算法模型看，AVL 节点记录高度，红黑节点记录颜色。模型不能直接推出对象的物理大小：

语言运行时可能给对象加头部和对齐填充；
boolean 字段不保证只占一个物理位；
Linux 的 rb_node把父指针和颜色合存在 __rb_parent_color 字段中；
父指针是否存在取决于实现方式。

比较内存应查看具体布局或测量，不要用“整数对一位颜色”直接下结论。

12. 排错清单

症状	检查点
根是红色	`_fix_insert` 退出后是否强制染黑
中序遍历少一整棵子树	旋转时是否接回 `middle`
内部旋转后节点不可达	旧根原父节点的孩子指针是否改指向新根
验证器发现父指针错误	孩子、旧根、新根的三组父链接是否同步
黑高度左右不等	红叔叔变色后是否把检查位置上移到祖父
内侧 case 旋转方向混乱	是否先转父节点，再重新取得父亲和祖父

13. 动手验证颜色与父链接

画出 [10, 5, 15, 1]，写出变色前后每个实际节点的颜色。
分别画 [10, 5, 1] 和 [10, 5, 7]，指出哪一步旋转父节点、哪一步旋转祖父。
解释为什么新节点染红不会立刻改变黑高度。
说明父指针是实现选择，却为何在本页代码中必须维护正确。
用一句话区分 Java TreeMap 与 C++ std::map 的实现保证。

总结：红黑树维护什么

红黑标记不测量每一段枝条的精确高度。它禁止连续红节点，并让同一节点到所有 NIL 的黑高度一致，由此把树高限制在 O(log n)。父指针虽不是定义的一部分，却是本页迭代修复的关键元数据；内部旋转时若没有同步接回原父节点，整棵子树会失联。

AVL 树显式维护 height，红黑树维护颜色与黑高度约束。两者都避免搜索树退化，保存的元数据和修复策略却不同。下一章不再维护完整搜索顺序，而把当前最小值或最大值留在根附近：第 7 章：堆。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算

6.2 红黑树

1. AVL 之后，为什么还要学颜色

2. 先统一 NIL 叶子

3. 黑高度怎样限制整棵树

4. 新节点为什么先染红

5. 三种修复形状

红叔叔：只变色，冲突向上走

黑叔叔，外侧形状：旋转祖父

黑叔叔，内侧形状：先拉直

6. 完整红黑树插入

为什么父链接必须一起更新

7. 插入旋转次数与总时间

8. 删除为什么更难

9. 红黑树和多路树的关系

10. 标准库到底承诺什么

Java `TreeMap`

C++ `std::map`

Linux rbtree

11. 元数据占多少空间

12. 排错清单

13. 动手验证颜色与父链接

总结：红黑树维护什么