红黑树深度解析：如何优雅地处理复杂的删除操作

在之前的文章中，我们已经一起探索了红黑树的插入操作。如果你已经跟上了我们的步伐，你一定会同意：红黑树通过精妙的颜色规则和旋转操作，在保持 $O(\log n)$ 性能的同时，维持了树的完美平衡。

然而，真正的挑战现在才开始。相比于插入，红黑树的删除操作往往被认为是数据结构课程中最难啃的骨头之一。别担心，在这篇文章中，我们将像剥洋葱一样，层层拆解删除背后的逻辑。你会发现，只要理解了其中的“双重黑”概念，一切其实都有迹可循。

为什么删除如此棘手？

在普通的二叉搜索树（BST）中，我们只需要找到节点，将其摘下，然后重新连接父子关系即可。但在红黑树中，我们还得时刻盯着那五条不可逾越的红黑性质。

删除操作之所以棘手，主要是因为它很容易破坏性质 5：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（即“黑高”）。简单来说，如果我们直接删除了一个黑色节点，这条路径的黑高就会突然变矮，导致整棵树失衡。为了解决这个问题，我们需要引入一个有趣的概念——双重黑（Double Black）。

但在深入“双重黑”之前，让我们先回顾并优化标准的 BST 删除流程，这是一切的基础。

第一步：执行标准 BST 删除

首先，我们需要找到待删除的节点，并将其从树的结构上移除。这与在普通 BST 中的操作是一致的。让我们回顾一下三种基本情况：

• 无子节点（叶子节点）：这是最简单的情况。我们只需直接将节点从其父节点上断开。

    // 伪代码示例：简单移除叶子节点
    if (node->left == NULL && node->right == NULL) {
        if (node->parent->left == node)
            node->parent->left = NULL;
        else
            node->parent->right = NULL;
        delete node; // 释放内存
    }
    

• 仅有一个子节点：这种情况也很直观。我们用其唯一的子节点替换该节点的位置。

    // 实际应用中，如果红黑树性质完好，
    // 这种情况通常意味着待删除节点是红色，且子节点是黑色（NIL）。
    Node* child = (node->left != NULL) ? node->left : node->right;
    if (node->parent->left == node)
        node->parent->left = child;
    else
        node->parent->right = child;
    // 记得更新子节点的父指针
    if (child != NULL) child->parent = node->parent;
    

• 有两个子节点：这是最麻烦的结构性操作。我们不能直接删除节点，否则树的连通性会断裂。

* 策略：找到该节点的中序后继（Inorder Successor，即右子树中最左侧的节点）。

* 替换：将后继节点的值复制到当前待删除节点。

* 递归：现在问题转化为了删除那个后继节点。而根据后继节点的定义，它要么没有子节点，要么只有一个右子节点（没有左子节点）。这让我们回到了前两种情况。

> 实战见解：在实际工程代码中，为了代码复用，我们通常会将 BST 的删除逻辑封装，最终只聚焦于“移除只有一个子节点或没有子节点的节点 $v$，并用其子节点 $u$ 来替换”这一动作。

第二步：颜色决定命运

现在，节点 $v$ 已经被移除，子节点 $u$ 取代了它的位置。红黑树是否还能保持平衡，完全取决于 $v$ 和 $u$ 的颜色组合。

#### 情况 A：简单情况（当 $u$ 或 $v$ 是红色时）

这是最幸运的情况。如果 $u$ 是红色，或者 $v$ 是红色（注意：红黑树不允许父子同为红色，所以两者不可能都是红色），我们可以很轻松地收尾。

• 操作：我们将替换上来的节点 $u$ 直接涂成黑色。
• 原理：

* 如果 $v$ 是红色：删除红色节点不会影响黑高。我们将 $u$（必为黑色）保留或涂黑，黑高不变。

* 如果 $u$ 是红色：我们在 $v$（黑色）的位置放了一个红色节点，这相当于在该路径上少了一个黑色。没关系，我们把 $u$ 涂黑，黑高就被补回来了，且不会引入红红冲突。

// 修复逻辑代码片段
if (u->color == RED || v->color == RED) {
    u->color = BLACK; // 只需变色，无需旋转
} else {
    // 进入最复杂的 Case B
    fixDoubleBlack(u); 
}

#### 情况 B：复杂情况（当 $u$ 和 $v$ 都是黑色时）

这就是噩梦的开始，也是“双重黑”登场的时候。

• 如果 $u$ 是根节点：

这很简单。我们只需要把根节点当作简单的黑色（实际上它只是少了一个黑色的子节点，但这不影响整棵树的相对黑高）。什么都不用做，操作结束。

• 如果 $u$ 不是根节点：

当 $v$（黑色）被移除，且 $u$（也是黑色或 NIL）上位时，这条路径上凭空少了一个黑色节点。为了平衡这个“亏空”，我们创造性地将 $u$ 标记为“双重黑”。

> 核心概念理解：“双重黑”并不是说节点真的变成了两种颜色，而是一个记账概念。它意味着：“这里本来应该有一个黑色节点，但为了维持其他路径的平衡，我这里现在欠着两个黑色单位的权重。” 我们的任务就是通过旋转和变色，把这个“双重黑”的负担分摊出去，最终消除它。

让我们设当前节点为 $u$（双重黑），它的兄弟节点为 $s$（Sibling）。修复操作的核心就在于观察这个兄弟 $s$。

第三步：修复双重黑（FixDoubleBlack）

为了消除 $u$ 身上的“双重黑”，我们需要检查兄弟节点 $s$ 的颜色及其子节点的颜色。这看起来眼花缭乱，但我们可以将其归纳为几大类操作。

#### 场景 1：兄弟 $s$ 是红色

如果兄弟是红色的，那么它的两个子节点必然是黑色的（红黑树性质）。

• 操作：

1. 将兄弟 $s$ 涂为黑色。

2. 将父节点 $p$ 涂为红色。

3. 对父节点 $p$ 进行旋转（如果 $s$ 是左子就右旋，反之亦然）。

• 目的：这步操作本身不会直接修复双重黑，它的主要作用是转换状态。旋转后，$u$ 会有一个新的黑色兄弟（原本 $s$ 的子节点），并且 $u$ 的父节点变红了。这让我们能够进入下面更容易处理的场景（兄弟是黑色）。

#### 场景 2：兄弟 $s$ 是黑色，且至少有一个子节点是红色

这是解决问题的关键步骤。我们需要根据 $s$ 和其红色子节点 $r$ 的位置关系，决定旋转的类型。这里的目标是利用红色节点 $r$ 来“吸收”多余的黑度。

我们可以分为四种具体的旋转情况：

• 左左情况：$s$ 是左子，且 $s$ 的左子 $r$ 是红色（或 $s$ 有两个红色子节点，以左子为准）。

* 操作：

1. $s$ 染上父节点 $p$ 的颜色。

2. $p$ 变为黑色。

3. $s$ 的左子 $r$ 变为黑色。

4. 对 $p$ 进行右旋。

* 结果：$u$ 变回单黑，树平衡恢复。

• 左右情况：$s$ 是左子，且 $s$ 的右子 $r$ 是红色。

* 操作：

1. 先对 $s$ 进行左旋（将 $r$ 提上来）。

2. 现在的情况变成了“左左”，只需按左左情况处理新的父节点即可。

• 右右情况：$s$ 是右子，且 $s$ 的右子 $r$ 是红色。

* 操作：

1. $s$ 染上父节点 $p$ 的颜色。

2. $p$ 变为黑色。

3. $s$ 的右子 $r$ 变为黑色。

4. 对 $p$ 进行左旋。

• 右左情况：$s$ 是右子，且 $s$ 的左子 $r$ 是红色。

* 操作：

1. 先对 $s$ 进行右旋。

2. 再对原父节点进行左旋。

> 代码示例：处理右右情况的逻辑片段

>

> void fixRightRight(Node *u, Node *p, Node *s) {
>     // s 是 p 的右子，且 s 的右子是红色
>     s->color = p->color;       // s 继承 p 的颜色
>     p->color = BLACK;          // p 变黑
>     s->right->color = BLACK;   // 原来的红色子节点变黑
>     rotateLeft(p);             // 左旋 p
>     // 双重黑已被消除，递归结束
> }
> 

#### 场景 3：兄弟 $s$ 是黑色，且所有子节点也都是黑色

这是最让人头疼的情况，因为我们无法利用红色子节点来抵消黑度。此时，我们只能把“债务”向上转移。

• 操作：

1. 将兄弟 $s$ 涂为红色。

2. 把 $u$ 的双重黑状态去掉一个，变成单黑（但是，这意味着 $u$ 这条路径的黑高其实还是比别的少 1，不过我们将这个问题上交给了父节点）。

3. 如果父节点 $p$ 原本是红色，将其变为黑色，此时平衡恢复（相当于红变黑补了黑高）。

4. 如果父节点 $p$ 原本是黑色，那么 $p$ 现在变成了“双重黑”。我们需要递归调用修复函数，将 $p$ 作为新的 $u$ 继续向上处理。

// 递归上移黑度的代码逻辑
s->color = RED; // 兄弟变红，表示借走了一个黑色单位
if (p->color == RED) {
    p->color = BLACK; // 父节点由红变黑，填补了空缺，结束
} else {
    fixDoubleBlack(p); // 父节点也是黑的，现在它背锅了，继续递归
}

性能分析与最佳实践

红黑树的删除操作虽然逻辑复杂，但正如我们之前提到的，它的时间复杂度始终保持在 $O(\log n)$。这是因为我们所有的旋转和变色操作都只发生在从删除节点到根节点的一条路径上，树的高度是对数级的。

在实现时，你可能会遇到以下挑战和解决方案：

• NIL 节点的处理：在代码实现中，显式地定义一个全局的 INLINECODEaee4a8bc 节点（颜色为黑）通常比反复检查 INLINECODE7ba9f360 要安全得多。这可以防止空指针异常，并且让“双重黑”逻辑更容易应用在叶子节点上。
• 递归 vs 迭代：上述的修复过程虽然可以用递归描述，但在工程实现中，为了防止栈溢出和提升微小的性能，通常会改写为 while 循环。
• 调试建议：红黑树的 Bug 极难调试。强烈建议在编写代码时，同时编写一个 validateTree() 函数，在每次插入和删除后都遍历整棵树，检查红黑性质是否依然成立（如：红节点不相连、计算所有路径的黑高是否相等）。

总结

让我们回顾一下红黑树删除的核心心法：

• 先按 BST 方式删除，找到替代节点 $u$。
• 只要有一个是红的，简单涂黑就完事。
• 如果全是黑，$u$ 变成“双重黑”。
• 利用兄弟 $s$ 来“消化”这个双重黑：

* 兄弟红？旋转让黑兄弟上位。

* 兄弟黑且有红子？旋转变色，完美解决。

* 兄弟全黑？兄弟变红，父节点背锅（向上递归）。

虽然规则繁多，但当你动手实现几次后，你会发现这其实是自然界平衡之美在代码中的体现。这种在局部微调（旋转）来维持全局平衡的思想，正是算法设计的精髓所在。

推荐阅读

如果你想从数学角度更严谨地证明为什么上述操作能覆盖所有情况，或者想看看其他语言的实现细节，我们强烈推荐你阅读以下经典著作中的相关章节。这些书籍是每一位系统级程序员的案头必备：

• Introduction to Algorithms (Thomas H. Cormen 等) – 这本书对红黑树删除的数学证明最为详尽。
• The Art of Computer Programming, Volume 3 (Donald E. Knuth) – 深入探讨了多路平衡树的历史与原理。
• Algorithms in C, Part 5 (Robert Sedgewick) – 提供了非常直观的图解和 C 语言实现细节。

希望这篇深入浅出的文章能帮助你彻底攻克红黑树删除这一难关！