第 17 讲：红黑树与 2-3-4 树

一、先理解 2-3-4 树

红黑树的五条规则如果直接背，是纯粹的记忆负担。但如果先看 2-3-4 树，它们会全部变成显然的。

2-3-4 树 是一棵多路搜索树，每个节点可以有 2、3 或 4 个孩子：

2-节点（1 个键）      3-节点（2 个键）        4-节点（3 个键）
     [ b ]             [ b | d ]            [ b | d | f ]
     ╱   ╲            ╱    │    ╲          ╱   │   │   ╲
   <b     >b        <b   b..d   >d       <b  b..d d..f  >f

核心不变式：所有叶子都在同一深度。 树是完美高度平衡的。

插入：分裂 4-节点

插入总是发生在叶子。若叶子是 4-节点（已满），先分裂：中间的键升到父节点，剩下两个键分成两个 2-节点。

       [ e ]                        [ c | e ]
      ╱                            ╱    │
 [a|b|c|d]      分裂     ⟹      [a|b]  [d]
   插入 x                        ← c 升到父节点

⭐ 树长高的唯一方式是根节点分裂——这就是"所有叶子同深度"能一直保持的原因。2-3-4 树从底部往上生长，而不是像 BST 那样从顶部往下延伸。 这是它天然平衡的根本原因。

高度：每个节点至少 2 个孩子，所以 h ≤ log₂ n；至多 4 个孩子，所以 h ≥ log₄ n。总是 Θ(log n)。

二、红黑树 = 2-3-4 树的二叉表示

问题：2-3-4 树节点大小不一，实现起来麻烦。能不能用二叉树表示它？

能。把 3-节点和 4-节点拆成若干个二叉节点，用红色边表示"这两个节点原本属于同一个 2-3-4 节点"：

2-节点          3-节点                    4-节点
  ⚫b            ⚫d       或    ⚫b            ⚫d
              ╱                   ╲          ╱   ╲
            🔴b                    🔴d      🔴b    🔴f

                （3-节点有两种表示）      （4-节点只有一种）

于是红黑树的五条规则全部有了来历：

规则	在 2-3-4 树中的含义
① 每个节点非红即黑	红 = “与父节点同属一个 2-3-4 节点”
② 根是黑色	根所在的 2-3-4 节点的代表
③ 所有叶子（nil 哨兵）是黑色	便于统一处理
④ 红节点的孩子必须是黑色（无连续红）	一个 2-3-4 节点最多 3 个键，即最多 2 条红边，且不能串成链
⑤ 从任一节点到其所有后代叶子的路径上，黑节点数相同	⭐ 对应"所有叶子同深度"——黑节点数就是 2-3-4 树的高度

⭐ 规则 ⑤ 是全部的核心，其他四条都是为它服务的。 它保证了树的"2-3-4 视角高度"是完美平衡的，而红节点只是在这个骨架上局部地多插了一层。

⭐ 高度定理：h ≤ 2 log₂(n+1)

定义：节点 x 的黑高（black-height） bh(x) = 从 x 到任一后代叶子路径上的黑节点数（不含 x 本身）。由规则 ⑤ 这是良定义的。

引理：以 x 为根的子树至少有 2^{bh(x)} − 1 个内部节点。

证明（对高度归纳）：x 是叶子时 bh = 0，节点数 0 = 2⁰−1 ✓。否则 x 的每个孩子的黑高是 bh(x) 或 bh(x)−1，由归纳假设各至少有 2^{bh(x)−1} − 1 个节点，故

节点数 ≥ 2(2^{bh(x)−1} − 1) + 1 = 2^{bh(x)} − 1                     ∎

定理证明：由规则 ④，从根到叶的路径上红节点数 ≤ 黑节点数，故 bh(root) ≥ h/2。代入引理：

n ≥ 2^{h/2} − 1
⟹ h ≤ 2 log₂(n + 1)                                                ∎

对比 AVL 的 1.44 log₂ n：红黑树最多高一倍，AVL 最多高 44%。红黑树更松 ⟹ 修复代价更低 ⟹ 修改更快，但查找稍慢。

三、插入的三种修复情形

新节点总是染成红色插入。为什么？因为插红色不会破坏规则 ⑤（黑高不变），只可能破坏规则 ④（连续红）——破坏一条比破坏两条容易修。

设新节点为 z，其父为 p，祖父为 g，叔叔为 u。若 p 是黑色则无事发生。若 p 是红色，分三种情形：

情形 1：叔叔 u 是红色  ⟹  重染色（不旋转），把问题上移两层
        ⚫g                     🔴g  ← 变红，可能与它的父冲突，递归向上
       ╱   ╲                   ╱   ╲
     🔴p    🔴u      ⟹        ⚫p    ⚫u
     ╱                        ╱
   🔴z                      🔴z

情形 2：叔叔黑，z 是"内侧"孩子  ⟹  旋转 p，转成情形 3
        ⚫g                    ⚫g
       ╱   ╲                 ╱   ╲
     🔴p    ⚫u    左旋 p    🔴z    ⚫u
       ╲            ⟹       ╱
        🔴z                🔴p

情形 3：叔叔黑，z 是"外侧"孩子  ⟹  旋转 g + 重染色，结束
        ⚫g                    ⚫p
       ╱   ╲    右旋 g       ╱   ╲
     🔴p    ⚫u   + 换色    🔴z    🔴g
     ╱          ⟹                   ╲
   🔴z                                ⚫u

⭐ 用 2-3-4 树的语言重述这三种情形，它们立刻变得直观：

情形 1 = 要插入的 2-3-4 节点已是 4-节点 ⟹ 分裂它，中间键升到父节点（这就是"把问题上移两层"）。
情形 2、3 = 要插入的是 2-节点或 3-节点 ⟹ 就地吸收，变成 3-节点或 4-节点，不需要向上传播。

修复代价：情形 1 可能一路向上传播 O(log n) 次重染色，但旋转最多 2 次（只在情形 2、3 发生，且它们直接终止循环）。

	AVL	红黑树
插入旋转	≤ 2	≤ 2
删除旋转	O(log n)	≤ 3
重染色	—	O(log n)（但只是改一个 bit）

⭐ 红黑树的核心优势就在"删除旋转 ≤ 3"这一行。 重染色只是写一个位，比旋转（改多个指针、破坏缓存、若有增强信息还要重算）便宜得多。因此删除密集的负载首选红黑树。

四、左倾红黑树：一个能写对的实现

标准红黑树的删除有六七种情形，是公认最难正确实现的经典数据结构之一。Sedgewick 的左倾红黑树（LLRB） 通过加一条约束大幅简化：

额外约束：红链接只能是左链接（即 3-节点只允许一种表示）。

const (
    red   = true
    black = false
)

type Node struct {
    Key         int
    Val         any
    Left, Right *Node
    Color       bool
    Size        int
}

func isRed(x *Node) bool {
    return x != nil && x.Color == red
}

func rotateLeft(h *Node) *Node { // 把右倾的红链接转成左倾
    x := h.Right
    h.Right = x.Left
    x.Left = h
    x.Color, h.Color = h.Color, red
    return x
}

func rotateRight(h *Node) *Node {
    x := h.Left
    h.Left = x.Right
    x.Right = h
    x.Color, h.Color = h.Color, red
    return x
}

func flipColors(h *Node) { // 4-节点分裂：中间键升到父节点
    h.Color = red
    h.Left.Color = black
    h.Right.Color = black
}

func insert(h *Node, k int, v any) *Node {
    if h == nil {
        return &Node{Key: k, Val: v, Color: red} // 新节点总是红色
    }
    switch {
    case k < h.Key:
        h.Left = insert(h.Left, k, v)
    case k > h.Key:
        h.Right = insert(h.Right, k, v)
    default:
        h.Val = v
    }

    // ⭐ 三行修复，顺序不可交换
    if isRed(h.Right) && !isRed(h.Left) {
        h = rotateLeft(h) // 右倾红链接 → 左倾
    }
    if isRed(h.Left) && isRed(h.Left.Left) {
        h = rotateRight(h) // 连续两个左红 → 平衡成 4-节点
    }
    if isRed(h.Left) && isRed(h.Right) {
        flipColors(h) // 4-节点 → 分裂
    }
    return h
}

⭐ 整个插入的修复逻辑只有三个 if，且顺序有严格的意义：先把红链接摆正，再处理连续红，最后分裂满节点。这段代码是"用不变式换实现复杂度"的经典范例——多加一条约束（红链接必须左倾），换来了代码量减少 80%。

⚠️ 代价：LLRB 的删除仍然需要 moveRedLeft / moveRedRight 等辅助操作，比插入复杂得多；而且左倾约束让树略高于标准红黑树。

五、真实世界的红黑树

系统	用途
Linux CFS 调度器	按虚拟运行时间排序的可运行进程队列
Linux 内核 `rbtree`	虚拟内存区域（VMA）、epoll 事件、I/O 调度、ext3/4 目录索引
C++ STL	`std::map` / `std::set` / `std::multimap`
Java	`TreeMap` / `TreeSet`；`HashMap` 单桶超 8 个元素时转红黑树（第 7 讲）
nginx	定时器管理

⭐ Linux 调度器的选择很有代表性：进程队列是极端修改密集的——每次时间片结束都要取出最小、更新 vruntime、重新插入。红黑树"删除只需 ≤ 3 次旋转"的性质在这里价值巨大，而查找变慢一点无关紧要（调度器只关心最小值，且内核额外缓存了最左节点指针，取最小是 O(1)）。

Go 为什么没有内建有序 map？ Go 团队的立场是保持标准库精简，且大多数场景 map + 排序切片就够了。需要有序结构时常用 github.com/google/btree、github.com/tidwall/btree（B 树）或跳表实现——注意大家选的通常不是红黑树，而是 B 树，原因见第 18 讲。

六、平衡树全景对比

	AVL	红黑树	B 树（17）	跳表（18）	Treap
高度	1.44 log n	2 log n	log_B n	期望 log n	期望 log n
查找	最坏 O(log n)	最坏 O(log n)	最坏 O(log n)	期望 O(log n)	期望 O(log n)
插入旋转	≤ 2	≤ 2	—	—	O(1) 期望
删除旋转	O(log n)	≤ 3	—	—	O(1) 期望
每节点开销	高度/2 bit	1 bit	键数组	层数指针	优先级
实现难度	中	高	中	低	低
并发友好	差	差	中	好	中
缓存友好	差	差	优	中	差

⭐ 一条实用建议：如果你在写业务代码而需要一个有序结构，优先考虑 B 树或跳表，而不是红黑树。前两者更容易写对、缓存表现更好，而红黑树的理论优势在大多数场景里体现不出来。红黑树的位置是内核和标准库——那里有人已经把它写对了，你直接用就好。

随堂自测

用 2-3-4 树的语言解释红黑树的五条规则，特别是规则 ④ 和 ⑤ 各对应什么。
2-3-4 树的高度界是什么？为什么"所有叶子同深度"能一直保持？
定义黑高，证明 以 x 为根的子树至少有 2^{bh(x)} − 1 个内部节点。
由上一题推出 h ≤ 2 log₂(n+1)。这一步用到规则 ④ 的哪一点？
新节点为什么总是插入为红色而不是黑色？
用 2-3-4 树重述插入修复的三种情形，说明为什么情形 1 需要向上传播而情形 2、3 不需要。
为什么红黑树删除只要 ≤ 3 次旋转，而 AVL 要 O(log n) 次？这为什么让 Linux 调度器选择红黑树？
左倾红黑树加了什么额外约束？它换来了什么、付出了什么？
手工执行 LLRB 依次插入 [S, E, A, R, C, H]，画出每步的树与颜色。
你要在业务代码里实现一个有序 map，为什么通常不该选红黑树？

一、先理解 2-3-4 树#

插入：分裂 4-节点#

二、红黑树 = 2-3-4 树的二叉表示#

⭐ 高度定理：h ≤ 2 log₂(n+1)#

三、插入的三种修复情形#

四、左倾红黑树：一个能写对的实现#

五、真实世界的红黑树#

六、平衡树全景对比#

随堂自测#