红黑树 学习笔记4 - 删除

接上，算法导论13.4 删除

与 n$n$ 个节点的红黑树上的其它基本操作一样，删除一个结点要花费 O(logn)$O(logn)$ 时间。与插入操作相比，删除操作要稍微复杂一些。
$$
$$首先来完成一些辅助程序。
$$ RB-TRANSPLANT( T,u,v$T,u,v$ ) 把以 u$u$ 为根的子树 替换为 以 v$v$ 为根的子树。

$$一些说明：
$$$$这段程序其实只是设置了 u.p$u.p$ 和 v$v$ 的关系。
$$$$第 1 行首先判断 u$u$ 是否为根结点。
$$
$$
$$
$$接下来看 RB-DELETE( T,z$T,z$ )

$$先解释一下原理：
$$$$考察 z$z$ 的孩子数量，若少于2个，则用孩子替换 z$z$ ，然后直接移除 z$z$ 。
$$$$若有2个孩子，则取到 z$z$ 的后继结点。并且这里有个小细节：
$$$$$$区分 z$z$ 的后继结点是否为右孩子，这导致一些微小的改动。
$$$$然后，将 z$z$ 移除，替换为 z$z$ 的后继，并将其颜色改为 z$z$ 的颜色。
$$$$最后，若 z$z$ 的后继原来颜色为黑色，这有可能导致令人不快的情况，将其黑色下推个右孩子，然后调用一个调整函数 RB-DELETE-FIXUP( T,x$T,x$ )。
$$
$$现在专注于上方的代码细节：
$$先做一些注记：对于 z$z$ 的左右均非空的情况， z$z$ 为要删除的结点，
$$$$$$$$y$y$ 为其后继， x$x$ 为 y$y$ 的右孩子。
$$$$1. 第 3 行判断 左为空，第 6 行判断 左非空，右为空,
$$   $$ 如果进入了这两个状态，只需要将 z$z$ 和其有可能非空的孩子交换即可，
$$   $$ 然后直接到第 21 行，注意到我们可以推出：
$$   $$ 此时 x$x$ 结点一定为红色，并且它是原来 z$z$ 下的唯一一个内部结点。
$$   $$ 那么进入 FIXUP 程序直接将其颜色设置为黑即可。
$$$$2. 复杂的情况从第 9 行开始，此时 z$z$ 的左右均非空，取 z$z$ 的后继为 y$y$ 。
$$   $$ 第 10 行记录 y$y$ 的颜色。
$$   $$ 第 11 行取 y$y$ 的右子为 x$x$ 。
$$   $$ 然后分2中情况：

$$1. z$z$ 的后继是右子。
$$$$第 13 行有一个迷之操作。
$$
$$

$$2. z$z$ 的后继不是右子。
$$$$第 14 行用 x$x$ 替换 y$y$ 所在位置。
$$$$第 15-16 行重新设置 y$y$ 的新右子关系（取代 z$z$ ）。
$$
$$接着到达第 17 行，此时，不论哪种情况，
$$原来以 z$z$ 为根的子树已经被 z$z$ 和 y$y$ 分为左右两边，
$$那么用 y$y$ 替换 z$z$ ，并且重新设置 y$y$ 的左孩子。
（注意应做好 z$z$ 的销毁工作，第一种情况 z$z$ 的右子是 y$y$ ，第二种情况 z$z$ 的右子是 y$y$ 的右子）
$$至此，我们已经完成了树形结构上的替换操作，下来研究如何维持红黑树的性质。
$$在第 20 行将 y$y$ 的颜色替换为原来 z$z$ 的颜色。
$$然后检查 y$y$ 的原始颜色，若为黑色，则下推给 x$x$ ，此举将导致 x$x$ 的颜色成为 红黑 / 黑黑 ，并调用 RB-DELETE-FIXUP( T,x$T,x$ ) 程序来恢复红黑树的性质。
$$
$$一点说明：如果 y$y$ 是红色，则红黑树的性质不受破坏。
$$$$1. 根结点颜色保持为黑。
$$$$2. 黑高没有变化。
$$$$3. 不存在两个相邻红结点。
$$
$$另一方面，如果 y$y$ 为黑色，则会产生3个问题：
$$$$1. 根结点变为红色，这只可能在 z$z$ 的孩子少于2个是发生。
$$$$2. 若 x$x$ 和 x.p$x.p$ 是红色的，则违反了性质4
$$$$3. y$y$ 的移动导致任何 y$y$ 的祖先的包含 y$y$ 的路径上都少了一个黑结点，这违反了性质5。
$$
$$改进的办法是将 y$y$ 的黑色下推给 x$x$ 结点，使之成为 红黑 / 黑黑 结点。
$$易知在 FIXUP 调用之前，性质5 成立。
$$
$$
$$
RB-DELETE-FIXUP( T,x$T,x$ )

$$下面我们来看看过程 RB-DELETE-FIXUP 是如何恢复红黑树性质的。
$$(注：图片中黑结点表示黑色，深色结点表示红色，浅色结点表示颜色未知。)


$$第 1-22 行的 while$while$ 循环的目标是将额外的黑色沿树上移，直到：
$$$$1. x$x$ 指向红（黑）结点，此时在第 23 行中，将 x$x$ 着为黑色。
$$$$2. x$x$ 指向根结点，此时可以简单地“移除”额外的黑色。
$$$$3. 执行适当的旋转和重新着色，退出循环。
$$
$$在 while$while$ 循环中， x$x$ 总是指向一个黑（黑）的非根节点。
$$退出循环时， x$x$ 为非根节点或为红（黑）。
$$
$$在第 2-21 行中是 x$x$ 为左孩子的情况。
$$保持指针 w$w$ 指向 x$x$ 的兄弟，注意到 w$w$ 不可能是 T.NIL$T.NIL$ 。
$$
$$下面我们将分 4 种情况证明：
$$$$如果 性质5 在变换之前成立，那么在变换之后也成立。
$$结合之前的结论 FIXUP 调用之前 性质5 成立，就可以知道 FIXUP调用完成后，红黑树所有性质都得到满足。
$$
$$
$$
$$
$$情况1： x$x$ 的兄弟结点 w$w$ 为红色。

$$由于 w$w$ 为红色，故 x.p$x.p$ 和 w$w$ 的2个孩子都为黑色。
$$操作：交换 x.p$x.p$ 和 w$w$ 的颜色，并且对 x.p$x.p$ 做一次左旋。
$$
$$总结：改变2个结点颜色，并做一次左旋。额外黑色不变。
$$$$  $$① –> ② –> End
$$$$  $$① –> ④ –> End
$$$$  $$① –> ③ –> ④ –> End
$$
$$
$$情况2： x$x$ 的兄弟结点 w$w$ 为黑色，且 w$w$ 的2个孩子都是黑色。

$$操作：从 x$x$ 和 w$w$ 上各去掉一重黑色，于是 x$x$ 变为一重黑色，而 w$w$ 变为红色。为了补偿去掉的黑色（即恢复性质5），在 x.p$x.p$ 上新增一重黑色，将 x.p$x.p$ 作为新结点 x$x$ 来重复 while$while$ 循环。
$$
$$总结：各去掉一重黑色，并补偿父节点一重黑色。无旋转操作。额外黑色上移。
$$$$  $$② –> ( ① | ② | ③ | ④ | End)
$$
$$
$$情况3： x$x$ 的兄弟结点 w$w$ 为黑色，且 w$w$ 的左孩子为红色， w$w$ 的右孩子为黑色。

$$操作：交换 w$w$ 和 w.left$w.left$ 的颜色，然后对 w$w$ 进行右旋，进入情况4。
$$
$$总结：改变2个结点颜色，并做一次右旋。额外黑色不变。
$$$$  $$③ –> ④ –> End
$$
$$
$$情况4： x$x$ 的兄弟结点 w$w$ 为黑色，且 w$w$ 的右孩子为红色。

$$操作：交换 x.p$x.p$ 和 w$w$ 的颜色，并对 x.p$x.p$ 做一次左旋，
$$$$  $$然后将 w.right$w.right$ 由红色变为黑色，并去掉 x$x$ 上的一重黑色。
$$$$  $$将 x$x$ 设置为 根结点，方便最后调整为黑色。
$$
$$总结：改变3个结点颜色，并做一次左旋。额外黑色消失。
$$$$  $$(这个比较特殊，其他旋转操作只用改变旋转的2个结点颜色)
$$$$  $$④ –> End
$$
$$
$$最后，从循环中退出时有两种可能：
$$$$1. 从情况 ② 退出，只可能是从 ① 或 ② 进入 ② 最后退出，于是退出时 x$x$ 为红（黑）结点（从 ① 进入） 或 根结点（从 ② 进入）。
$$$$2. 从情况 ④ 退出，根结点的颜色可能被破坏，所以在 ④ 中最后将 x$x$ 设为根结点。
$$FIXUP 程序最后统一将 x$x$ 着为黑色。
$$
$$
总结：
$$RB-DELETE 在调用 RB-DELETE-FIXUP 之前时间为 O(logn)$O(logn)$ 。
$$在 RB-DELETE-FIXUP 中，
$$$$情况 ①、③、④ 在各执行 O(1)$O(1)$ 次数的颜色改变和至多 3 次旋转后便终止。
$$$$情况 ② 是 while$while$ 循环可以重复执行的唯一情况，
$$$$$$然后指针 x$x$ 沿树上升至多 O(logn)$O(logn)$ 次，且不执行任何旋转。
$$所以，过程 RB-DELETE-FIXUP 要花费 O(logn)$O(logn)$ 时间，做至多 3 次旋转。
$$因此， RB-DELETE 运行的总时间为 O(logn)$O(logn)$ 。
$$
$$
$$
课后习题：
13. 4-1
$$
$$
13. 4-2
$$
$$
13. 4-3
$$
$$
13. 4-4
$$
$$
13. 4-5
$$
$$
13. 4-6
$$
$$
$$