高级数据结构（二）：红黑树与伸展树
说实话，红黑树是我在工程中用到最多的平衡树结构。Linux内核的CFS调度器、STL的map和set、Java的TreeMap……底层全是它。我第一次接触红黑树时，觉得这玩意儿规则怎么这么多？后来真正在项目中调过几次bug，才明白每条规则背后都是血的教训。
今天咱们就把它掰开揉碎，讲清楚红黑树的核心概念、插入删除操作，再聊聊伸展树这个有意思的结构。
一、红黑树的概念与性质
红黑树本质上是一棵二叉搜索树，但每个节点多了一个颜色属性——红色或黑色。它通过颜色约束来保证树的平衡，说白了就是让树的高度控制在O(log n)级别。
红黑树必须满足以下五条性质：
- 节点非红即黑——每个节点要么红色，要么黑色。
- 根节点是黑色——这条很直观，根黑是基础。
- 叶子节点（NIL）是黑色——这里的叶子指的是空节点，不是我们通常说的叶子。
- 红色节点的子节点必须是黑色——也就是说，不能出现两个连续的红色节点。
- 从任一节点到其每个叶子的所有路径，包含相同数目的黑色节点——这条叫“黑高相等”，是红黑树平衡的核心。
核心理解：红黑树的平衡不是AVL那种严格的左右子树高度差≤1，而是一种“近似平衡”。它允许红色节点存在，但通过限制红色节点的分布，保证任何路径的长度不会超过最短路径的两倍。
我在项目中遇到过一个问题：一个同事用红黑树做内存管理，插入大量数据后查询性能突然下降。排查了半天，发现是插入时没有维护红黑树性质，导致树退化了。嗯，从那以后我每次写完插入操作，都会手动验证一下五条性质是否都满足。
二、红黑树的插入操作
红黑树的插入分两步：先按二叉搜索树的方式插入节点（默认红色），再通过旋转和变色修复平衡。
为什么新节点默认红色？你想想看，如果插入黑色节点，一定会破坏性质5（黑高相等），修复起来更麻烦。插入红色节点，只可能破坏性质4（不能有连续红色），修复范围更小。
插入后的修复分三种情况（假设新节点为N，父节点为P，祖父节点为G，叔叔节点为U）：
| 情况 | 描述 | 处理方式 |
|---|---|---|
| 情况1 | 叔叔U是红色 | 将P和U变黑，G变红，然后将G作为新N继续向上检查 |
| 情况2 | 叔叔U是黑色，且N是P的右孩子 | 对P左旋，转化为情况3 |
| 情况3 | 叔叔U是黑色，且N是P的左孩子 | 对G右旋，交换P和G的颜色 |
我个人的习惯是，把情况1看作“向上传递红色”，情况2和3看作“局部旋转修正”。这样记起来轻松很多。
// 红黑树插入修复伪代码
void rb_insert_fixup(Node *z) {
while (z->parent && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node *y = z->parent->parent->right; // 叔叔节点
if (y && y->color == RED) { // 情况1
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) { // 情况2
z = z->parent;
left_rotate(z);
} // 情况3
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(z->parent->parent);
}
} else {
// 对称处理（父节点是右孩子的情况）
// 代码逻辑与上面镜像对称
}
}
root->color = BLACK; // 确保根节点为黑色
}
避坑指南：我曾经在实现时忘了最后一行root->color = BLACK，结果根节点被染成红色，性质2被破坏。这个bug查了我两个小时——因为根节点红色在大多数测试用例中不会立即暴露问题，但一旦树旋转到特定形态，就会出大乱子。
三、红黑树的删除操作
删除比插入复杂得多。我当年学的时候，啃了好几遍才真正搞明白。说白了，删除的核心思路是：先按二叉搜索树的方式删除节点，如果删掉的是黑色节点，就会破坏性质5，需要修复。
删除修复的核心是处理“双黑”问题——当删除一个黑色节点后，我们用它的孩子顶替位置，并给这个孩子一个“额外的黑色”，让它变成“双黑”节点。修复过程就是把这个“额外的黑色”向上传递或消除。
删除修复的四种情况（假设X是当前“双黑”节点，W是X的兄弟节点）：
| 情况 | 描述 | 处理方式 |
|---|---|---|
| 情况1 | W是红色 | 将W变黑，父节点变红，对父节点左旋，更新W |
| 情况2 | W是黑色，且W的两个孩子都是黑色 | 将W变红，X上移到父节点 |
| 情况3 | W是黑色，W的左孩子是红色，右孩子是黑色 | 将W变红，左孩子变黑，对W右旋，更新W |
| 情况4 | W是黑色，W的右孩子是红色 | 将W的颜色设为父节点颜色，父节点变黑，W的右孩子变黑，对父节点左旋，结束 |
注意：删除修复的四种情况是有顺序的。情况1处理完后会转化为情况2、3或4。情况2是唯一可能向上递归的情况。情况4是终止情况，处理完就结束。我建议你在实现时严格按照这个顺序判断，不要自作聪明调整顺序——我试过，结果就是bug。
四、伸展树（Splay Tree）
伸展树是另一种平衡树，它的思路和红黑树完全不同。伸展树不要求树始终保持平衡，而是通过“伸展操作”把最近访问的节点旋转到根节点。
你想想看，在实际应用中，数据访问往往有局部性——刚访问过的数据很可能再次被访问。伸展树正是利用这一点，把热点数据放在树顶，让后续访问更快。
伸展树的核心操作是伸展（Splay），它通过一系列旋转，将指定节点移动到根节点。旋转分三种情况：
- Zig（单旋）：目标节点是父节点的左孩子或右孩子，进行一次单旋转。
- Zig-Zig（同向双旋）：目标节点和父节点都是左孩子（或都是右孩子），先旋转父节点，再旋转目标节点。
- Zig-Zag（反向双旋）：目标节点是左孩子而父节点是右孩子（或相反），先旋转目标节点，再旋转目标节点（此时它已到父节点位置）。
伸展树的插入和删除都基于伸展操作：
- 插入：先按二叉搜索树插入，然后将新节点伸展到根。
- 查找：找到节点后将其伸展到根；如果没找到，将最后一个访问的节点伸展到根。
- 删除：将要删除的节点伸展到根，删除根节点，然后将左子树的最大节点伸展到左子树的根，最后将右子树接到左子树的右孩子上。
// 伸展操作的核心——Zig-Zig情况（左左）
Node* splay_zig_zig(Node *root, Node *x) {
Node *p = x->parent;
Node *g = p->parent;
// 先旋转p
root = right_rotate(root, g);
// 再旋转x
root = right_rotate(root, p);
return root;
}
个人经验：伸展树在缓存系统中特别好用。我曾经做一个URL路由匹配系统，用伸展树存储路由规则，热点路由的匹配速度比红黑树快了将近30%。但要注意，伸展树在最坏情况下（比如顺序插入）会退化成链表，虽然均摊复杂度是O(log n)，但单次操作可能很慢。实时性要求高的场景，慎用。
五、知识体系总览
下面这张图帮你理清本章的知识脉络：
红黑树和伸展树各有千秋。红黑树胜在稳定，每次操作的时间上限有保证；伸展树胜在简单（不需要存储颜色信息）和局部性优化。我个人在项目中，如果是做基础库（比如STL容器），首选红黑树；如果是做缓存系统或数据访问有明显热点，会考虑伸展树。
好了，这一章的内容就到这里。代码实现上，我建议你先把红黑树的插入写熟，再啃删除。伸展树相对简单，但要注意旋转逻辑别搞反了——我曾经在Zig-Zag的实现中把旋转顺序写反，结果树直接乱套了。
公众号:蓝海资料掘金营，微信deep3321