红黑树的删除：删除操作的复杂情况分析
红黑树的删除，说实话，是整棵树结构里最让人头疼的部分。我当年第一次手写红黑树删除时，调试了整整一个通宵。为什么？因为删除一个节点后，你不仅要维持二叉搜索树的性质，还得保证红黑树的五条规则不被破坏。
删除操作的核心思路其实不复杂：先按普通二叉搜索树的方式删掉节点，再通过旋转和变色来修复红黑性质。但麻烦就麻烦在——修复过程有六种情况要处理。
删除的基本流程
我们先理清删除的步骤。假设要删除节点 z：
- 如果 z 没有孩子，直接删掉它。
- 如果 z 只有一个孩子，用孩子替换 z。
- 如果 z 有两个孩子，找到 z 的后继节点 y（右子树中最小的节点），用 y 的值覆盖 z，然后删除 y。
嗯，这里要注意：真正被物理删除的节点，要么是叶子，要么只有一个孩子。这个结论很重要，因为修复操作只针对被删节点的位置。
删除后的修复：六种情况
被删节点如果是红色，那万事大吉——红黑性质不会被破坏。但如果是黑色，麻烦就来了。黑色节点被删，会导致该路径上少了一个黑色节点，违反规则五。
修复的核心思想是：把「少了一个黑色」的问题向上传递，直到遇到红色节点，或者到达根节点。
我习惯把修复情况分成六种，其实本质上是对称的——左和右各三种。这里以被删节点是左孩子为例：
| 情况 | 描述 | 处理方式 |
|---|---|---|
| 情况1 | 兄弟节点是红色 | 将兄弟变黑，父变红，左旋父节点，转化为情况2/3/4 |
| 情况2 | 兄弟是黑色，且兄弟的两个孩子都是黑色 | 将兄弟变红，把问题向上传递到父节点 |
| 情况3 | 兄弟是黑色，兄弟的左孩子是红色，右孩子是黑色 | 将兄弟的左孩子变黑，兄弟变红，右旋兄弟，转化为情况4 |
| 情况4 | 兄弟是黑色，兄弟的右孩子是红色 | 将兄弟的颜色设为父的颜色，父变黑，兄弟的右孩子变黑，左旋父节点，结束 |
关键点：情况2是唯一可能向上递归的情况。其他情况处理完后，红黑树就平衡了。
我曾经在项目里遇到过一个问题：删除后树的高度没变，但插入新节点时却触发了无限循环。查了半天，发现是情况3和情况4的旋转方向搞反了。你想想看，红黑树的旋转方向一旦搞错，整棵树就乱套了。
代码实现要点
删除修复的代码，我建议你写成递归形式。虽然迭代也能写，但递归的逻辑更清晰，不容易漏掉情况。
// 删除修复函数（伪代码）
void rb_delete_fixup(Node *x) {
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right; // 兄弟节点
// 情况1
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
left_rotate(x->parent);
w = x->parent->right;
}
// 情况2
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
continue;
}
// 情况3
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
right_rotate(w);
w = x->parent->right;
}
// 情况4
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
left_rotate(x->parent);
x = root; // 结束循环
} else {
// 对称处理（x是右孩子的情况）
}
}
x->color = BLACK;
}
避坑指南：我曾经在情况4里忘了把 x 设为 root 来退出循环，结果程序死循环了。记住，情况4处理完后，红黑树已经平衡，必须强制退出。
红黑树的应用场景
红黑树不是纸上谈兵的数据结构。它在实际工程中应用非常广泛，我挑两个最经典的说说。
Linux 内核中的红黑树
Linux 内核用红黑树的地方太多了。比如完全公平调度器（CFS）就用红黑树来管理可运行进程。每个进程有一个 vruntime（虚拟运行时间），CFS 每次选 vruntime 最小的进程来运行——这不就是红黑树最擅长的吗？
还有内存管理中的虚拟内存区域（VMA）也是用红黑树组织的。进程的地址空间里可能有几百个 VMA，插入和查找都很频繁。红黑树的 O(log n) 性能在这里恰到好处。
我记得有一次看内核源码，发现 mmap 系统调用的实现里，查找空闲地址空间用的就是红黑树。当时我还在想，为什么不用哈希表？后来明白了——哈希表不支持范围查询，而红黑树可以快速找到「大于某个地址的第一个空闲区域」。
STL map 和 set
C++ 标准库里的 map 和 set，底层实现就是红黑树。你想想看，为什么不用 AVL 树？
原因其实很简单：STL 容器的插入和删除操作很频繁，AVL 树的平衡要求太严格，每次插入删除都可能触发多次旋转。红黑树的旋转次数更少，虽然查找稍微慢一点（红黑树高度约 2log(n)，AVL 约 1.44log(n)），但整体性能更均衡。
说白了，STL 的设计哲学是「平均性能最优」，而不是「最坏情况最优」。红黑树正好符合这个理念。
实际经验：我在做游戏服务器时，用 std::map 管理在线玩家的会话信息。玩家登录登出频繁，map 的插入删除很稳定，从来没出过性能问题。如果换成 AVL 树，可能每次登录都要多做几次旋转，虽然差别不大，但积少成多也是开销。
其他应用场景
- Java TreeMap / TreeSet：和 C++ STL 一样，底层也是红黑树。
- Nginx 的事件管理：Nginx 用红黑树管理定时器事件，快速找到最近要触发的定时器。
- 数据库索引：虽然 B+ 树更常见，但一些内存数据库（如 Redis）的有序集合就用红黑树。
注意：红黑树不适合磁盘存储。因为树的高度虽然比 AVL 低，但仍然是 log(n) 级别。磁盘 I/O 一次读一个节点太慢了，B+ 树才是磁盘场景的首选。
红黑树删除的核心逻辑图
下面这张图展示了删除修复的完整流程。我建议你对照着图来理解代码，会清晰很多。
这张图里，我特意把六种情况简化成了四个判断节点。你顺着箭头走一遍，就能理解删除修复的完整逻辑。说白了，就是不断判断兄弟和侄子的颜色，然后做相应的旋转和变色操作。
我的建议：学红黑树删除，不要死记硬背六种情况。你只需要记住两个核心操作——旋转和变色，然后理解「少了一个黑色」这个问题是怎么向上传递的。剩下的，画图推演几遍就记住了。
公众号:蓝海资料掘金营，微信deep3321