红黑树详解：五条性质与插入删除调整
红黑树是一种自平衡二叉搜索树：不追求左右子树高度差不超过 1 的严格平衡，只对节点的红黑着色做少量约束，换来插入、删除时至多几次旋转就能恢复平衡。C++ 的 std::map/std::set、Java 的 TreeMap（以及 HashMap 链表过长时的树化结构）、Linux 内核的 epoll 监听描述符管理都基于它。本文从二叉搜索树的退化问题出发，经 AVL 与 2-3-4 树两条线索引出红黑树的五条性质，然后完整过一遍插入与删除的调整策略，最后给出与 AVL 的对比和选型结论。
参考资料：《算法导论》第 13 章、Wikipedia: Red–black tree
从二叉搜索树说起
二叉搜索树（BST）靠一条性质组织数据：左子树所有节点小于等于根，右子树所有节点大于等于根，左右子树递归满足同样规则。这使得查找、插入、删除都沿着一条根到节点的路径进行，比较次数不超过树高。
问题在于树高不受控。随机顺序插入时树高期望为 $O(\log n)$；但按有序序列插入，每个节点都挂在同一侧，树退化成链表，查找退化为 $O(n)$。自平衡树的目标就是把树高约束在 $O(\log n)$ 内，区别只在于「平衡到什么程度、用什么代价维持」。
AVL：严格平衡及其代价
AVL 树是最早的自平衡 BST（Adelson-Velskii 与 Landis，1962），它在 BST 之上加一条硬约束：每个节点左右子树高度之差（平衡因子）的绝对值不超过 1。
由此换来的是高度上界约 $1.44,\log_2 n$（由节点数最少的「斐波那契树」导出），非常接近理想值 $\log_2 n$，查找性能在各类平衡树中接近最优。
代价在写入侧。插入或删除破坏约束后，靠旋转恢复：
- LL 型（失衡由左子树的左子树引起）：对失衡节点右旋；
- RR 型：对失衡节点左旋；
- LR 型（左子树的右子树引起）：先对左子左旋，再对失衡节点右旋；
- RL 型：先对右子右旋，再对失衡节点左旋。
插入的失衡一次单旋或双旋即可修复，调整到此终止；删除则不同，一次旋转后祖先仍可能失衡，最坏要沿路径向根回溯，做 $O(\log n)$ 次旋转。对增删频繁的场景，这个维护开销是 AVL 不被通用容器采用的主要原因。
2-3-4 树：理解红黑树的另一条路
B 树把「每节点一个元素、两个孩子」放宽为「每节点多个元素、多个孩子」，并要求所有叶子在同一层，天生完美平衡，是为磁盘按页读写设计的结构。2-3-4 树就是 4 阶 B 树，节点只有三种形态：
- 2-节点：1 个元素，2 个子树；
- 3-节点：2 个元素，3 个子树；
- 4-节点：3 个元素，4 个子树。
节点内元素有序，$k-1$ 个元素正好把 $k$ 个子树的值域切开。2-3-4 树完美平衡、增删只影响一条路径，但「节点孩子数可变」在 C++ 这类定长结构里实现起来别扭。解决办法是把它拍平成二叉树：每个节点选一个元素作为黑节点上提，其余元素染红下挂——得到的正是红黑树。
等价转换
规则可以概括为一句话：黑节点对应 2-3-4 树节点中被上提的元素，红节点是同一节点里被压下去的其余元素。4-节点居中的元素 b 上提为黑，两侧的 a、c 染红挂下；3-节点上提 b（左倾或右倾均可，两种都合法）。
这个视角直接解释了红黑树的全部性质为什么成立——后面逐一对应。
五条性质
红黑树是每个节点带一个颜色位（红或黑）的 BST，满足：
- 节点要么是红色，要么是黑色；
- 根节点是黑色；
- 每个叶子节点（指 NIL 空节点）是黑色；
- 红色节点的两个子节点都是黑色（任何路径上不存在连续两个红节点）；
- 从任一节点到其每个叶子的路径包含相同数目的黑色节点（黑高相同）。
一棵合法的红黑树示例（省略 NIL 叶子）：
从 2-3-4 树的视角看这些性质：性质 4 说红节点的孩子必黑，即红节点只能出现在黑节点下方——对应「红元素与黑元素同属一个 2-3-4 节点」；性质 5 说黑高处处一致——对应「2-3-4 树所有叶子同层」。性质 2 是性质 4 在根处的体现（根若为红，其「上提」关系悬空）。
两条重要推论：
- 最长路径不超过最短路径的 2 倍。最短路径全黑，长度等于黑高 $bh$；最长路径红黑相间，因红节点不连续，长度至多 $2,bh$。
- 树高不超过 $2,\log_2(n+1)$。结合黑高定义与「每条路径至少一半是黑节点」即可得出，查找因此是 $O(\log n)$。
查找
红黑树的查找与普通 BST 完全相同，颜色不参与比较。AVL 更严格的平衡只带来常数级别的查找优势，两者渐近复杂度一致。
插入
新节点染红后按 BST 规则插入。染红只可能违反性质 4（与红色父节点冲突）：若染黑，则该路径黑高比别处多 1，违反性质 5，修复代价高得多。插入后的修复以「当前节点 N 与父节点 P 是否双红」为线索，设 G 为祖父、U 为叔节点：
情形 1：N 是根。 直接染黑，结束。
情形 2：P 是黑色。 无冲突，结束。
情形 3：P 红、U 红。 不旋转，P 与 U 染黑、G 染红，双红冲突上移到 G，以 G 为新的 N 继续处理：
从 2-3-4 树看，这是 4-节点吸收新元素后的分裂：中间元素（G）上提到父节点，两侧（P、U）各自成为新的 2-节点。
情形 4：P 红、U 黑。 按新节点相对祖父的方位旋转一次（双旋情形两次）并重新着色，修复立即终止。以 P 是 G 的左子为例（P 是右子时左右对调）：
| 插入方位 | 旋转 | 染色 |
|---|---|---|
| 左左（N 是 P 的左子） | 对 G 右旋 | P 升为子树根并染黑，G 降为 P 的右子并染红 |
| 左右（N 是 P 的右子） | 先对 P 左旋，再对 G 右旋 | 同上，N 升到中间层 |
| 右右 | 对 G 左旋 | 同「左左」的镜像 |
| 右左 | 先对 P 右旋，再对 G 左旋 | 同「左右」的镜像 |
左左情形的调整前后（调整后 P 黑、G 红，子树黑高不变）：
整体上，插入修复至多 2 次旋转、$O(\log n)$ 次变色（情形 3 沿路径上浮，情形 4 一次到位）。
删除
删除先做与 BST 相同的结构处理：
- 目标节点至多一个子节点：用子节点顶替后直接删；
- 目标节点有两个子节点：与中序后继交换内容，转化为删除后继（后继至多一个右子）。
真正的麻烦在颜色：删掉的是一个黑节点时，它所在路径的黑高少 1，等价于顶替节点上背了一个「多余的黑色」（双黑）。修复的目标就是消化这个双黑，以双黑节点 N（记兄弟为 W、近侄/远侄按与 N 的距离区分）分为四种情形：
| 情形 | 着色条件 | 处理 |
|---|---|---|
| 1 | W 红 | 父与 W 换色、朝 N 一侧旋转父节点，转为情形 2/3/4 |
| 2 | W 黑，两个侄子皆黑 | W 染红，双黑上移到父节点，继续循环 |
| 3 | W 黑，近侄红、远侄黑 | 近侄旋转上提并换色，转为情形 4 |
| 4 | W 黑，远侄红 | W 顶替父位并继承父的原色，父染黑、远侄染黑，修复结束 |
情形 2 只是变色并把问题上移，可能循环 $O(\log n)$ 次；带旋转的情形 1、3、4 各执行至多一次，因此删除至多 3 次旋转、$O(\log n)$ 次变色。这与 AVL 删除最坏 $O(\log n)$ 次旋转形成关键对比。
若被删节点是红色，删除不影响任何路径的黑高，无需修复。
AVL 与红黑树怎么选
| 维度 | AVL | 红黑树 |
|---|---|---|
| 高度上界 | 约 $1.44,\log_2 n$，更矮 | $2,\log_2(n+1)$，常数更大 |
| 插入调整 | 至多 1 次旋转 | 至多 2 次旋转 + $O(\log n)$ 次变色 |
| 删除调整 | 最坏 $O(\log n)$ 次旋转 | 至多 3 次旋转 + $O(\log n)$ 次变色 |
| 额外空间 | 每节点存高度或平衡因子 | 每节点 1 个颜色位 |
| 适用场景 | 查询远多于写入、要求最快查找 | 通用场景，增删频繁 |
选型要点：
- 通用有序容器选红黑树：增删调整开销有常数上界，查找代价只差常数因子。
std::map/std::set、TreeMap都是这么选的。 - 查询密集到值得为高度较真时选 AVL：如读多写少的静态字典；写入一频繁，删除的回溯旋转就把优势吃掉。
- 数据在磁盘上时选 B 树系：节点大小对齐页，一次 IO 换一层比较，这是数据库索引的主流的实现方式。
要点
- 红黑树 = 拍平的 2-3-4 树：黑元素上提、红元素下挂，五条性质全部由这个对应关系导出。
- 五条性质的净效果：最长路径不超过最短的 2 倍，高度 $O(\log n)$，查找与 BST 完全同构。
- 插入染红，修复「双红冲突」：叔红则变色上浮，叔黑则一次旋转到位；至多 2 次旋转。
- 删除的难点是「双黑」：兄弟侧借红（情形 3/4）或变色上移（情形 2）；至多 3 次旋转。
- 与 AVL 的取舍不在查找，在删除：红黑树用「放宽平衡 + 常数次旋转」换掉了 AVL 删除的 $O(\log n)$ 次旋转。