vlambda博客
学习文章列表

对红黑树进行删除操作时，始终要考虑到删除某个节点后是否违背了红黑树的性质，因此将红黑树的性质列在下面：

在介绍节点的删除操作和节点颜色校正之前，首先对涉及到的节点的名称做如下约定：

P：最初要删除的节点，一般将问题转化为删除其后继节点。

X：原始待处理节点P的中序前驱节点或中序后继节点，前驱节点和后继节点选择其一都可以，X即为当前待删除节点。

N：前驱节点或后继节点的孩子节点（前驱节点或后继节点最多只有一个孩子节点，后面将会进行分析）。

S：节点P的另一个孩子节点。

L：S节点的左孩子节点。

R：S节点的右孩子节点。

在对红黑树进行删除操作时，首先要确定待删除节点有几个孩子，

❶ 如果节点P没有子节点，则将P直接删除。

❷ 如果节点P有一个子节点，则将此子节点替换到P的位置，然后删除节点P。

❸ 如果节点P有两个孩子，不能直接删除该节点。而是要先找到该节点的中序前驱（该节点左子树中最大的节点，此前驱节点最多只有一个左子节点）或者中序后继（该节点右子树中最小的节点，此后继节点最多只有一个右子节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除，前驱节点和后继节点选择其一都可以（我们将这个被选择的节点记为节点X，这样与后面的例子中的记号也保持一致）。

由于前驱和后继至多只有一个孩子节点，这样就把删除两个孩子的结点转为删除一个孩子的结点。在删除的过程中，我们只关心树是否仍然保持红黑树的性质，数据是否组织正确，而不关心这个结点是最初要删除的结点还是我们从中复制出值的那个结点。

【注意】以上删除操作时没有考虑待删除的目标节点的颜色，删除完成后还需要根据目标节点的颜色对红黑树进行颜色修正，使得最终的树满足红黑树的性质（尤其是性质5，在进行节点删除时常常出现经过某个节点到达叶子节点的这些路径中黑色节点的数目不相等的情况，这时就需要自底向上逐步修正现存节点的颜色）。

至于为什么中序前驱或中序后继最多只有一个孩子节点，可画图进行分析。

如图1所示：利用二叉树的中序遍历，可得节点P的中序前驱节点为g，中序后继节点为e，并且中序前驱节点和中序后继节点至多只有一个孩子节点。

❶ 假如节点P的中序前驱节点g还有2个孩子节点分别为n1（左子节点）和n2（右子节点），那么节点b的中序前驱会成为节点n2，而不再是g节点。

❷ 假如节点P的中序前驱节点g还有1个孩子节点n1（左子节点），那么节点b的中序前驱仍然是g节点。

❸ 假如节点P的中序前驱节点g还有1个孩子节点n2（右子节点），那么节点b的中序前驱会成为节点n2，而不再是g节点。

综上，某个节点的中序前驱节点要么没有孩子节点，要么只有一个左孩子节点。

同理，某个节点的中序后继节点要么没有孩子节点，要么只有一个右孩子节点。

此结论在后面的节点删除操作中会经常用到，假如需要删除图1中的P节点，则一般转化为对其前驱节点g或后继节点e进行删除操作（选择前驱或后继节点中的一个均可，原理都一样。因此，在后面将以删除P的中序后继节点为例进行说明，删除中序前驱的做法与此类似）。记转换后的待删除节点为X，则在删除X时还要根据X的颜色对其他节点进行颜色修正。

红黑树删除操作的复杂度在于删除节点时的颜色修正问题，当删除的节点是红色时，直接拿其孩子节点补空位即可。因为删除红色节点，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多，本节对节点颜色修正的情况进行说明，后面的文章中会具体介绍如何进行节点颜色的修正。

首先来看情形【A】和情形【B】：

图2：情形【A】和情形【B】

对于情形【B】，删除黑色叶子节点后，就会违背性质5，这可以举例来说明，如图3所示：将删除节点P的操作转化为删除P的中序后继节点X，然而X是黑色的，当X被删除后经过节点P到达叶子节点的所有路径中，黑色节点的数目不相等，破坏了性质5，因此需要对节点进行颜色修正。

接着来看情形【C】：删除的节点P有两个子节点，此时，我们通过将P和它的后继节点X的值交换的方式，将删除节点P转换为删除后继节点X，而后继节点X存在以下三种情况：

【C1】: X是叶子节点且为红色，对应情形A。

【C2】: X是叶子节点且为黑色，对应情形B。

【C3】: X有一个子节点N，对应情形D（情形D在后面介绍）

至于【C1】【C2】【C3】这三种情况中，节点X是叶子节点或者是有一个子节点的原因已经在本文第3节进行了举例说明。

最后来说一说情形【D】：删除的节点P下面有一个子节点 S，此时，将P和S的值进行交换，巧妙的将删除P变为删除S，如果S是叶子节点，这样D这种情况就会转换为A, B这两种情况：

【D1】：P为黑色，S为红色，对应情形 A。

【D2】: P为黑色或红色，S为黑色，对应情形 B。

到此，关于红黑树节点删除操作的基本思路，以及几种基本的情况已经介绍完毕，删除节点后相关节点的颜色修正问题将在后面的文章中进行详细的介绍。