705 红黑树

红黑树

定义

红黑树 (Red-Black Tree) 是一种自平衡的二叉排序树，它通过为每个结点增加一个颜色属性（红色或黑色）并遵循特定的规则来维持树的平衡，从而确保查找、插入、删除等操作的时间复杂度在最坏情况下也是 $O(\log n)$。

红黑性质

一棵红黑树必须满足以下五条性质：

1. 结点颜色：每个结点要么是红色，要么是黑色。
2. 左根右：首先满足二叉搜索树的性质（）
3. 根叶黑：根结点是黑色的,所有叶子结点都是黑色的。在实际实现中，这些叶子结点通常是哨兵结点。
4. 不红红：一个红色结点的两个子结点都是黑色的。这意味着从根到叶子的任何路径上都不会出现连续的两个红色结点。
5. 黑路同：对每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。这个数目称为该结点的黑高 。

相关结论

• 路径长度：从根到叶子的最长路径长度不会超过最短路径长度的两倍。这是红黑树能够维持平衡的关键。
• 结点数与高度：一棵含有 $n$ 个内部结点的红黑树，其高度 $h\le 2{\log }_2(n+1)$。这保证了其操作的时间复杂度为 $O(\log n)$。
• 黑高：记树的黑高为 $bh(T)$，则树中内部结点数至少为 $2^{bh(T)}-1$。

插入

红黑树的插入操作首先按照二叉排序树的规则将新结点插入，并将其染成红色。这样做的好处是不会违反性质 5（黑色高度不变）。但可能会违反性质 2（根为红色）或性质 4（出现连续红色结点）。

插入后的调整分为以下几种情况（设新插入结点为 N，其父结点为 P，祖父结点为 G，叔父结点为 U）：

1. Case 1: N 是根结点

   • 直接将 N 染成黑色。

2. Case 2: P 是黑色

   • 无需任何操作，树仍然满足所有性质。

3. Case 3: P 是红色（此时 G 必为黑色，因为插入前是红黑树）

   • Case 3.1: 叔父 U 是红色
     • 操作：将 P 和 U 染成黑色，将 G 染成红色。
     • 后续：将 G 视为新的插入结点，递归向上调整。
   • Case 3.2: 叔父 U 是黑色（或 NIL）
     • 调整分为两步：旋转 和 变色。
     • LL 型 (P 是 G 的左孩子，N 是 P 的左孩子):
       • 操作：将 P 染黑，G 染红，对 G 进行右旋。
     • RR 型 (P 是 G 的右孩子，N 是 P 的右孩子):
       • 操作：将 P 染黑，G 染红，对 G 进行左旋。
     • LR 型 (P 是 G 的左孩子，N 是 P 的右孩子):
       • 操作：先对 P 进行左旋，转换为 LL 型，再按 LL 型处理。
     • RL 型 (P 是 G 的右孩子，N 是 P 的左孩子):
       • 操作：先对 P 进行右旋，转换为 RR 型，再按 RR 型处理。

关键点：插入操作最多需要 2 次旋转。

删除

红黑树的删除操作比插入更复杂。首先按二叉排序树规则删除结点。

• 只有左孩子/只有右孩子：直接用孩子代替之，然后染黑

• 如果删除的是红色结点，树的性质不会被破坏，无需调整。
• 如果删除的是黑色结点，则会破坏性质 5（黑色高度），需要进行复杂的调整。

调整的核心思想是：如果被删除的黑色结点的替代者（通常是其子结点）也是黑色，则该路径上会“丢失”一个黑色结点，导致“双重黑色”问题。调整过程就是将这个“双重黑色”属性沿树向上移动，直到：

1. 遇到一个红色结点，将其染黑，调整结束。
2. 到达根结点，调整结束。
3. 通过旋转和变色来消除双重黑色。

设被调整的结点为 X（它带有双重黑色属性），其兄弟结点为 S，父结点为 P。

1. Case 1: S 是红色

   • 操作：将 S 染黑，P 染红，对 P 进行旋转（X 是左孩子则左旋，反之右旋）。
   • 后续：X 的新兄弟结点变为黑色，问题转化为 Case 2, 3 或 4。

2. Case 2: S 是黑色，且 S 的两个子结点都是黑色

   • 操作：将 S 染红。
   • 后续：将 P 视为新的被调整结点，递归向上调整。

3. Case 3: S 是黑色，S 的远侄（与 X 同侧的 S 的子结点）是黑色，近侄是红色

   • 操作：将 S 染红，近侄染黑，对 S 进行旋转。
   • 后续：X 的新兄弟结点是黑色且其远侄是红色，问题转化为 Case 4。

4. Case 4: S 是黑色，S 的远侄是红色

   • 操作：将 S 的颜色设为 P 的颜色，P 染黑，S 的远侄染黑，对 P 进行旋转。
   • 后续：调整结束。

关键点：删除操作最多需要 3 次旋转。