红黑树
二叉搜索树（BST）看起来很美：中序遍历有序，查询、插入、删除都是 $O(h)$，其中 $h$ 是树高。理想情况下 $h = O(\log n)$，一切都很高效。
但现实很骨感。考虑按顺序插入 1, 2, 3, 4, 5：
graph TD 1 --> 2 2 --> 3 3 --> 4 4 --> 5 1 --> N1["NIL"] 2 --> N2["NIL"] 3 --> N3["NIL"] 4 --> N4["NIL"] 5 --> N5["NIL"] 5 --> N6["NIL"] style 1 fill:#444,color:#fff style 2 fill:#444,color:#fff style 3 fill:#444,color:#fff style 4 fill:#444,color:#fff style 5 fill:#444,color:#fff
一条链！退化成了链表，所有操作都变成 $O(n)$。这就是 BST 的平衡问题——它的性能完全取决于输入数据的顺序。
AVL 树是一种方案（严格平衡，左右子树高度差 ≤ 1），但它过于保守——每次插入删除可能触发大量旋转。红黑树走了另一条路：不追求完美平衡，只保证"近似平衡"，换取更少的维护代价。
很多人学红黑树时被各种 Case 搞得头晕眼花——什么时候左旋、什么时候右旋、什么时候变色？死记硬背痛苦且低效。理解红黑树最好的方式，是认识到一个关键事实：
什么是 2-3-4 树？
2-3-4 树是一种 B 树（阶数 4），它的每个节点可以有 1~3 个键和 2~4 个子节点：
| 节点类型 | 键数 | 子节点数 | 示例 |
|---|---|---|---|
| 2-节点 | 1 | 2 | [5] |
| 3-节点 | 2 | 3 | [3, 7] |
| 4-节点 | 3 | 4 | [2, 5, 8] |
2-3-4 树是完美平衡的：所有叶子节点都在同一层。这使得它的所有操作都是 $O(\log n)$。但 2-3-4 树的实现很麻烦——需要处理可变长度的键数组和子节点数组。红黑树就是用"着色"技巧把 2-3-4 树编码成二叉树。
节点映射关系
2-3-4 树的三种节点，在红黑树中各有对应的二叉树形态：
| 2-3-4 树节点 | 红黑树表示 | 规则 |
|---|---|---|
2-节点 [k] | 一个黑色节点 k | 直接对应 |
3-节点 [a, b] | 黑色节点 + 红色子节点（两种排列） | 红链"粘合"两个键 |
4-节点 [a, b, c] | 黑色节点 + 两个红色子节点 | 两条红链粘合三个键 |
以 3-节点为例：[3, 7] 可以表示为"3（黑）→ 7（红，右子）"或"7（黑）→ 3（红，左子）"——这就是红黑树中红色节点可以"左倾"或"右倾"的来源。左倾红黑树（LLRB）强制红色链接只出现在左侧，使对应关系变为 1:1。
用 2-3-4 树理解红黑树性质
红黑树的性质在 2-3-4 树视角下变得极其自然：
· 性质 3（红节点不能有红子节点）→ 2-3-4 树最多是 4-节点，不可能有 5-节点
· 性质 5（所有路径黑高相同）→ 2-3-4 树所有叶子在同一层，黑节点 = 2-3-4 树的节点
红黑树是一棵带颜色标记的二叉搜索树，每个节点被染成红色或黑色。它必须同时满足以下五条性质：
| # | 性质 | 直觉含义 |
|---|---|---|
| 1 | 每个节点是红色或黑色 | 颜色是二值的，没有灰色地带 |
| 2 | 根节点是黑色 | 树的起点必须是"稳重的"颜色 |
| 3 | 所有 NIL 叶子（哨兵）是黑色 | 叶子节点统一为黑，这是"底部约束" |
| 4 | 红色节点的两个子节点必须是黑色 | 不能有连续的红节点（核心限制） |
| 5 | 从任一节点到其所有后代 NIL 的路径，黑色节点数量相同 | "黑高"一致，这是平衡的根源 |
NIL 哨兵节点
红黑树中，所有"空指针"都被替换为一个统一的 NIL 哨兵节点（NIL），它是黑色的。实际实现中，这个哨兵可以是一个共享的全局对象。引入哨兵的目的是让每条"到叶子的路径"都有明确的终点，简化性质 5 的表述和代码逻辑。
为什么这五条性质能保证平衡？关键在于性质 4 和性质 5 的配合：
性质 4 告诉我们：一条路径上不可能连续出现两个红节点，所以红色节点最多只能"穿插"在黑色节点之间。这意味着从根到最远叶子的路径上，红色节点数 ≤ 黑色节点数。
性质 5 告诉我们：所有路径的黑高（black-height，记为 $bh$）相同。
合在一起：最长路径 ≤ $2 \times bh$，最短路径 ≥ $bh$。而 $bh \geq h/2$，所以：
因此 $h \leq 2\log_2(n+1) = O(\log n)$。五条性质共同锁死了树高的上界。
旋转（Rotation）是红黑树维护平衡的基本操作，所有插入和删除的修复都通过旋转完成。旋转分为左旋和右旋，它们互为逆操作。
左旋（Left Rotate）
左旋以节点 x 为支点，将其右子节点 y 提升到 x 的位置，x 变为 y 的左子节点。
graph TD
subgraph Before["旋转前"]
A1["x"] --> B1["α"]
A1 --> C1["y"]
C1 --> D1["β"]
C1 --> E1["γ"]
end
graph TD
subgraph After["旋转后"]
A2["y"] --> B2["x"]
A2 --> C2["γ"]
B2 --> D2["α"]
B2 --> E2["β"]
end
右旋（Right Rotate）
右旋是左旋的镜像操作——以节点 y 为支点，将其左子节点 x 提升到 y 的位置。从 2-3-4 树的视角来看，左旋和右旋都是在重新分配同一个多键节点内部的键的排列方式。
红黑树的插入分为两步：标准 BST 插入 + 颜色修复。
Step 1：BST 插入
和普通 BST 一样，找到新节点应该插入的位置。新节点默认染成红色。
为什么新节点染红？
如果染黑，插入后必然违反性质 5（黑高变化）。染红只可能违反性质 4（父节点也是红色），而性质 4 的修复相对容易，是局部操作。从 2-3-4 树的角度看：插入红节点 = 向 2-3-4 树的一个节点中添加一个键，这可能导致节点"溢出"（overflow），需要分裂。
Step 2：修复 Insert Fixup
插入后，如果新节点 z 的父节点是红色，就违反了性质 4（对应 2-3-4 树中出现了 4-节点溢出）。修复的核心思想是：通过重新着色和旋转，把"溢出"向上传播，直到消解。
设 z 的父节点为 p，叔节点为 u，祖父节点为 g。根据 u 的颜色和 z 的位置，分三种情况：
| Case | 条件 | 2-3-4 树视角 | 红黑树操作 |
|---|---|---|---|
| 1 | 叔 u 红 | 4-节点分裂：中间键上移 | p、u 染黑，g 染红；z ← g |
| 2 | 叔 u 黑，z 是 p 的"弯"子 | 3-节点内部调整方向 | 旋转 p，转化为 Case 3 |
| 3 | 叔 u 黑，z 是 p 的"直"子 | 3-节点提升 | p 染黑，g 染红；旋转 g |
用流程图来直观展示修复的决策路径：
graph TD
A["z 的父节点 p 是红色？"] -->|"否"| DONE["无需修复"]
A -->|"是"| B{"叔节点 u 的颜色？"}
B -->|"红色"| C["Case 1: 4-节点分裂
p、u 染黑，g 染红
z ← g，继续循环"]
B -->|"黑色"| D{"z 和 p 方向一致？"}
D -->|"不一致（弯折）"| E["Case 2: 旋转对齐方向
转化为 Case 3"]
D -->|"一致（直线）"| F["Case 3: p 染黑，g 染红
旋转 g，修复完成"]
E --> F
C --> A
style C fill:#e74c3c,color:#fff
style E fill:#f39c12,color:#fff
style F fill:#27ae60,color:#fff
2-3-4 树视角详解
Case 1：叔节点是红色（4-节点分裂）
父 p 和叔 u 都是红色，意味着祖父 g、p、u 构成了一个 4-节点（三个键粘合在一起）。现在又插入了一个红节点 z，形成 5-节点——溢出了！解决方式是把中间键（g）上移，左右两个键各自独立：p 和 u 变成黑色（独立节点），g 变红色（上移）。然后以 g 为新的 z 继续检查——因为 g 变红后可能又和它的父节点冲突。
Case 2 → Case 3：方向对齐（3-节点内部调整）
叔 u 是黑色，说明 2-3-4 树中 z、p 构成的 3-节点要和 g 合并。但如果 z 和 p 的方向不一致（比如 p 是 g 的左子，但 z 是 p 的右子），就需要先旋转对齐——在 2-3-4 树视角下，这只是在重新排列 3-节点内部键的顺序。
Case 3：终极修复（3-节点提升）
方向对齐后，一次旋转就能让 p 提升为新的子树根，g 降级为 p 的子节点。颜色交换后，性质 4 和性质 5 同时恢复。
复杂度分析
插入修复中：
· Case 1 会让 z 上移两层（到祖父），最多循环 $O(\log n)$ 次。
· Case 2 一次旋转就转化为 Case 3。
· Case 3 一次旋转就彻底结束。
因此，插入修复最多 $O(\log n)$ 次重着色，最多 2 次旋转。总时间 $O(\log n)$。
删除是红黑树中最复杂的操作。理解它的关键是抓住一条线索：删除一个节点后，什么性质可能被破坏？
Step 1：BST 删除
和普通 BST 类似，先定位待删除节点 z，根据子节点数分三种情况：
| z 的子节点数 | 操作 | 实际被移除的节点 |
|---|---|---|
| 无子节点（叶子） | 直接删除 | z 本身 |
| 一个子节点 | 用子节点替代 z | z 本身 |
| 两个子节点 | 找到中序后继 y，用 y 替代 z | 后继 y（至多有一个右子） |
统一模型：记实际被移除的节点为 y，替代 y 位置的节点为 x。我们需要关注的是 y 的颜色：
· 如果 y 是红色，删除后不违反任何性质。无需修复。
· 如果 y 是黑色，删除可能导致性质 4 或 5 被破坏，需要调用 delete_fixup(x)。
黑色节点被删除的后果
删除黑色节点 y 会带来两个问题：
1. 性质 5：经过 y 的所有路径少了一个黑节点，黑高不一致（对应 2-3-4 树中的下溢）。
2. 性质 4：如果 y 的替代者 x 和 y 的父节点都是红色，会出现连续红节点。
修复的核心思路是给 x 额外"加一层黑色"（称为"双重黑"），然后通过旋转和重着色将这层多余的黑色消化掉。
Step 2：修复 Delete Fixup
删除修复处理节点 x（它带有"额外的黑色"）。设 w 是 x 的兄弟节点。修复分为四种情况：
| Case | 条件 | 2-3-4 树视角 | 操作 |
|---|---|---|---|
| 1 | w 是红色 | 兄弟是 3-节点，先"旋转展开" | w 染黑，p 染红；旋转，进入 2/3/4 |
| 2 | w 黑，w 两个子都黑 | 兄弟是 2-节点，借不到，合并 | w 染红，x ← x.parent |
| 3 | w 黑，近侄子红、远侄子黑 | 兄弟是 3-节点，先调整方向 | 调整颜色，旋转 w，转化为 Case 4 |
| 4 | w 黑，远侄子红 | 兄弟有富余键，借键 | 交换颜色，旋转 p，结束 |
graph TD
START["x 带有额外黑色"] --> A{"兄弟 w 的颜色？"}
A -->|"红色"| B["Case 1: 展开兄弟
w 染黑，p 染红
旋转，w ← 新兄弟"]
A -->|"黑色"| C{"w 的子节点颜色？"}
C -->|"两个都黑"| D["Case 2: 合并
w 染红
x ← x.parent，继续"]
C -->|"远侄子黑，近侄子红"| E["Case 3: 调整方向
转化为 Case 4"]
C -->|"远侄子红"| F["Case 4: 借键
交换颜色，旋转 p → 结束"]
B --> C
E --> F
style B fill:#e74c3c,color:#fff
style D fill:#f39c12,color:#fff
style E fill:#3498db,color:#fff
style F fill:#27ae60,color:#fff
2-3-4 树视角详解
从 2-3-4 树的角度理解删除修复，整个逻辑变得非常清晰：删除黑色节点 = 2-3-4 树中从 2-节点删除键，导致该节点变空（下溢）。此时有两种策略：
· 借键（Case 3/4）：如果兄弟节点有富余键（是 3-节点或 4-节点），就向它借一个。借键的过程是：父节点的一个键下移到被删节点，兄弟节点的一个键上移到父节点。Case 4 就是借键的最终形态。
· 合并（Case 2）：如果兄弟也是 2-节点（没有富余），那只能"合并"——把父节点的一个键拉下来和兄弟合并成 3-节点。但这会让父节点少一个键，可能引发父节点的下溢——所以需要以父节点为新的 x 继续向上修复。
Case 1 只是一个"预处理"步骤，把红色兄弟旋转成黑色兄弟，让后续的借键/合并操作可以正确执行。
复杂度分析
删除修复中：
· Case 1 一次旋转后转化为 Case 2/3/4。
· Case 2 让 x 上移一层，最多循环 $O(\log n)$ 次。
· Case 3 一次旋转后转化为 Case 4。
· Case 4 一次旋转后结束。
因此，删除修复最多 $O(\log n)$ 次重着色，最多 3 次旋转。总时间 $O(\log n)$。
| 操作 | 时间复杂度 | 旋转次数 | 重着色次数 |
|---|---|---|---|
| 查询（Search） | $O(\log n)$ | 0 | 0 |
| 前驱/后继（Min/Max） | $O(\log n)$ | 0 | 0 |
| 插入（Insert） | $O(\log n)$ | ≤ 2 | $O(\log n)$ |
| 删除（Delete） | $O(\log n)$ | ≤ 3 | $O(\log n)$ |
对比 AVL 树：
| 特性 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡标准 | 宽松：最长路径 ≤ 2× 最短路径 | 严格：左右子树高度差 ≤ 1 |
| 查询性能 | $O(\log n)$，常数因子略大 | $O(\log n)$，常数因子更小 |
| 插入旋转 | ≤ 2 次 | $O(\log n)$ 次 |
| 删除旋转 | ≤ 3 次 | $O(\log n)$ 次 |
| 适用场景 | 写多读少（如标准库 map） | 读多写少（如数据库索引） |
以下是一个完整的红黑树 Python 实现，包含插入、删除、搜索和可视化输出。每个方法都带有详细注释，与上文讲解的 Case 一一对应。
查看完整 Python 代码
"""
Red-Black Tree — Python Implementation
=======================================
基于 CLRS《算法导论》第 13 章的标准实现。
"""
RED = True
BLACK = False
class NilNode:
"""NIL 哨兵节点：所有叶子指针统一指向此对象"""
def __init__(self):
self.color = BLACK
self.left = self.right = self.parent = None
NIL = NilNode()
class Node:
"""红黑树节点"""
__slots__ = ('key', 'color', 'left', 'right', 'parent')
def __init__(self, key, color=RED,
left=NIL, right=NIL, parent=NIL):
self.key = key
self.color = color
self.left = left
self.right = right
self.parent = parent
def __repr__(self):
c = 'R' if self.color == RED else 'B'
return f"{self.key}({c})"
class RedBlackTree:
"""红黑树：支持 insert / delete / search / inorder"""
def __init__(self):
self.root = NIL
# ── 搜索 ─────────────────────────────────────
def search(self, key):
"""标准 BST 搜索，O(log n)"""
x = self.root
while x is not NIL:
if key == x.key:
return x
x = x.left if key < x.key else x.right
return None
def minimum(self, x=None):
"""子树最小节点"""
if x is None:
x = self.root
while x.left is not NIL:
x = x.left
return x
# ── 旋转 ─────────────────────────────────────
def _left_rotate(self, x):
"""
左旋：以 x 为支点
x y
/ \ → / \
α y x γ
/ \ / \
β γ α β
"""
y = x.right
x.right = y.left # β 挂到 x 的右子
if y.left is not NIL:
y.left.parent = x
y.parent = x.parent # y 接管 x 的位置
if x.parent is NIL:
self.root = y
elif x is x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x # x 变为 y 的左子
x.parent = y
def _right_rotate(self, y):
"""右旋：左旋的镜像"""
x = y.left
y.left = x.right
if x.right is not NIL:
x.right.parent = y
x.parent = y.parent
if y.parent is NIL:
self.root = x
elif y is y.parent.right:
y.parent.right = x
else:
y.parent.left = x
x.right = y
y.parent = x
# ── 插入 ─────────────────────────────────────
def insert(self, key):
"""插入 key，O(log n)"""
z = Node(key)
# 标准 BST 插入
y = NIL
x = self.root
while x is not NIL:
y = x
x = x.left if z.key < x.key else x.right
z.parent = y
if y is NIL:
self.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
# 新节点默认红色，可能违反性质 4
self._insert_fixup(z)
def _insert_fixup(self, z):
"""
插入修复 — 3 种 Case
从 2-3-4 树视角：处理 4-节点溢出
"""
while z.parent.color == RED:
if z.parent is z.parent.parent.left:
# 父节点是祖父的左子
u = z.parent.parent.right # 叔节点
if u.color == RED:
# ── Case 1: 叔红 → 4-节点分裂 ──
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent # 上移两层
else:
if z is z.parent.right:
# ── Case 2: z 是"弯"子 → 对齐方向 ──
z = z.parent
self._left_rotate(z)
# ── Case 3: z 是"直"子 → 一次旋转搞定 ──
z.parent.color = BLACK
z.parent.parent.color = RED
self._right_rotate(z.parent.parent)
else:
# 镜像：父节点是祖父的右子
u = z.parent.parent.left
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z is z.parent.left:
z = z.parent
self._right_rotate(z)
z.parent.color = BLACK
z.parent.parent.color = RED
self._left_rotate(z.parent.parent)
self.root.color = BLACK # 确保根是黑色
# ── 删除 ─────────────────────────────────────
def delete(self, key):
"""删除 key，O(log n)"""
z = self.search(key)
if z is None:
return
y = z
y_original_color = y.color
if z.left is NIL:
x = z.right
self._transplant(z, z.right)
elif z.right is NIL:
x = z.left
self._transplant(z, z.left)
else:
# 两个子节点：找中序后继
y = self.minimum(z.right)
y_original_color = y.color
x = y.right
if y.parent is z:
x.parent = y # 处理 x == NIL
else:
self._transplant(y, y.right)
y.right = z.right
y.right.parent = y
self._transplant(z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == BLACK:
self._delete_fixup(x)
def _transplant(self, u, v):
"""用子树 v 替换子树 u"""
if u.parent is NIL:
self.root = v
elif u is u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
def _delete_fixup(self, x):
"""
删除修复 — 4 种 Case
从 2-3-4 树视角：处理 2-节点下溢（借键/合并）
"""
while x is not self.root and x.color == BLACK:
if x is x.parent.left:
w = x.parent.right # 兄弟
if w.color == RED:
# ── Case 1: 兄弟红 → 展开为黑兄弟 ──
w.color = BLACK
x.parent.color = RED
self._left_rotate(x.parent)
w = x.parent.right
if (w.left.color == BLACK and
w.right.color == BLACK):
# ── Case 2: 兄弟两子都黑 → 合并 ──
w.color = RED
x = x.parent
else:
if w.right.color == BLACK:
# ── Case 3: 远侄子黑 → 调整方向 ──
w.left.color = BLACK
w.color = RED
self._right_rotate(w)
w = x.parent.right
# ── Case 4: 远侄子红 → 借键，修复完成 ──
w.color = x.parent.color
x.parent.color = BLACK
w.right.color = BLACK
self._left_rotate(x.parent)
x = self.root # 终止循环
else:
# 镜像
w = x.parent.left
if w.color == RED:
w.color = BLACK
x.parent.color = RED
self._right_rotate(x.parent)
w = x.parent.left
if (w.right.color == BLACK and
w.left.color == BLACK):
w.color = RED
x = x.parent
else:
if w.left.color == BLACK:
w.right.color = BLACK
w.color = RED
self._left_rotate(w)
w = x.parent.left
w.color = x.parent.color
x.parent.color = BLACK
w.left.color = BLACK
self._right_rotate(x.parent)
x = self.root
x.color = BLACK
# ── 遍历 ─────────────────────────────────────
def inorder(self):
"""中序遍历，返回有序列表"""
result = []
def _walk(x):
if x is NIL:
return
_walk(x.left)
c = 'R' if x.color == RED else 'B'
result.append(f"{x.key}({c})")
_walk(x.right)
_walk(self.root)
return result
# ── 使用示例 ─────────────────────────────────────
if __name__ == "__main__":
rbt = RedBlackTree()
# 插入
for key in [7, 3, 18, 10, 22, 8, 11, 26]:
rbt.insert(key)
print("插入后中序:", " → ".join(rbt.inorder()))
# 输出: 3(B) → 7(R) → 8(R) → 10(B) → 11(R) → 18(B) → 22(B) → 26(R)
# 搜索
node = rbt.search(10)
print(f"搜索 10: {node}") # 10(B)
# 删除
rbt.delete(18)
print("删除 18 后:", " → ".join(rbt.inorder()))
这个实现的关键设计决策：
- NilNode 哨兵：用全局共享的
NIL对象替代None，简化边界条件判断 - 颜色用布尔值：
RED = True,BLACK = False，比枚举更轻量 - insert_fixup 和 delete_fixup：与上文讲解的 Case 一一对应，注释标注了每个分支对应的 Case
红黑树不是教科书中的纸上谈兵——它是工程实践中被使用最广泛的平衡搜索树之一。选择红黑树而非 AVL 树的核心原因是：红黑树的旋转次数有常数上界（插入 ≤ 2 次，删除 ≤ 3 次），这使得它在频繁修改的场景下性能更稳定。
| 系统 | 应用场景 | 为什么选红黑树？ |
|---|---|---|
| Linux 内核 | 完全公平调度器（CFS）、epoll、内存管理 | 需要 $O(\log n)$ 的插入/删除保证，旋转次数有上界 |
| C++ STL | std::map、std::set、std::multimap | 写操作频繁时，红黑树的修改代价低于 AVL |
| Java | TreeMap、TreeSet | 与 STL 同理；Java 8 的 HashMap 在哈希冲突严重时也会退化为红黑树 |
| Python | 某些第三方库（如 bintrees） | 内置的 dict 用哈希表，但有序映射场景需要红黑树 |
| 函数式编程 | 持久化数据结构（Haskell Data.Map） | 红黑树支持纯函数式实现（Okasaki, 1999），每次修改只影响 $O(\log n)$ 个节点 |
| 计算几何 | 线段扫除法、区间树 | 需要最坏情况 $O(\log n)$ 的查询和修改保证 |
Java HashMap 的退化优化
Java 8 对 HashMap 做了一个精妙的优化：当哈希桶中的链表长度超过阈值（默认 8）时，链表会自动转换为红黑树。这使得最坏情况下的查找从 $O(n)$ 改善到 $O(\log n)$。当元素减少到阈值以下时，又会退回链表。这个设计充分利用了红黑树"旋转次数有上界"的特性——频繁的插入删除不会导致过高的维护开销。
红黑树不是孤立存在的。它是更广泛的平衡搜索树族谱的一员：
graph TD BST["二叉搜索树"] --> AVL["AVL 树
(严格平衡)"] BST --> RBT["红黑树
(近似平衡)"] BST --> SPLAY["Splay 树
(自调整)"] BST --> TREAP["Treap
(随机化)"] RBT --> LLRBT["左倾红黑树
(Sedgewick 2008)"] RBT --> RBS["标准库实现
(STL/Java)"] BTree["B 树族"] --> B234["2-3-4 树
(红黑树等价)"] BTree --> BPlus["B+ 树
(数据库/文件系统)"] style BST fill:#555,color:#fff style RBT fill:#e74c3c,color:#fff style AVL fill:#27ae60,color:#fff style LLRBT fill:#3498db,color:#fff style B234 fill:#9b59b6,color:#fff
左倾红黑树（LLRB）是 Robert Sedgewick 在 2008 年提出的变体，强制红色链接只出现在左子节点上。虽然理论上旋转次数略多于标准红黑树，但实现简单得多——插入只需 33 行 Java 代码。LLRB 和 2-3 树（或 2-3-4 树）存在一一对应关系：红色链接对应 2-3 树中的"粘合"节点。本文正是利用了这个对应关系来帮助理解红黑树的操作。
在更宏观的视角下，B 树族（B 树、B+ 树、B* 树）可以看作红黑树在多路分支上的推广。一棵红黑树等价于一棵特殊的 2-3-4 树，每条红色链接将两个节点"粘合"为一个 3 节点或 4 节点。
历史脉络：1972 年 Bayer 发明了对称二叉 B 树（2-3-4 树的前身），1978 年 Guibas 和 Sedgewick 从中推导出红黑树。"红色"这个颜色选择据 Sedgewick 本人回忆，只是因为当时 Xerox PARC 的彩色激光打印机打出来的红色最好看。
参考来源
- Cormen, T. H. et al. Introduction to Algorithms (CLRS), 4th Ed., Chapter 13: Red-Black Trees
- Sedgewick, R. Algorithms, 4th Ed., Red-Black BSTs
- Wikipedia: Red–Black Tree
- OI Wiki: 红黑树
- MartinLwx: How to memorize the Red-black tree
- Stanford CS166: Balanced Trees, Part II