第13章 红黑树(4)
13.4 删除
跟其它n结点红黑色树的基本操作一样，删除一个结点的运行时间是O(lg n)。从红黑树中删除一个结点比插入一个结点要复杂一点。
从红黑树中删除一个结点的方法在基于TREE-DELETE方法的（第12.3节）。首先我们需要定制一下TRANSPLANT子方法，这样TREE-DELETE可以将它运用在红黑树上。
RB-TRANSPLANT与TRANSPANT有两个地方不一样。首先，第1行用T.nil代替了NIL。其次，在第6行的v.p赋值是无条件的：即使v指向哨兵结点，我们可以将v.p赋值。事实上，当v=T.nil，我们将能够利用v.p来赋值。
RB-DELETE方法有点像TREE-DELETE方法，但是增加了数行伪代码。一些增加的代码是为了跟踪y，它有可能导致破坏红黑的性质。当我们要删除结点z并且z有小于两个孩子，那么z将从树中删除，我们将y当作z。当z有两个孩子，y将是z的后继，y将会移动到z在树中的位置。当它从树中删除或者移动，我们将记下y的颜色，我们跟踪了结点x，将x移动到y在树中原来的位置，因为x可能会破坏红黑树的性质。删除结点z后，RB-DELETE将调用辅助方法RB-DELETE-FIXUP，这个方法会修改颜色和做一些旋转来恢复红黑树性质。
尽管RB-DELETE包含的伪代码是TREE-DELETE的两倍那么多，但是这两个方法有着相同的基本结构。你可以在RB-DELETE找到TREE-DELETE的每一行（有一点点变化，用T.nil替换了NIL，调用TRANSPLANT替换成了调用RB-TRANSLPLANT），在相同的条件下执行。
下面是这两个方法的其它的不同之处：
- 我们维护了结点y，y做为从树中删除的结点或才在树中移动的结点。第1行设置了y指向z，当z有少于两个孩子时直接删除了。当z有两个孩子，第9行设置y指向z的后继，如同TREE-DELETE一样，并且y将会移动到z在树中的位置。
- 因为y的颜色可能会改变，变量y-original-color存储了y在改变之前的颜色。第2和10行在对y进行了赋值后立即设置了这个变量。当z有两个孩子的时候，那么y≠z，并且结点y将移动到结点z在红黑树中的原始位置；第20行让y着成z相同的颜色。我们需要保存y的原始颜色在RB-DELETE的结尾测试它；如果它是黑色的，那么移除或者移动的y可能会破坏红黑树的性质。
- 正如我们刚才讨论过的，我们记录y的原始位置的结点x。第4，7，11设置x指向y唯一的孩子或者，如果y没有孩子，指向哨兵T.nil。（回顾12.3节y没有左孩子。）
- 因为结点x移动到了y的原始位置，x.p一直指向y的双亲结点在树中原始位置，甚至是,事实上也有可能是哨兵T.nil。就算z是y的原始双亲（如果z有两个孩子并且它的后继就是z的右孩子），x.p在RB-TRANSPLANT的也在第6行进行了赋值。（观察第5，8或者14的RB-TRANSPLANT的调用，传递的第二参数跟x是一样的。）
当y的原始双亲是z的时候，然而，我们不希望让x.p指向y的原始双亲，因为我们将会删除这个结点。（译者注：z结点将用从树中删除，x.p指向这个结点就没有意义了）由于结点y将会提升取代z的位置，在第13行设置了x.p指向y，这会导致x.p指向y双亲的原始位置（译者注：原双亲的位置就是z在树中的位置），不管x=T.nil与否。 - 最后，如果y是黑色结点，我们可能破坏一个或更的红黑树性质，所以我们在第22行调用RB-DELETE-FIXUP去恢复红黑树的性质。如果y是红色的，当y删除或者移动的时候，红黑树的性质没有被破坏，理由如下：
- 树中没有结点的black-height被改变。
- 没有红结点是相邻的。因为y取代了z在树中的位置，跟z的颜色是一致的，我们不可能在y的新位置找到两个相邻的红色结点。更进一步，如果y不是z的右孩子，那么y的原始右孩子x替换了y在树中的位置。如果y是红色的，那么x一定是黑色的，所以用x替换y不会导致两个红色结点变成相邻的。
- 因为如果y是红色的，它就不可能是根，根继续是黑色的。
如果结点y是黑色的，可能会出现三个问题，可以调用RB-DELETE-FIXUP将会修正它们。首先，如果y一开始是根并且y的一个红色的孩子变成了新的根，这样我们破坏了性质2。第二，如是x和x.p都是红色的，那么我们破坏了性质4。第三，在树内移动y将会导致任意一条之前包含y的简单路径少一个黑色结点。因此在树中任何以y为祖先的结点不都满足性质5。我们说之前的y的位置上的结点x有一个“额外”的黑色结点，这样就修正了性质5。换句话说，我们在任意包含x的简单路径上增加一个黑色结点，这样情形下，性质5就保持了。当我们移除或者移动黑色结点y，我们将y的黑属性“推”给结点x。问题就是现在结点x既不是红色也不是黑色，性质1将不满足。（译者著：x本身是有颜色的，y的颜色色留在了原地也就是现在x位置，那么x结点就有两种颜色，一种是本身的颜色，一种是黑色）换句话说，结点x可能是“双黑”或者“红和黑”，在包含x的简单路径上，它贡献了2个或者1个黑结点数量。结点x的颜色属性现在仍然是红色（如果x是红和黑）或者黑色（如果x是双黑）。换句话说，在x指向的结点上有一个额外的额外的黑附加上这个结点上而不是在color属性上。（译者著：color属性不能表示该结点的颜色了）。
我们现在可以看看RB-DELETE-FIXUP并考察它是如何修复查找树上的红黑属性的。
方法RB-DELETE-FIXUP恢复了性质1，2和4。练习13.4-1和13.4-2让你去说明方法是如何恢复性质2和4的，所以本节的余下部分，我们专注于性质1。第1-22行的while循环的目的是在树中向上移动额外的黑，直到：
- x指向了一个红和黑结点，这种情形我们在第23行将x的着成（单色）黑色。
- x指向了根，这种情况我们简单的“移除”额外的黑；或者
- 做一些适当的旋转和重新着色，然后我们退出循环。
在while循环里，x一直指向一个非根的双黑结点。我们在第2行里判断x是它双亲x.p的左孩子还是右孩子。（我们给出了x是左孩子情形的代码；x是右孩子的情况在第22行，这们是对称的）我们维护了指针w指向x的兄弟。因为结点x是双黑的，节点w肯定不是T.nil，否则从x.p到叶子w（单黑）（译者著：叶子是黑色的）的路径上的黑结点将会比x.p到x路径上的黑结点的数量要少。
代码中的这四种情形将会在表13.7中出现。在考查每一种情形前，让我们大致地看一下如何验证每一种情形的转换保持了性质5。关键思想在于每种情形的变化，所示的每一个树根（包括）到它的子树α，β，…… ζ都保持了黑结点的数量（包括x的额外的黑色）。因些如果变化之前满足性质5，那么之后它也满足。举个例子，如图13.7(a)，它描述了情形1，变化前和变化后从根到任意子树α，β的黑结点的数量都是3。（再次提醒，记住x结点添加了一个额外的黑色）相同地，在变换前后，从根到任意的子树γ，δ，ε的黑结点的数量是2。在图13.7(b)，图示的树根统计必须包含根根的颜色属性值c,它可能是红色或者黑色。如果我定义count(RED)=0和count(BLACK)=1，那么大变换前后，从根到α的黑结点的数量都是2+count(c)。这种情形下，通过变换后，新结点x的color属性c，但是这个结点的是红黑（当c=RED）或者双黑(当c=BLACK)。同样地，你还可以验证其它情形（参看练习13.4-5）。
情形1：x的兄弟w是红色的。
当结点x的兄弟w是红色的就是情形1（RB-DELETE-FIXUP的第5-8行和图13.7(a)）。由于w肯定有黑色的孩子，我们可以交换w和x.p的颜色，并在x.p上做一次右旋，这不会违反红黑树的性质。旋转前w的孩子是x的新兄弟，它现在颜色是黑色的，因些我们把情形1变成了情形2，3或者4。
情形2：x的兄弟x是黑色的，并且w的孩子都是黑色的。
在情形2中（RB-DELETE-FIXUP的第10到11行和图13.7(b)），w的孩子都是黑色的。因为w也是黑色的，我们可以将x和w的黑都关掉，让x只有一个黑和w变成红色。为了补偿从x和w中移除的黑色，我们添加一个额外的黑色到x.p上，x.p原始可能是红色或者黑色。观察如果是通过情形1进入情形2的，新结点x是红黑色的，由于原始的x.p是红色的，新的结点是红黑的。意味着，新结点x的color属性值是红色的，然后当我们测试循环条件的时，循环结束。然后我们在第23行将新结点x（单黑）着成黑色。
情形3：x的兄弟w是黑色的，w的左孩子是红色的，并且w的右孩子是黑色的。
当w是黑色的，它的左孩子是红色的并且它的右孩子是黑色的就是情形3（第13到16行和图13.7(c)）。我们可以先交换w和它左孩子的颜色并用w做一次右旋，这并不会破坏红黑树的属性。X的新兄弟w现在一棵带有红色右孩子的黑色的结点，这样我们就将情形3转换成了情形4了。
情形4：x的兄弟w是黑色的，并且w的右孩子是红色的。
当结点x的兄弟w是黑色的并且w的右孩子是红色的就是情形4(第17到21行和图13.7(d))。通过改变一些颜色和在x.p上的一次左旋，使它变成单黑，这样我们可以移除x上的额外的黑色并且不会破坏任何红黑树的性质。设置x成根将会在测试循环条件时使while循环终止。
分析
RB-DELETE的运行时间是多少呢？因为高度为n的红黑树是O(lg n)，除去调用RB-DELETE-FIXUP的时间方法总时间花费O(lg n)。在RB-DELETE-FIXUP里，情形1，3和4的每一个都会在常数次颜色修改和最多三次旋转结束循环。情形2是唯一一个重复while循环的，并且只是x指针在树中向上移动，并不会旋转。因些RB-DELETE-FIXUP会花费O(lg n)的时间和最多三次旋转，因此RB-DELETE的总时间也是O(lg n)。
图13.7 RB-DELETE-FIXUP的while循环里的情形。黑色结点的color属性为BLACK，深色的阴影结点color属性为RED，浅色阴影结点color属性用c和c’表示，它可能是红色或者黑色的。字母α,β,…,ζ代表任意子树。每一种情形通过改变颜色和/或做一次旋转从左边的状态变成右边的状态。任何x的指向的结点都有一个额外的黑，这个结点可能是双黑或者红黑。只情形2会重复循环。(a)通过交换B和D的颜色和做一次左旋，将情形1转换在2，3或者4。(b)情形2中，通过将D结点着成黑色并将x指向B结点，x指向的额外的黑在树中向上移动。如果我们是通过情形1进入情形1，while循环将会终止，因为新结点x是红黑的，因此它color属性值c是红色。(c)通过交换C结点和D结点的颜色和一次右旋将情形3转换成情形4。(d)情形4通过改变一些颜色和一次左旋(不会破坏红黑树的性质)移除额外的黑，然后循环终止。
练习
13.4-1 证明执行完RB-DELETE-FIXUP，树根一定黑色的。
13.4-2 证明如在RB-DELETE中x和x.p都是红色的，通过调用RB-DELETE-FIXUP性质4被恢复了。
13.4-3 在练习13.3-2中，你发现一查从初始空树通过成功插入key41，38，31，12，19，8的红黑树。现在画出依次删除8，12，19，31，38，41之成功后红黑树。
13.4-4 RB-DELETE-FIUXP的哪一行代码我们将检查了修改哨兵T.nil？
13.4-5 在图13.7的的各种情形中，给出从图示的根到各个子树α，β，…，ζ的黑结点个数，并验证每个个数与变化后的相同。当结点的color属性值是c或者c’,就使用表达式count(c)或者count(c’)表示在你的统计中。
13.4-6 Skelton和Baron教授认为在RB-DELETE-FIXUP情形1开始的时候，x.p结点可能是黑色的。如果这个教授的说法是正确的，那么第5-6行就是错了。证明x.p在情形1开始的时候一定是黑色的，教授们的担心是多余的。
13.4-7 假设结点x通过RB-INSERT插入到红黑树，然后通过RB-DELETE立即删除。结果的红黑树与初始的红黑树一亲吗？验证一下你的答案。
全文下载：第13章 红黑树