引言 (Introduction)
上一篇我们学习了 AVL 树，它通过严格的平衡因子（$|bf| \le 1$）保证了树高始终接近 $\log N$。但在工程实践中，被广泛采用的反而是另一种自平衡 BST——红黑树（Red-Black Tree）。Java 的 TreeMap/TreeSet、C++ 的 std::map/std::set、Linux 内核的 CFS 调度器，底层都是红黑树。
红黑树放弃了一部分严格平衡性，换取了更少的旋转次数：AVL 树在最坏情况下每次插入可能需要 $O(\log N)$ 次旋转，而红黑树最多只需要 $2$ 次。这使得红黑树在写密集场景下更具优势。
本文作为系列第五篇，在 AVL 树的基础上深入红黑树的原理与实现。
1. 五大性质与数据结构
一棵合法的红黑树必须同时满足以下五大性质：
- 节点颜色：每个节点要么是红色，要么是黑色。
- 根节点：根节点总是黑色。
- 叶子节点：所有叶子节点（NIL/空节点）都是黑色。
- 红色约束：红色节点的两个子节点必须是黑色（即不允许出现连续的红色）。
- 黑色高度：从任意节点到其所有后代叶子节点的路径上，包含相同数量的黑色节点。
推论：性质 4 和 5 共同保证了不存在一条路径的长度超过另一条路径的两倍，即树是近似平衡的。最短路径（全黑）与最长路径（红黑相间）的长度比至多为 $1:2$。
from enum import Enum
from typing import Optional
class Color(Enum):
RED = 0
BLACK = 1
class RBNode:
"""红黑树节点定义"""
def __init__(self, val: int):
self.val = val
self.left: Optional['RBNode'] = None
self.right: Optional['RBNode'] = None
self.parent: Optional['RBNode'] = None
self.color: Color = Color.RED # 新插入节点始终为红色
为什么新节点是红色？ 插入红色节点不会破坏性质 5（黑色高度不变），最多只可能违反性质 4（插入位置的父节点也是红色）。这比插入黑色节点（直接破坏性质 5，修复代价高得多）更容易处理。
2. 旋转操作（含 parent 指针维护）
红黑树的旋转与 AVL 旋转的结构一致，但额外需要维护 parent 指针。
def _rotate_left(self, root: RBNode, x: RBNode) -> RBNode:
"""对 x 执行左旋，返回新的局部根"""
y = x.right
assert y is not None
# 1. y 的左子树接管给 x 的右边
x.right = y.left
if y.left:
y.left.parent = x
# 2. y 继承 x 的 parent 关系
y.parent = x.parent
if not x.parent:
root = y # x 原为整棵树根，y 成为新根
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
# 3. x 成为 y 的左孩子
y.left = x
x.parent = y
return root
def _rotate_right(self, root: RBNode, y: RBNode) -> RBNode:
"""对 y 执行右旋，返回新的局部根"""
x = y.left
assert x is not None
# 对称操作
y.left = x.right
if x.right:
x.right.parent = y
x.parent = y.parent
if not y.parent:
root = x
elif y == y.parent.left:
y.parent.left = x
else:
y.parent.right = x
x.right = y
y.parent = x
return root
3. 插入操作与修复算法
3.1 标准 BST 插入
首先执行与普通 BST 完全相同的插入，将新节点染成红色：
def insert(self, val: int) -> None:
"""向红黑树插入值 val"""
node = RBNode(val)
# 标准 BST 插入
parent: Optional[RBNode] = None
curr = self.root
while curr:
parent = curr
if val < curr.val:
curr = curr.left
elif val > curr.val:
curr = curr.right
else:
return # 重复值忽略
node.parent = parent
if not parent:
self.root = node
elif val < parent.val:
parent.left = node
else:
parent.right = node
# 插入修复
self.root = self._insert_fixup(self.root, node)
self.root.color = Color.BLACK # 根始终为黑色
3.2 插入修复：六种 Case
修复的触发条件是父节点为红色（违反了性质 4）。我们用 z 表示当前关注的节点（初始为刚插入的节点），核心判断依据是叔叔节点 u（父节点的兄弟）的颜色。
前置定义：设 p = z.parent，g = p.parent（爷爷节点），u = p 是 g.left 则 u = g.right，反之亦然。
g(BLACK)
/ \
p(RED) u(?)
/
z(RED)
Case 1：叔叔是红色 —— 变色上推
将父节点和叔叔染黑，爷爷染红，然后把关注点 z 上移到爷爷节点。这相当于把红色「推」向根的方向。
g(BLACK) g(RED)
/ \ / \
p(RED) u(RED) --> p(BLACK) u(BLACK)
/ /
z(RED) z(RED)
Case 2：叔叔是黑色 + z 是父节点的内侧孩子 —— 旋转成直线
当 z 和 p 形成三角形（即 p 是 g 的左孩子，但 z 是 p 的右孩子），先对 p 旋转，将 z 拉直。这一步骤将问题转化为 Case 3。
g(BLACK) g(BLACK)
/ /
p(RED) --> z(RED)
\ /
z(RED) p(RED)
Case 3：叔叔是黑色 + z 是父节点的外侧孩子 —— 旋转+变色
当 z 和 p 在一条直线上（即 p 是 g 的左孩子，z 也是 p 的左孩子），对 g 做一次右旋，然后将 p 染黑、g 染红。此时整棵树恢复合法。
g(BLACK) p(BLACK)
/ \ / \
p(RED) u(BLACK) --> z(RED) g(RED)
/ \
z(RED) u(BLACK)
对称情况：上述描述假设 p 是 g 的左孩子。当 p 是右孩子时，Case 2 和 Case 3 的方向（左/右）完全镜像。
3.3 修复代码实现
def _insert_fixup(self, root: RBNode, z: RBNode) -> RBNode:
"""插入修复：维持红黑树五大性质"""
while z.parent and z.parent.color == Color.RED:
p = z.parent
g = p.parent # 一定存在（根是黑色的，p 为红不可能是根）
if p == g.left:
u = g.right # 叔叔节点
# ---- Case 1: 叔叔是红色 ----
if u and u.color == Color.RED:
p.color = Color.BLACK
u.color = Color.BLACK
g.color = Color.RED
z = g # 上推
else:
# ---- Case 2: z 是父节点的内侧孩子 (LR) ----
if z == p.right:
root = self._rotate_left(root, p)
z = p # z 和 p 已经互换
p = z.parent
# ---- Case 3: z 是父节点的外侧孩子 (LL) ----
p.color = Color.BLACK
g.color = Color.RED
root = self._rotate_right(root, g)
else: # 对称：p == g.right
u = g.left
# ---- Case 1 (对称): 叔叔是红色 ----
if u and u.color == Color.RED:
p.color = Color.BLACK
u.color = Color.BLACK
g.color = Color.RED
z = g
else:
# ---- Case 2 (对称): z 是父节点的内侧孩子 (RL) ----
if z == p.left:
root = self._rotate_right(root, p)
z = p
p = z.parent
# ---- Case 3 (对称): z 是父节点的外侧孩子 (RR) ----
p.color = Color.BLACK
g.color = Color.RED
root = self._rotate_left(root, g)
root.color = Color.BLACK
return root
复杂度分析：
- 每次修复只有 Case 1 会继续循环（
z上移两层），其他 case 最多执行一次旋转即可终止。 - 旋转变色均为 $O(1)$，整棵树的插入总复杂度为 $O(\log N)$。
- 插入操作至多进行 2 次旋转（Case 2 → Case 3 各旋转一次）。
4. AVL 与红黑树的工程对比
| 对比维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡条件 | 严格：$\lvert bf \rvert \le 1$ | 宽松：最长路径 $\le 2 \times$ 最短路径 |
| 树高 | 更低（约 $1.44 \log_2 N$） | 略高（约 $2 \log_2 N$） |
| 查找性能 | 略优（树更矮） | 稍逊 |
| 插入旋转次数 | 最多 $O(\log N)$ 次 | 最多 2 次 |
| 适用场景 | 读密集（数据库索引） | 写密集（Map/Set 实现、调度器） |
工程实例：
- Java
TreeMap：基于红黑树实现的有序映射，put/get/remove均为 $O(\log N)$。 - C++
std::map：同样采用红黑树，保证迭代器在中序遍历下有序递增。 - Linux CFS 调度器：内核用红黑树按
vruntime组织可运行进程，每次调度取最左侧节点。
5. LeetCode 实战应用
5.1 #220 存在重复元素 III (Contains Duplicate III)
题目描述：给定数组，判断是否存在两个下标 $i \neq j$，满足 $|i-j| \le k$ 且 $|nums[i]-nums[j]| \le t$。
from sortedcontainers import SortedList # 底层为红黑树
def contains_nearby_almost_duplicate(nums: List[int], k: int, t: int) -> bool:
"""LeetCode 220"""
window = SortedList()
for i, val in enumerate(nums):
# 维护大小为 k 的滑动窗口
if i > k:
window.remove(nums[i - k - 1])
# 在有序窗口中二分查找 [val - t, val + t] 内的元素
pos = window.bisect_left(val - t)
if pos < len(window) and window[pos] <= val + t:
return True
window.add(val)
return False
核心思想：利用红黑树的有序性和 $O(\log N)$ 的增删查找，维护大小为 $k$ 的滑动窗口。bisect_left 找到第一个 $\ge$ val - t 的元素，再判断是否 $\le$ val + t。
5.2 #731 我的日程安排表 II (My Calendar II)
题目描述：实现日历，允许最多两次预定重叠（即不允许三重预定）。
利用有序字典（底层红黑树）维护每个时刻的预定数变化量：
from sortedcontainers import SortedDict
class MyCalendarTwo:
"""LeetCode 731: 区间预订，禁止三重重叠"""
def __init__(self):
self.delta = SortedDict() # 时刻 -> 预定数变化量
def book(self, start: int, end: int) -> bool:
# 临时增加预定
self.delta[start] = self.delta.get(start, 0) + 1
self.delta[end] = self.delta.get(end, 0) - 1
active = 0
for time in self.delta:
active += self.delta[time]
if active >= 3: # 发现三重预定，回滚
self.delta[start] -= 1
self.delta[end] += 1
return False
return True
核心思想：delta[start] += 1 表示从此开始新增一个预定，delta[end] -= 1 表示从此结束。扫描时 active 累计即为当前活跃预定数，若 $\ge 3$ 说明三重重叠。
5.3 #450 删除二叉搜索树中的节点 (Delete Node in BST)
题目描述：给定 BST 和一个值 key，删除值为 key 的节点并返回新树。
def delete_node(root: Optional[RBNode], key: int) -> Optional[RBNode]:
"""LeetCode 450: BST 删除节点"""
if not root:
return None
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
# 找到目标节点
if not root.left: # 只有右子树
return root.right
if not root.right: # 只有左子树
return root.left
# 两个孩子：用右子树的最小节点（后继）替换
succ = root.right
while succ.left:
succ = succ.left
root.val = succ.val
root.right = delete_node(root.right, succ.val)
return root
与红黑树删除的关系：红黑树的删除操作比插入更为复杂，因为它可能破坏性质 5（黑色高度），需要额外的双黑节点修复过程。受限于篇幅本文不做展开，但理解 BST 删除是掌握红黑树删除的第一步。
结论 (Conclusion)
红黑树通过「颜色约束 + 旋转 + 变色」三个核心手段，在牺牲少量平衡性的同时大幅减少了旋转次数（至多 2 次），成为现代工程实现中最广泛采用的平衡二叉搜索树。从 AVL 的严格平衡到红黑树的近似平衡，体现的是「理论与实践的不同侧重点」——AVL 追求理论最优查询，红黑树追求更均衡的读写性能。下一篇我们将跳出严格二叉搜索树的框架，进入线段树的区间查询世界。