RB-INSERT-FIXUP

概述

RB-INSERT-FIXUP 是红黑树插入操作中的修复过程。由于新插入的节点被着为红色，可能违反红黑性质 2（根为黑）或性质 4（红节点的子节点为黑）。RB-INSERT-FIXUP 通过变色和旋转操作恢复红黑性质，最多执行 2 次旋转，总时间复杂度为 $O(\lg n)$。

定义

RB-INSERT-FIXUP(T, z)

给定红黑树 $T$ 和新插入的红色节点 $z$，RB-INSERT-FIXUP 通过迭代修复，恢复 $T$ 的所有红黑性质。

为什么新节点着红色

在 RB-INSERT 中，新节点 $z$ 被着为红色。这一选择是关键的设计决策：

• 着红色：只可能违反性质 2（$z$ 恰好是根）或性质 4（$z$ 的父节点为红色）。这两种情况都容易修复。
• 着黑色：必定违反性质 5（黑高度一致性），因为从根到 $z$ 的路径上多了一个黑色节点，而其他路径没有。修复代价远大于着红色。

因此，着红色是”最小破坏”策略，使得修复过程尽可能简单。

三种情况分析

设 $z$ 为新插入的红色节点，$p=z.p$（$z$ 的父节点）。由于 $z$ 为红色且违反了性质 4，因此 $p$ 必为红色。

设 $pp=p.p$（$z$ 的祖父节点），由性质 4，$pp$ 必为黑色。

设 $u=pp$ 的另一个子节点（即 $z$ 的叔叔节点，uncle）。

以下分析假设 $p$ 是 $pp$ 的左子节点（$p=pp.left$）。$p$ 是 $pp$ 右子节点的情况完全对称。

Case 1：叔叔 $u$ 为红色

        pp(B)              pp(R)
       /    \             /    \
     p(R)   u(R)   →    p(B)  u(B)
     /                   /
   z(R)                z(R)

处理方法：

1. 将 $p$ 着为黑色
2. 将 $u$ 着为黑色
3. 将 $pp$ 着为红色
4. 令 $z=pp$，将问题上移两层到祖父节点

效果： $z$ 所在的子树的黑高度不变（$p$ 和 $u$ 从红变黑，$pp$ 从黑变红），但 $pp$ 变红后可能继续违反性质 4，因此需要继续循环处理。

Case 2：叔叔 $u$ 为黑色，$z$ 是 $p$ 的右子节点

        pp(B)            pp(B)
       /    \           /    \
     p(R)   u(B)  →  z(R)   u(B)
       \              /
       z(R)         p(R)

处理方法：

1. 对 $p$ 执行左旋 旋转
2. 令 $z=p$，$p=z.p$（此时 $z$ 变为 $p$ 的左子节点）
3. 转入 Case 3

效果： Case 2 本身不修复问题，而是将情况转化为 Case 3。

Case 3：叔叔 $u$ 为黑色，$z$ 是 $p$ 的左子节点

        pp(B)             p(B)
       /    \           /    \
     p(R)   u(B)  →  z(R)  pp(R)
     /                       \
   z(R)                      u(B)

处理方法：

1. 将 $p$ 着为黑色
2. 将 $pp$ 着为红色
3. 对 $pp$ 执行右旋 旋转

效果： 修复完成。$z$（现在是 $p$ 的左子节点）和 $p$ 都是黑色，$pp$ 变为红色但不违反性质 4（因为 $pp$ 的父节点是黑色的，或者 $pp$ 变为根）。

伪代码

RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
      if z.p == z.p.p.left
          y = z.p.p.right          // y 是叔叔
          if y.color == RED        // Case 1
              z.p.color = BLACK
              y.color = BLACK
              z.p.p.color = RED
              z = z.p.p
          else
              if z == z.p.right    // Case 2
                  z = z.p
                  LEFT-ROTATE(T, z)
              // Case 3
              z.p.color = BLACK
              z.p.p.color = RED
              RIGHT-ROTATE(T, z.p.p)
      else                         // 对称情况（p 是右子节点）
          // 与上面完全对称，left/right 互换
  T.root.color = BLACK             // 确保性质 2

核心性质

旋转次数

最多 2 次旋转

• Case 1 不需要旋转，只需变色。但 Case 1 可能重复多次（每次上移两层）。
• Case 2 需要 1 次旋转，然后转入 Case 3。
• Case 3 需要 1 次旋转，修复完成。
• 因此，整个修复过程最多需要 2 次旋转（Case 2 + Case 3 各一次）。

时间复杂度

$O(\lg n)$

• Case 1 的循环最多执行 $O(\lg n)$ 次（每次 $z$ 上移两层，树高为 $O(\lg n)$），但每次只有 $O(1)$ 的变色操作。
• Case 2 + Case 3 最多 2 次旋转，$O(1)$ 时间。
• 总时间复杂度为 $O(\lg n)$。

循环终止条件

循环在以下两种情况下终止：

1. $z.p$ 为黑色（或 $z$ 为根）：此时 $z$ 为红色不违反任何性质。
2. 进入 Case 3 并执行旋转后：此时 $z.p$ 被着为黑色，循环条件不再满足。

循环结束后，最后将根节点着为黑色（确保性质 2），即使根节点本来就是黑色（幂等操作）。

章节扩展

RB-INSERT 的完整流程：

1. BST 插入：像普通 BST 一样插入新节点 $z$，$O(\lg n)$。
2. 着色：将 $z$ 着为红色。
3. 修复：调用 RB-INSERT-FIXUP 恢复红黑性质，$O(\lg n)$。

总时间复杂度：$O(\lg n)$。

参见

• 红黑树 — 红黑树的完整定义与五条性质
• 旋转 — 左旋与右旋操作
• RB-DELETE-FIXUP — 删除修复（更复杂的四种情况）
• 黑高度 — 黑高度的定义