第 13 章红黑树 (Red-Black Trees)

核心结论

红黑树性质：5 条规则——(1) 每节点红或黑；(2) 根黑；(3) 叶 (NIL) 黑；(4) 红节点的子节点都黑（无红-红相邻）；(5) 每节点到后代叶的任意路径黑节点数相同（黑高 bh）。
高度上界 (引理 13.1)：n 节点的红黑树高度 h ≤ 2 lg(n+1) = O(lg n)；推论：所有基本操作 SEARCH/INSERT/DELETE 等最坏 O(lg n)。
旋转 (Rotation)：LEFT-ROTATE / RIGHT-ROTATE 是局部操作——保持 BST 性质、改变指针结构 O(1) 时间；n 节点树恰有 n-1 种可能旋转。
插入 (RB-INSERT)：BST 插入 + 染新节红；调用 RB-INSERT-FIXUP 处理 3 种情形：uncle 红（重染色，z 上移 2 层）/ uncle 黑 + z 是右子（rotate 转到情形 3）/ uncle 黑 + z 是左子（recolor + rotate 终止）。最坏 2 次旋转。
删除 (RB-DELETE)：基于 TREE-DELETE，RB-DELETE-FIXUP 处理 4 种情形——sibling 红 / sibling 黑 + 两侄都黑 / sibling 黑 + 左侄红 / sibling 黑 + 右侄红；最坏 3 次旋转。
变种与对比：AA 树（左子不能红）、AVL 树（更严平衡）、Treap（键序 + 随机优先级）、Splay 树（摊还 O(lg n)）、跳表（链表 + 多级指针）。

本章主旨

本章是「自平衡二叉搜索树」的代表——红黑树。是第 12 章 BST 的「工程级实现」。通过：(1) 给节点加 color 字段，(2) 在 INSERT / DELETE 后用旋转 + 重染色恢复 5 条红黑性质，保证树高 O(lg n)，从而最坏情形下也达到 Θ(lg n) 性能。红黑树是 C++ STL std::map / set、Java TreeMap、Linux CFS 调度器的核心数据结构——是理论与实践的桥梁。本章是数据结构部分最数学化的章节之一——大量循环不变量证明。

一、核心概念

本章围绕 4 个核心概念展开：从红黑树的 5 条性质与高度上界开始，引入旋转作为基本操作，再用 RB-INSERT / RB-DELETE 展示如何在保持性质的同时插入与删除。

概念	定义 + 重要性	实现提示
红黑性质 (Red-Black Properties)	5 条规则：节点红/黑、根黑、叶 NIL 黑、无红-红相邻、每节点到后代叶黑高（bh）相同。	§13.1；定义红黑树是「近似平衡」BST；NIL 视为黑哨兵节点（§13.1）；总高度 ≤ 2 lg(n+1)。
旋转 (LEFT-ROTATE / RIGHT-ROTATE)	局部指针重连操作——保持 BST 性质；LEFT-ROTATE(T, x) 把 x 的右孩子 y 提升为子根，x 变为 y 的左子。	§13.2；O(1) 时间；n 节点 BST 恰 n-1 种可能旋转；双旋转组合可处理任意重平衡。
RB-INSERT 与 3 种情形	BST 插入 + 染新节红；RB-INSERT-FIXUP 处理 uncle 颜色三种情形：uncle 红（重染，z 上移 2 层）/ uncle 黑 + z 是右子（rotate → case 3）/ uncle 黑 + z 是左子（recolor + rotate 终止）。	§13.3；最坏 2 次旋转；三种情形对称左右各一组共 6 种。
RB-DELETE 与 4 种情形	基于 TREE-DELETE；若删除的 y 黑 → 调用 RB-DELETE-FIXUP，处理 sibling 颜色 4 种情形：sibling 红 / sibling 黑 + 两侄黑 / sibling 黑 + 左侄红 / sibling 黑 + 右侄红；引入「extra black」概念。	§13.4；最坏 3 次旋转；只有情形 2 循环，z 上移 O(h) 次；总 O(h)。

概念

定义 + 重要性

实现提示

红黑性质 (Red-Black Properties)

5 条规则：节点红/黑、根黑、叶 NIL 黑、无红-红相邻、每节点到后代叶黑高（bh）相同。

§13.1；定义红黑树是「近似平衡」BST；NIL 视为黑哨兵节点（§13.1）；总高度 ≤ 2 lg(n+1)。

旋转 (LEFT-ROTATE / RIGHT-ROTATE)

局部指针重连操作——保持 BST 性质；LEFT-ROTATE(T, x) 把 x 的右孩子 y 提升为子根，x 变为 y 的左子。

§13.2；O(1) 时间；n 节点 BST 恰 n-1 种可能旋转；双旋转组合可处理任意重平衡。

RB-INSERT 与 3 种情形

BST 插入 + 染新节红；RB-INSERT-FIXUP 处理 uncle 颜色三种情形：uncle 红（重染，z 上移 2 层）/ uncle 黑 + z 是右子（rotate → case 3）/ uncle 黑 + z 是左子（recolor + rotate 终止）。

§13.3；最坏 2 次旋转；三种情形对称左右各一组共 6 种。

RB-DELETE 与 4 种情形

基于 TREE-DELETE；若删除的 y 黑 → 调用 RB-DELETE-FIXUP，处理 sibling 颜色 4 种情形：sibling 红 / sibling 黑 + 两侄黑 / sibling 黑 + 左侄红 / sibling 黑 + 右侄红；引入「extra black」概念。

§13.4；最坏 3 次旋转；只有情形 2 循环，z 上移 O(h) 次；总 O(h)。

二、详细笔记

13.1 红黑树的性质与黑高

What：红黑树是带 color 字段（红/黑）的 BST，满足 5 条「红黑性质」；由此推得高度上界 2 lg(n+1)。

Why：这 5 条性质「强制」树近似平衡——任何根到叶的路径长度 ≤ 任何其他路径的 2 倍；不靠显式平衡因子（如 AVL 树）而靠颜色约束。

How：

5 条性质（§13.1）：
每个节点红或黑。
根节点是黑。
每个叶 (NIL) 是黑。
若节点红，则其两个子节点都黑（无红-红相邻）。
对每个节点，从该节点到后代叶节点的每条简单路径含相同数目的黑节点。
NIL 哨兵（§13.1）：所有 NIL 指针统一为单个 T:nil 哨兵（黑色）；简化「NIL 父指针」的边界条件。代码用 T:nil 代替 NIL。
黑高 (Black-Height)：bh(x) = 从 x（不含）到叶的路径上黑节点数；性质 5 保证 bh(x) 良定义；bh 树 = bh(根)。
引理 13.1：n 内节点红黑树高 ≤ 2 lg(n+1)：
- 命题：以 x 为根的子树 ≥ 2^{bh(x)} - 1 内部节点（对高度归纳）。
- 基：x = NIL（叶）→ bh = 0，含 0 ≥ 2⁰ - 1。
- 步：x 内部 → x.left 与 x.right 黑高 ≥ bh(x) - 1；归纳得每个 ≥ 2^{bh(x)-1} - 1；总数 ≥ (2^{bh(x)-1} - 1) + (2^{bh(x)-1} - 1) + 1 = 2^{bh(x)} - 1。
- 完整证明：h ≤ 2 bh(根)（无连续红节点 → 半数为黑）；n ≥ 2^{bh(根)} - 1 ≥ 2^{h/2} - 1 → h ≤ 2 lg(n+1)。
推论：所有 BST 操作（SEARCH / MIN / MAX / SUCCESSOR / PREDECESSOR）在红黑树上 = O(lg n) 最坏。

When： . 需要有序字典 + 最坏保证 → 红黑树。 . 单纯字典 + 平均 O(1) → 散列表。 . 高频插入删除 + 严格平衡 → AVL 树。

Example（图 13.1）：一棵 7 黑高（根黑高 3）的红黑树：根 13（黑）；左 8（红）→ 左 1（黑）→ 左 6（红）→ 右 11（红）+ 右 17（红）；右子树类似。BST 性质满足 + 颜色约束满足 → h = 4 = 2·3 ≤ 2 lg(15) ≈ 7.7。

13.2 旋转 (LEFT-ROTATE / RIGHT-ROTATE)

What：旋转是「保持 BST 性质的局部指针重连」操作；LEFT-ROTATE 把 x 提升到右子位置，RIGHT-ROTATE 是对称的。

Why：旋转是 RB-INSERT-FIXUP 和 RB-DELETE-FIXUP 的核心工具——重染色 + 旋转恢复红黑性质。

How：

LEFT-ROTATE(T, x)（§13.2）：

\[\begin{array}{rl} & \textbf{LEFT-ROTATE}(T, x) \\ 1 & y = x.\text{right} \\ 2 & x.\text{right} = y.\text{left} \quad \text{// 1. y's 左子树成为 x 的右子树} \\ 3 & \textbf{if } y.\text{left} \neq T.\text{nil} \\ 4 & \quad y.\text{left}.\text{p} = x \\ 5 & y.\text{p} = x.\text{p} \quad \text{// 2. y 继承 x 的父关系} \\ 6 & \textbf{if } x.\text{p} == T.\text{nil} \\ 7 & \quad T.\text{root} = y \\ 8 & \textbf{elseif } x == x.\text{p}.\text{left} \\ 9 & \quad x.\text{p}.\text{left} = y \\ 10 & \textbf{else } x.\text{p}.\text{right} = y \\ 11 & y.\text{left} = x \quad \text{// 3. x 成为 y 的左子} \\ 12 & x.\text{p} = y \end{array}\]
复杂度 O(1) — 仅改指针。
n-节点 BST 恰 n-1 种旋转（练习 13.2-2）：每条边对应一次旋转的可能；n-1 条边 → n-1 种旋转。

When： . 任何 BST 重平衡 → 旋转。 . Treap 实现 → 不停旋转维持堆序。 . Splay 树 → 旋转 + zig-zag 组合。

Example（图 13.3）：LEFT-ROTATE(T, x) 其中 x = 12，右子 y = 18；操作后 y=18 提升为根（代替 x 在父的位置），x=12 成为 y 的左子，y 原左子（11, 9）成为 x 的右子。中序遍历不变。

13.3 RB-INSERT

What：插入 = BST 插入 + 染新节红色 + 调用 RB-INSERT-FIXUP 恢复 5 条性质（处理红-红冲突）。

Why：只把新节点染红色（不染黑）——黑高不变，但可能违反性质 2（根红）或性质 4（红-红相邻）；染黑色则所有路径黑高都 +1（违反性质 5）。FIXUP 用 3 种情形把「红-红」消除。

How：

RB-INSERT(T, z)（§13.3）：BST 插入 + z.color = RED + 调用 FIXUP。
RB-INSERT-FIXUP（§13.3）：

\[\begin{array}{rl} & \textbf{while } z.\text{p}.\text{color} == \text{RED} \\ & \quad \textbf{if } z.\text{p} == z.\text{p}.\text{p}.\text{left} \\ & \quad\quad y = z.\text{p}.\text{p}.\text{right} \quad \text{// uncle} \\ & \quad\quad \textbf{if } y.\text{color} == \text{RED} \\ & \quad\quad\quad \textbf{Case 1: uncle 红} \\ & \quad\quad \quad z.\text{p}.\text{color} = \text{BLACK}; y.\text{color} = \text{BLACK} \\ & \quad\quad \quad z.\text{p}.\text{p}.\text{color} = \text{RED}; z = z.\text{p}.\text{p} \\ & \quad\quad \textbf{else if } z == z.\text{p}.\text{right} \\ & \quad\quad\quad \textbf{Case 2: uncle 黑, z 是右子} \\ & \quad\quad \quad z = z.\text{p}; \textbf{LEFT-ROTATE}(T, z) \\ & \quad\quad\quad \textbf{Case 3: uncle 黑, z 是左子} \\ & \quad\quad \quad z.\text{p}.\text{color} = \text{BLACK}; z.\text{p}.\text{p}.\text{color} = \text{RED} \\ & \quad\quad \quad \textbf{RIGHT-ROTATE}(T, z.\text{p}.\text{p}) \\ & \quad \textbf{else (symmetric)} \\ & T.\text{root}.\text{color} = \text{BLACK} \end{array}\]
三种情形：
- 情形 1（uncle 红）：重染色（z.p 和 y 转黑、z.p.p 转红）；z 上移到 z.p.p 继续。性质 5 保持（路径黑数不变）。
- 情形 2（uncle 黑 + z 是右子）：rotate 转为情形 3。
- 情形 3（uncle 黑 + z 是左子）：recolor + 右旋转 z.p.p；循环终止。
复杂度：n 节点红黑树 BST 插入 O(h) = O(lg n)；FIXUP 每次情形 1 把 z 上移 2 层 → O(h) 次 = O(lg n)；情形 2/3 终止循环 → 最坏 2 次旋转。

When： . 大多数红黑树实现用 sentinel T:nil，代码稍改动；父指针可省（用栈模拟，练习 13.3-6）。 . 若用「treap」等随机化结构 → 直接是 O(lg n) 期望，免去 FIXUP。

Example：插入 13 到图 13.4 的树：(a) 13 插入为黑 z，z.p = 红 7 → 性质 4 违反；(b) 情形 1（uncle 11 红）：重染色，z 上移到黑 11？——视具体树结构；(c) 情形 2/3：rotate 终止。图见 §13.3。

13.4 RB-DELETE

What：删除 = TREE-DELETE + 调用 RB-DELETE-FIXUP；若删除的 y 黑 → FIXUP 处理「extra black」问题（4 种情形）。

Why：删除黑色节点会减少某些路径的黑高，破坏性质 5；FIXUP 通过「把 y 的黑色转移到 x（x 是替代 y 位置的节点）」保留黑高，最后消除 x 的「双黑」标记。

How：

RB-DELETE(T, z)（§13.4）：
- 用 RB-TRANSPLANT 代替 TREE-DELETE 的 TRANSPLANT（处理 T.nil）。
- 维持 y (待删 / 移动节点) + y-original-color + x (替代节点)。
- 删除结束后若 y-original-color = BLACK → RB-DELETE-FIXUP。
「extra black」概念：删黑节点 y 后，y 位置现在的 x 是「doubly black」——多了一层黑色。FIXUP 目标是把多出的黑色「向上推到根」或遇到红节点变黑。
RB-DELETE-FIXUP（§13.4）：

\[\begin{array}{rl} & \textbf{while } x \neq T.\text{root} \text{ and } x.\text{color} == \text{BLACK} \\ & \quad \textbf{if } x == x.\text{p}.\text{left} \\ & \quad\quad w = x.\text{p}.\text{right} \quad \text{// sibling} \\ & \quad\quad \textbf{Case 1: sibling 红} \\ & \quad\quad \quad w.\text{color} = \text{BLACK}; x.\text{p}.\text{color} = \text{RED} \\ & \quad\quad \quad \textbf{LEFT-ROTATE}(T, x.\text{p}); w = x.\text{p}.\text{right} \\ & \quad\quad \textbf{Case 2: sibling 黑, 两侄都黑} \\ & \quad\quad \quad w.\text{color} = \text{RED}; x = x.\text{p} \quad \text{// extra black 上推} \\ & \quad\quad \textbf{Case 3: sibling 黑, 左侄红, 右侄黑} \\ & \quad\quad \quad w.\text{left}.\text{color} = \text{BLACK}; w.\text{color} = \text{RED} \\ & \quad\quad \quad \textbf{RIGHT-ROTATE}(T, w); w = x.\text{p}.\text{right} \\ & \quad\quad \textbf{Case 4: sibling 黑, 右侄红} \\ & \quad\quad \quad w.\text{color} = x.\text{p}.\text{color}; x.\text{p}.\text{color} = \text{BLACK} \\ & \quad\quad \quad w.\text{right}.\text{color} = \text{BLACK}; \textbf{LEFT-ROTATE}(T, x.\text{p}); x = T.\text{root} \\ & \quad \textbf{else (symmetric)} \\ & x.\text{color} = \text{BLACK} \end{array}\]
四种情形：
- 情形 1（sibling 红）：重染色 + 左旋 → 转为情形 2/3/4。
- 情形 2（sibling 黑 + 两侄都黑）：sibling 转红，多余黑上推到 x.p；继续（O(lg n) 次）。
- 情形 3（sibling 黑 + 左侄红）：重染色 + 右旋 → 情形 4。
- 情形 4（sibling 黑 + 右侄红）：重染色 + 左旋 + 终止（多余黑被分配到子树）。
复杂度：FIXUP 总 O(h) = O(lg n)；最坏 3 次旋转。

When： . 红黑树实际实现中删除比插入少见（DELETE 通常不如 INSERT 频繁）。 . RB-JOIN（问题 13-2）合并两红黑树 + 一个中间键 → O(lg n)。

Example：删除红节点 → 不调用 FIXUP；删除黑节点（无孩子或单孩子）→ 移到 NIL 或单孩子位置，多余黑「继承」给 NIL/孩子，需 FIXUP。

三、关键图表

核心公式对照表

式编号

内容

红黑性质 (5 条)

见 §13.1

引理 13.1

n 节点红黑树高 h ≤ 2 lg(n+1)

子树节点下界

x 为根子树 ≥ 2^{bh(x)} - 1

黑高下界

bh(根) ≥ h/2

LEFT/RIGHT-ROTATE

O(1) 时间

RB-INSERT

O(lg n) 时间 + 最坏 2 次旋转

RB-INSERT 情形数

3 种（uncle 红 / uncle 黑 + z 右子 / uncle 黑 + z 左子），加对称共 6 种

RB-DELETE

O(lg n) 时间 + 最坏 3 次旋转

RB-DELETE 情形数

4 种（sibling 红 / 黑 + 两侄都黑 / 黑 + 左侄红 / 黑 + 右侄红）

RB-JOIN

O(lg n) 时间

Treap 期望旋转

< 2

四、思维导图

mindmap
  root((第 13 章 红黑树))
    5性质
      节点颜色
      根黑
      叶黑
      无红红
      黑高相同
    高度
      ≤2lg(n+1)
      引理13.1
    旋转
      O(1)
      保BST
      双方向
    插入
      染红插入
      uncle三情形
      2次旋转
    删除
      extra black
      sibling四情形
      3次旋转
    变种
      AA树
      AVL
      Treap
      Splay
      跳表

五、重点与易错点

红黑树是「近似平衡」而非「严格平衡」 — 高度 ≤ 2 lg(n+1)，比 AVL 树松；常数因子小（最多 3 次旋转）。
NIL 视为黑哨兵 — 用 T:nil 单个对象代替所有 NIL 指针，简化「父指针」的边界条件。
INSERT 时为什么染红而不染黑（练习 13.3-1）— 染红只可能违反性质 2（根红）和性质 4（红-红），不会改黑高；染黑改所有路径黑高（性质 5 灾难）。
RB-INSERT-FIXUP 情形 1 是「向上推」 — z 上移 2 层；情形 2/3 是「向下处理」（rotate + 终止）。
RB-INSERT 最坏 2 次旋转 — 情形 1 不旋转，情形 2/3 最多 1 次。
RB-DELETE-FIXUP 引入「extra black」概念 — 不需要真改颜色属性；用「节点位置指示」表示多出黑；最终通过旋转把它分配到子树。
RB-DELETE 情形 2 是唯一可能循环 — z 上移 O(lg n) 次；情形 1/3/4 有限步骤终止。
RB-DELETE 最坏 3 次旋转 — 情形 1 + 情形 3 + 情形 4 顺序可能（实际代码中情形 1 不会单独引发旋转）。
删除红节点不调用 FIXUP — 因为红节点删不改变黑高；只有删黑节点才调。
红黑树持久化 (问题 13-1) 关键 — 不修改原节点，「path copying」只建沿路径 O(h) 个新节点；空间复杂度 O(lg n)。
AA 树 (Weiss) — 左孩子不能红；编程更简单但功能受限（性能略低）。
AVL 树 (Adelson-Velsky & Landis) — 高度差 ≤ 1 的严格平衡；插入 / 删除需要 O(lg n) 次旋转；但查找常数略小。
Treap (Random + Heap) — 键序满足 BST + 优先级满足最小堆；插入期望 O(lg n) 且旋转期望 < 2 次。
Splay 树 (Sleator-Tarjan) — 摊还 O(lg n)；自调整（无显式平衡因子）；适合访问局部性强的字典。
红黑树 vs 跳表 — 跳表实现简单、并发友好；但复杂操作不如红黑树（如 MIN/MAX 仍是 O(lg n)）。
平衡树的选择：均衡高度严格度（红黑 < AA < AVL）vs 编程难度（跳表 < Treap < 红黑 < AVL）。

补充：与其他章节的衔接

第 12 章（BST）：红黑树是 BST 的「自平衡」变种；BST 所有操作 O(h)，红黑树 h = O(lg n)。
第 14 章（扩充数据结构）：在红黑树上加 size 字段 → 顺序统计树（OS-tree），可 O(lg n) 找第 i 小 / 找某元素排名。
第 18 章（B 树）：B 树是多路（而非二叉）平衡搜索树；用于磁盘存储（页 I/O）；红黑树可看作 2-3-4 树的二叉表示。
第 17 章（摊还分析）：Splay 树摊还分析；红黑树也可摊还分析（构造全局插入时间为 O(lg n)）。
第 23 / 24 章（最短路径）：Dijkstra 算法用优先级队列 → 红黑树作底层（O(lg n) DECREASE-KEY）；heap 仅 O(lg n) DECREASE-KEY 也可但常数更大。
第 27 章（多线程）：并发字典用红黑树（锁粒度）/ 跳表（无锁）vs 散列表（细锁）。

第 13 章 红黑树 (Red-Black Trees)

核心结论

一、核心概念

二、详细笔记

13.1 红黑树的性质与黑高

13.2 旋转 (LEFT-ROTATE / RIGHT-ROTATE)

13.3 RB-INSERT

13.4 RB-DELETE

三、关键图表

四、思维导图

五、重点与易错点

补充：与其他章节的衔接

第 13 章红黑树 (Red-Black Trees)