Article

算法导论-CH13-红黑树

算法导论-CH13-红黑树，待补充摘要。

May 23, 2026 修考 16 min read

Demo: Balancing with Tree Rotation

红黑树demo

CS61B Lecture 19 课程笔记：树旋转与红黑树 (Tree Rotations & LLRBs)

知识脑图与手写笔记逻辑结构

本篇笔记结合了课堂课件与手写笔记的精华，按照以下核心逻辑顺序展开：

研究动机 (Motivation)：为什么不用 $2\text{-}3$ 树？（实现极其痛苦）
树旋转 (Tree Rotation)：如何通过旋转（rotateLeft / rotateRight）在不破坏 BST 性质的前提下改变树的高度与结构？
左倾红黑树 (LLRB)：通过引入 “红链接 (Red Glue)” 将 $2\text{-}3$ 树完美投影（Isometry）到 BST。
动态平衡维护 (Maintaining Isometry)：手写笔记核心——插入 4 步法则以及如何通过旋转与颜色翻转（Color Flip）自动保持树的平衡。
经典例题与演练：保留全部课堂互动与练习，并给出详细的推导步骤。

一、研究动机：B-Trees 的痛点

在学习了 $2\text{-}3$ 树和 $2\text{-}4$ 树（即 B-Trees）后，我们知道它们能够保证完美的对数级查找时间 $O(\log N)$ 。然而，高德纳（Donald Knuth）曾说过：

“Beautiful algorithms are, unfortunately, not always the most useful.” （美丽的算法遗憾地并不总是最实用的。）

在实际开发中直接实现 $2\text{-}3$ 树会遇到以下严重痛点：

多种节点类型难以维护：需要分别处理 2-Nodes 和 3-Nodes。
节点类型相互转换极其繁琐：在插入和删除时，需要频繁在 2-Nodes、3-Nodes 和临时 4-Nodes 之间变换。
向上回溯分裂（Split）逻辑复杂：需要沿着父节点指针一路向上回溯分裂并重新分配子节点。

替代思路 (Alternate Idea)

我们能否继续使用简单、统一的二叉搜索树 (BST) 结构，但通过某种机制让它自动保持平衡？答案是：通过“树旋转 (Tree Rotation)”机制来调节高度。

二、树旋转 (Tree Rotation)

1. 旋转的定义与标准操作程序 (SOP)

旋转操作能够在完全保留 BST 查找性质（即左小右大）的前提下，改变树的局部高度与局部根节点。

(1) 左旋 `rotateLeft(G)`

手写笔记 SOP 还原与完善：

令 $x$ 为 $G$ 的右孩子。 $x$ 将取代 $G$ 成为该子树的新根（New Boss）。

$G$ 下沉，成为 $x$ 的左孩子（因为 $G < x$ ）。

$x$ 原本的左孩子（介于 $G$ 和 $x$ 之间）转移，成为 $G$ 的新右孩子。

直观图示：

     G (旧根)                    x (新根)
    / \                        / \
   A   x                      G   C
      / \                    / \
     B   C                  A   B

性质不变性验证：
- 旋转前： $A < G < B < x < C$
- 旋转后： $A < G < B < x < C$ （BST 顺序完美保留！）

(2) 右旋 `rotateRight(P)`

手写笔记 SOP 还原与完善：

令 $x$ 为 $P$ 的左孩子。 $x$ 将取代 $P$ 成为该子树的新根。

$P$ 下沉，成为 $x$ 的右孩子（因为 $P > x$ ）。

$x$ 原本的右孩子（介于 $x$ 和 $P$ 之间）转移，成为 $P$ 的新左孩子。

直观图示：

        P (旧根)                 x (新根)
       / \                     / \
      x   C                   A   P
     / \                         / \
    A   B                       B   C

2. 旋转的局限性与非法操作

旋转不是万能的：如果某个节点没有相应的孩子，则无法向该方向旋转。
- 例如：若节点 $1$ 没有左孩子，执行 rotateRight(1) 是非法操作 (Invalid Operation)。
旋转的代价：通过树旋转，我们可以在 $O(1)$ 的时间内改变树的高度。通过在整棵树上做最多 $O(N)$ 次旋转，我们可以将任意形状的 BST 调整到平衡状态，但盲目尝试旋转开销太大。

三、左倾红黑树 (Left-Leaning Red-Black Trees, LLRB)

1. 红链接的本质：2-3 树的同构映射 (Isometry)

为了知道“何时、何地进行旋转”，我们引入一个天才的想法：建立 BST 与 $2\text{-}3$ 树的 1-对-1 投影关系。

2-Node 的映射：直接对应 BST 中的普通节点（黑链接）。
3-Node 的映射： $2\text{-}3$ 树中的 3-Node 含有两个元素（较小值 $L$ ，较大值 $R$ ）。我们将其拆分为两个二叉节点，并用一条红色的“粘合线 (Glue Link)”*将* $L$ *作为* $R$ *的*左孩子相连。

手写笔记要点：将 $2\text{-}3$ 树使用一种 “glue” 来联系，用红线表示。这种红线说明连接的两个 item 实际上在 $2\text{-}3$ 树中是在一起（属于同一个节点）*的。为了规范化，我们规定红链接*必须向左倾斜，即左倾红黑树（LLRB）。

3-Node 映射对照图：

  2-3 Tree 里的 3-Node:          LLRB 里的表示:
      [ d   f ]                      f (Black)
     /   |   \                     / \
    b    e    g                (Red) d    g
                              / \
                             b   e

2. LLRB 的核心性质 (Properties)

基于 $2\text{-}3$ 树的完美平衡性，LLRB 继承了以下极强的数学性质：

没有任意节点可以拥有两条红链接：
- 对应 $2\text{-}3$ 树中最多只能有 3-Node（即 1 条红链接），不能出现 4-Node。
完美黑色平衡 (Perfect Black Balance)：
- 从根节点（Root）到任意叶子节点的空链接（Null Link）的路径上，黑色链接的数量必须完全相同。这是因为 $2\text{-}3$ 树本身是完美平衡的，红链接只是内部的“粘合剂”，不增加 $2\text{-}3$ 树的高度。
红链接只能是左倾的（这是 LLRB 特有的简化规定，标准红黑树允许右倾红链接）。

3. LLRB 树高分析 (Height Analysis)

手写笔记推导纠错与完善：

设 $2\text{-}3$ 树的高度为 $H$ 。

最矮路径：全由黑色链接组成（即一路上全都是 2-Nodes），高度为 $H$ 。

极高路径（最长路径）：红黑交替的路线（即一路上全都是 3-Nodes）。

因为不能有两个连续的左倾红链接（每一层最多一个红链接），所以最长路径最多包含 $H$ 条黑链接和 $H+1$ 条红链接。

因此，LLRB 的最大高度为：

$Height_{max} \le 2H + 1$

由于 $H = \Theta(\log N)$ ，所以 LLRB 的高度也严格被控制在 $\Theta(\log N)$ 内。查找操作的运行时间最坏情况下也仅为 $O(\log N)$ ！

四、维护同构映射：LLRB 的插入与旋转算法

📝 这里是手写笔记第二页的精髓！ > 课件中的复杂情况被精简为了极其好记的 “4步法则 / SOP 维护机制”。当我们在树中插入新元素时，只需自底向上递归应用这四条规则，就能自动修复所有冲突。

🚨 LLRB 插入 4 步法则 (SOP)

① 规则一：新插入的元素，一律用 “Red Glue” 连接

原理：在 $2\text{-}3$ 树中，新元素总是先放入叶子节点中进行合并（即放入现有的节点中，而不是新开一层）。在二叉树中，这等价于用红链接（Glue）将新节点连接到父节点上。

② 规则二：如果是右侧 red glue $\rightarrow$ `rotateLeft`

原理：红链接必须左倾。如果插入到了右侧，需要通过一次左旋，将其转为合法的左倾红链接。
图示：

    Parent                     Parent
      \                          /
       New (Red)   ==旋===>    New (Red)

③ 规则三：如果有连续两个左侧 red $\rightarrow$ `rotateRight`

原理：不能出现连续两个左侧红链接（这在 $2\text{-}3$ 树中代表一个非法的 4-Node，且偏向一侧严重失衡）。通过右旋，我们可以将结构对称化，为下一步的“颜色翻转”做准备。
图示：

          Grandparent                 Parent
            / (Red)                  /      \ (Red)
         Parent       ==右旋===>   New(Red)  Grandparent
          / (Red)
        New

④ 规则四：如果同时有左右 red $\rightarrow$ 翻转颜色 (Color Flip)，上一层次级变 red

原理：当一个节点的左右孩子都是红色时，这代表在 $2\text{-}3$ 树中产生了一个临时的 4-Node $[A, B, C]$ 。根据 $2\text{-}3$ 树的规则，4-Node 必须分裂，中间元素 $B$ 向上提并融入父节点。
操作：
1. 将左右孩子的颜色由红变黑（相当于向下分配分裂后的黑色连接）。
2. 将当前节点自身的颜色由黑变红（相当于把中间元素向上推入父节点，成为父节点的红链接）。
注意：当前节点变红后，可能会导致它的父级节点也产生“右倾红链接”或“连续红链接”冲突。因此，该过程需要自底向上递归级联（Cascading），直到根节点。根节点最后若变红，直接强制变回黑色即可（这对应着 $2\text{-}3$ 树增加一层高度的时刻）。

五、课堂例题与练习解析 (Exercises)

📊 练习 1：判断合法的 LLRB

【题目】：以下四棵红黑树，有多少棵是合法的 LLRB（即能 1-对-1 投影到合法的 $2\text{-}3$ 树）？ (注：双线表示红链接，单线表示黑链接)

    (1)             (2)             (3)             (4)
     G               G               G               G
    / \             / \             / \             / \
   B   X           B   X           B   X           C   X
  // \            / \             / \\            // \
  A   C          A   C           A   C            A   B

【详细解析】：

图 (1) [不合法]：节点 B 有两条红链接（左子 A 和自身作为 G 的左子）。这意味着节点 B 在 $2\text{-}3$ 树中既和 G 粘合，又和 A 粘合，形成了一个 4-Node。LLRB 不允许 4-Node 状态持久化。
图 (2) [不合法]：G 到 A、B、C、X 的空路径上，黑色链接数不平衡。具体而言：
- 到 A 的路径：G -> B (黑), B -> A (黑)，共 2 个黑键。
- 到 X 的路径：G -> X (黑)，共 1 个黑键。
- 违反了“黑色完美平衡”。
图 (3) [不合法]：B -> C 是右倾红链接。LLRB 规定红链接必须左倾。
图 (4) [合法]：
- 所有红链接都是左倾的（C -> A 是红链接）。
- 完美黑色平衡：从 G 到任意 Null 的黑色高度均为 1（路径 G -> C 是黑的，G -> X 是黑的）。
- 对应的 $2\text{-}3$ 树结构为：根节点是 G，左子是 3-Node [A, C]，右子是 X。

📊 练习 2：计算 LLRB 的实际高度

【题目】：若某一 $2\text{-}3$ 树结构如下（粉色标记的为 3-Nodes，即含有两个元素的节点）：

          [ D , E ]                  [ P ]
         /    |    \                /     \
      [ B ] [ G ]  [ J, N ]      [ Q, R ] [ V, W ]

已知该 $2\text{-}3$ 树的高度（Tallness/Height）为 3。求它对应的 LLRB 的树高度（即从根到叶子结点的最长路径边数）。

【详细解析】：

分析投影变换：
- 在 LLRB 中，每一个普通的 2-Node 对应 $1$ 条黑链接。
- 每一个 3-Node 被拆分为两个二叉节点，中间用 $1$ 条红链接连接。
寻找最长路径：
- 树的深度取决于沿着哪一条路径向下走。为了让路径最长，我们应该选择穿过尽可能多的 3-Nodes（因为 3-Node 会额外贡献一条红链接）。
- 观察上图：
  - 根节点是 3-Node [D, E] $\rightarrow$ 贡献 $1$ 条黑键， $1$ 条红键。
  - 中间孩子 [J, N] 是 3-Node $\rightarrow$ 贡献 $1$ 条黑键， $1$ 条红键。
  - 叶子节点 [Q, R] 也是 3-Node $\rightarrow$ 贡献 $1$ 条黑键， $1$ 条红键。
计算高度：
- 该路径上包含的黑色链接数 = $2\text{-}3$ 树的高度 = $3$ 。
- 该路径上包含的红色链接数 = 沿途 3-Nodes 的个数 = $2$ （注意：最底下的 3-Node 不会向更下方产生红链接）。
- 故最长路径高度为：
  
  $3 \text{ (Black)} + 2 \text{ (Red)} = 5$

📊 挑战练习：插入元素 $7$ 到 $1$ 验证平衡

【自主演练】：尝试将 $7, 6, 5, 4, 3, 2, 1$ 依次插入一个初始为空的 LLRB 树中，应用上面的 4 步法则。

【部分过程详解】：

插入 7：
- 7（根，黑色）。
插入 6：
- 新插入一律为红，故 6(红) 挂在 7 的左边（合法，无需旋转）。
插入 5：
- 5(红) 挂在 6 的左边。此时出现连续左侧红链接（违反规则三：7 -> 6(红) -> 5(红)）。
- 修复：对 7 执行 rotateRight(7) $\rightarrow$ 结构变为 6 成为根，5(红) 为左子，7(红) 为右子。
- 此时，6 的左右孩子均为红色（违反规则四）。
- 修复：对 6 进行 Color Flip $\rightarrow$ 5 和 7 变为黑色，6 变为红色（作为根节点，最终被强制设为黑色）。
- 阶段树形状：
```
      6 (黑)
     /   \
   5(黑) 7(黑)
```
- 树实现完美平衡！

六、各种搜索树总结 (Search Tree Summary)

树类型	平衡机制	查找复杂度 $O(\cdot)$	插入复杂度 $O(\cdot)$	实现复杂度与评价
普通 BST	无（依赖插入顺序）	最坏 $O(N)$ , 平均 $O(\log N)$	最坏 $O(N)$ , 平均 $O(\log N)$	极易实现，但容易退化为链表。
$2\text{-}3$ 树 (B-Tree)	节点分裂与合并（向上回溯）	严格 $O(\log N)$	严格 $O(\log N)$	逻辑极难维护，存在多种节点类型和高昂的转换开销。
左倾红黑树 (LLRB)	树旋转与颜色翻转（保持 $2\text{-}3$ 树同构）	严格 $O(\log N)$	严格 $O(\log N)$	插入操作极其简洁，代码优美，但删除操作（Delete）依然较难实现。
标准红黑树 (TreeMap)	允许左右红链接	严格 $O(\log N)$	严格 $O(\log N)$	Java 中的 `TreeMap` 对应的是 $2\text{-}4$ 树。代码更复杂，但在实际工业运行中，由于减少了旋转次数，速度通常比 LLRB 更快。

CS61B Lecture 19 课程笔记：树旋转与红黑树 (Tree Rotations & LLRBs)

知识脑图与手写笔记逻辑结构

一、 研究动机：B-Trees 的痛点

替代思路 (Alternate Idea)

二、 树旋转 (Tree Rotation)

1. 旋转的定义与标准操作程序 (SOP)

(1) 左旋 rotateLeft(G)

(2) 右旋 rotateRight(P)