19 红黑（R B）树：节点删除后的平衡性调整（一）

你好，我是王健伟。

上次我和你分享了红黑树的概念和基础实现代码，以及向红黑树插入新节点后进行平衡性调整的方法。这次我将继续和你分享另一个重要的话题——从红黑树中删除一个节点后的平衡性调整。

红黑树的删除操作比较繁琐和复杂，所以我建议，如果能不实际删除则不做实际删除，比如将要删除的节点做个“删除”标记这样的解决方案看是否能解决问题。当然，本节课讲述的是如何将节点从红黑树中真正删除。

红黑树删除操作后的平衡性调整及实现代码

从红黑树中删除节点同样会让红黑树失衡，从而需要进行平衡性调整。前面曾经详细讲解过平衡二叉树（AVL）的节点删除操作，分三个主要步骤。

对于红黑树的节点删除操作，同样分为3个主要步骤，而且其中前2个步骤与平衡二叉树的节点删除操作相同，实现代码也基本相同，需要注意的就是红黑树中有一个parent指针需要正确地指向父节点。而第3个步骤的平衡性调整除了进行旋转外还可能根据需要对节点进行变色操作。

首先回顾一下对节点进行删除操作所分的几种情况（这些知识前面已经讲解过）——针对所要删除的节点的子节点个数不同，有如下几种情况需要处理。

要删除的节点是叶子节点，则直接把该节点删除并将指向该被删除节点的父节点的相应孩子指针设置为空。
要删除的节点有左子树或右子树（单分支节点），则把该节点删除并更新指向该被删除节点的父节点的相应孩子指针，让该指针指向要删除节点的非空的子节点（节点替换），同时该非空子节点的父节点指针也要做正确指向。
要删除的节点左子树和右子树都不为空，则首先找到这个要删除节点的左子树的最右下节点，当然，也可以找这个要删除节点右子树的最左下节点；其次，将该节点的值替换到要删除的节点上；最后，把刚刚找到的那个左子树的最右下节点，或者右子树的最左下节点删除即可。当然，被删除的节点如果还带有子节点，则要正确地设置该子节点的父节点指针指向。

所以，对于删除节点来说，最终删除的节点也只分两种情况。

因为对于删除左右子树都不为空的节点，最终是要转换成上述两种情况之一的。

举个例子，图1中第1张图所示的红黑树是经过了若干次插入节点和删除节点操作后所形成的模样。现在，要对这棵红黑树的某节点进行删除操作，在不考虑删除节点后需要进行平衡性调整的情况下，看一看删除节点的几种情况。

如果要删除节点9：节点9是个纯叶子节点，可以直接删除掉。删除节点后得到的结果如图1中第2张图所示。
如果要删除节点8：节点8是节点6的右孩子并且有右孩子9，删除节点8时，让节点8的父亲节点6的右孩子指向节点9，节点9的父指针也要指向节点6。删除节点8后得到的结果如图1中第3张图所示。
如果要删除节点6：节点6的左右子树都不为空，找到节点6左子树的最右下节点4，用右下节点的值4覆盖节点6中的值6（值6变成了值4），最后再把最右下这个节点4删除。当然还要注意到节点4还带了一个左节点3，因此节点4的父节点2要指向节点3。当然，节点3的父指针也要指向节点2。删除节点后得到的结果如图1中的第4张图所示。