额外黑色

概述

额外黑色（extra black） 是红黑树删除修复过程中的一个概念性工具。当被删除（或被移动）的节点 $y$ 为黑色时，为了在修复过程中保持各路径上黑色节点数的”账面平衡”，将替代节点 $x$ 视为带有一个”额外黑色”，使得经过 $x$ 的路径在概念上仍然保持原来的黑高度。修复过程的目标就是逐步将这个额外黑色上移直到它可以被安全消除。

定义

额外黑色

在 RB-DELETE 中，当被移除的节点 $y$ 为黑色时，其替代节点 $x$（$x$ 可能为 NIL）被赋予一个额外的黑色。此时 $x$ 具有”双重黑色”（如果 $x$ 原本为黑色）或”红黑色”（如果 $x$ 原本为红色）的属性。这个额外黑色是一个概念性标记，不实际存储在节点中，仅用于指导修复逻辑。

问题来源

红黑树的删除操作基于 BST 的删除（见 二叉搜索树），分为三种情况：

1. $z$ 没有子节点：直接删除 $z$，$x=\text{NIL}$ 替代 $z$。
2. $z$ 有一个子节点：用子节点替代 $z$，$x=z$ 的唯一子节点。
3. $z$ 有两个子节点：找到 $z$ 的后继 $y$（或前驱），用 $y$ 的数据替换 $z$ 的数据，然后删除 $y$。

在所有情况下，设 $y$ 是实际从树中移除的节点（可能就是 $z$ 本身，也可能是 $z$ 的后继），$x$ 是替代 $y$ 位置的节点。

关键观察：

• 若 $y$ 为红色：删除不影响任何路径的黑高度，无需修复。
• 若 $y$ 为黑色：经过 $x$ 的所有路径上黑色节点数减少了 1，违反性质 5。

额外黑色的工作机制

核心思想

将 $x$ 视为带有”额外黑色”，使得：

• 经过 $x$ 的路径上的黑色节点数在概念上恢复为删除前的值。
• 但 $x$ 本身现在”多了一个黑色”，需要在修复过程中消除。

$x$ 的三种状态

$x$ 原始颜色	赋予额外黑色后的状态	含义
红色	红黑色	$x$ 贡献 1 红 + 1 黑 = 2 个颜色
黑色	双重黑色	$x$ 贡献 2 个黑色
NIL（黑色）	双重黑色 NIL	NIL 哨兵贡献 2 个黑色

额外黑色的消除方式

额外黑色通过 RB-DELETE-FIXUP 过程逐步上移，最终通过以下两种方式消除：

1. 遇到红色节点（吸收）：如果带有额外黑色的节点 $x$ 是红色的，则将 $x$ 直接着为黑色。红色吸收额外黑色，$x$ 变为纯黑色，额外黑色消失。这对应于 RB-DELETE-FIXUP 循环终止后执行 x.color = BLACK 的操作。

2. 到达根节点（丢弃）：如果额外黑色被上移到根节点，则直接丢弃。因为根节点多一个黑色意味着所有路径都多一个黑色，相对平衡不受影响。这对应于 RB-DELETE-FIXUP 中令 $x=T.root$ 终止循环的操作。

额外黑色的上移过程

在 RB-DELETE-FIXUP 的 Case 2 中，额外黑色从 $x$ 上移到 $x.p$：

• 将 $x$ 的兄弟 $w$ 从黑色变为红色（$w$ 所在路径失去一个黑色）
• 将 $x$ 上移到 $x.p$（$x$ 的额外黑色随之上移）
• 效果：$x$ 原路径和 $w$ 路径的黑色数同时减少 1，但 $x.p$ 获得额外黑色，使得经过 $x.p$ 的路径保持平衡

核心性质

概念性工具

不实际存储

额外黑色不存储在节点的 color 属性中。它是一个纯粹的概念性工具，用于推理修复过程的正确性。在代码实现中，RB-DELETE-FIXUP 通过检查 $x$ 的颜色和 $x$ 是否为根来判断循环条件，间接地处理额外黑色的状态。

与红黑性质的关系

额外黑色存在期间，红黑性质的状态如下：

红黑性质	是否满足	说明
性质 1（非红即黑）	满足	额外黑色是概念性的，不改变实际颜色
性质 2（根为黑）	可能违反	若额外黑色到达根，循环终止时修复
性质 3（NIL 为黑）	满足	NIL 仍为黑色
性质 4（红子为黑）	满足	额外黑色不影响红节点的子节点约束
性质 5（黑高度一致）	概念上满足	额外黑色使得各路径的黑高度在概念上一致

章节扩展

额外黑色是理解 RB-DELETE-FIXUP 的关键。四种情况的处理逻辑可以用额外黑色的视角统一理解：

• Case 1：调整结构，使兄弟变为黑色，为后续处理做准备。
• Case 2：将额外黑色上移一层。
• Case 3：调整兄弟子树结构，为 Case 4 做准备。
• Case 4：通过变色 + 旋转，将额外黑色”分散”到兄弟子树中，消除额外黑色。

参见

• RB-DELETE-FIXUP — 使用额外黑色机制的修复过程
• 红黑树 — 红黑树的完整定义与五条性质
• 黑高度 — 黑高度的定义
• 旋转 — 修复过程中使用的旋转操作