红黑树的删除

导航链接

    红黑树的性质
    红黑树的旋转、变色
    红黑树的插入
    红黑树的删除

 
友情提醒，接下来你可能会很困，因为红黑树删除结点真麻烦。。。

 

二叉搜索树如何删除结点？

我们先看看，二叉搜索树是怎样删除结点，从中我们又能获得怎样的启发。二叉搜索树的删除操作比较简单，可以分为以下三种场景。

场景一：删除没有孩子的结点

删除没有孩子的结点，对排序并不会产生任何影响，所以可直接删除(呃，么有孩子的结点，也就么得牵挂)。

---

 

场景二：删除有一个孩子的结点

删除有一个孩子的结节，则可以让孩子结点顶替当前结点（子承父业），继续保持原有排序。

---

 

场景三：删除有两个孩子的结点

删除有两个孩子的结点，那就必须从后代中找到一个离它最近的子孙，替换当前结点的值，再删除子孙结点。（子孙替我挡刀）

至于选取哪个最近的结点，无特殊规定。比如在Min<...<Y<X<Z<...<Max排序中你删除X，你即可以选择Y代替，也可以选择Z代替。二叉搜索树中，称Y为后继，Z为前驱。

 
 
 
 

---

红黑树如何删除结点？

但红黑树的删除没有那么简单，因为上述的删除操作，都可能破坏红黑树的性质。

如果按场景一方式删除结点800，会导致200->400->600->leaf这条路径比200->400->600->500->550->leaf少一个根结点，从而违背了 《从任意结点到其每个叶子的所有路径都包含相同数目的黑色结点》。

 

按场景二的方式删除下图的中800结点，使用其唯一的孩子结点900代替，会导致600、900成为两个连续的红结点。从而违背了 《从每个叶子到根的所有路径上不能有两个连续的红结点》。

 

按场景三的方式删除下图的中400结点，用最近的结点325的拷贝到当前位置，再将325移除，会导致300、310成为两个连续的红结点。也违背了 《从每个叶子到根的所有路径上不能有两个连续的红结点》。

上面只是列举了部分例子，有些时候可能违背的性质会更多。但二叉搜索树的删除方式并不是毫无借鉴可言，我们可以在它的操作上，再添加一些维护红黑树性质的动作。也就是说，红黑树删除结点 = 二叉搜索树删除结点 + 旋转、变色。

 

---

红黑树的删除主要有以下四种场景。

场景一：被删结点无孩子，且被删结点为红色

因为无孩子的红色结点一定会在树的最下层，删除之后也不会影响树的高度，所以可以直接删除。

---

 

场景二：被删结点无孩子，且被删结点为黑色

如果一个黑色结点没有孩子，直接删除会使一条支路上黑色结点数量减一，需要适当调整树的结构，后面再说。

---

 

场景三：被删结点有一个孩子（被删结点一定是红色，子结点为黑色）

首先，只有一个孩子的结点，不可能是黑色，因为这样会导致从该结点出发，到叶子结点的路径高度不一致。

所以这样的结点只能是红色，并且根据 《从每个叶子到根的所有路径上不能有两个连续的红结点》 可以推断，其子结点一定是黑色。

删除这样的结点也很简单，只需要让子结点覆盖当前结点，同样变成黑色即可。这样只是少了一个红节点，不会破坏树的结构。

---

 

场景四：被删结点有两个孩子

当删除有两个孩子的结点时，和二叉搜索树删除一样，也是先找到后继结点，替换当前结点的值，进而转变成删除后继结点。值得注意的是，只需要替换值，不需要替换颜色。如图，删除310结点。

而无论删除哪个后继结点，又会回到之前的三种场景，比如说：

删除上图中的50结点，它有两个孩子，后继结点为25。删除它又等于回到了场景三，被删结点有一个孩子。

删除上图中的320结点，它有两个孩子，后继结点为315。删除它又等于回到了场景二，被删结点无孩子，结点为黑色。

删除上图中的325结点，它有两个孩子，后继结点为324。删除它又等于回到了场景一，被删结点无孩子，结点为红色。如图：

所以重点还是回到了怎样删除无孩子的黑结点。

 

---

怎样删除无孩子的黑结点？

通过场景二的图片不难看出，删除一个没有子结点的黑结点，势必会造成二叉树的一条支路变短。如果想平衡树高，就必须结合待删除结点的父（Parent）、兄（Brother）、侄子（或叫外甥，Nephew）结点综合考虑，如何通过旋转、变色，恢复红黑树的特性。

 

结构1：兄为黑，且有一个子结点为红，与兄结点在同一斜边上

兄结点为黑色，兄结点有一个子结点为红色，并且兄结点与该结点在同一条斜边上。这时我们不需要关心父结点的颜色，可红可黑，所以将它染成从红到黑的渐变色。

上图中的1、2、3分别代表其它子树，D结点就是待删除结点。D结点被删除后，会用一个双黑结点NIL代替它（一个空结点，但它权值为2，代表着两个黑结点）。接下来就是平衡的过程，把这个多出来的黑色权值扔掉，使它成为一个普通的黑结点，最终整个删除操作完成。

对于这样的结构，需要进行如下转换：

1. 将父结点右旋（待删除结点为右结点，如果为左结点，则改为左旋）。
2. 父结点与兄结点互换颜色，并且将侄结点变成黑色。
3. 将双黑结点变成普通的叶结点。

如图：

完整动画展示如下：

---

 

结构2：兄为黑，且有一个子结点为红，与兄结点不在同一斜边上

兄结点为黑色，兄结点有一个子结点为红色，并且兄结点与该结点不在同一条斜边上。这时候我们也无需关注父结点的颜色，只需要将其转换成结构1，具体操作如下：

1. 将兄点左旋（侄结点为右孩子，如果为左孩子，则改为右旋）。
2. 兄结点与侄结点互换颜色。

如图：

完整动画展示如下：

---

 

结构3：兄为黑，且没有红色的子结点，父为红

兄结点为黑色，并且没有红色的子结点，并且父结点为红色。

这样结构处理相对简单：

1. 将兄结点变成红色。
2. 将父结点变成黑色。
3. 将双黑结点变成普通叶结点。

因为兄结点没有红色子结点，所以它是可以变成红色的。这样左右两边高度同时减一，再让父结点由红变黑，高度又和原来一样了。

示例：

删除结点400，先将后继节点300的值填入到400结点，进行删除300结点。接下来，用双黑结点代替300，组成结构3。直接将兄弟结点变红，父结点变黑，就完成了删除。

---

 

结构4：兄为黑，且没有红色的子结点，父为黑

兄结点为黑色，并且没有红色的子结点，并且父结点为黑色。

面对这样的结构，无论怎样变化，兄结点那一侧永远都会多一个黑结点，所以只能将兄结点变成红色，让父结点变成双黑结点。这样，就让父结点成为了待删除的结点，让父结点继续再与它的兄结点、父结点去判断，调整。

示例：

删除结点10时，父、兄结点都为黑色，没有红色的侄结点。进行的操作就是，用双黑结点替换待10，再让兄结点35变成红色，父结点25成为双黑结点。再继续对25进行删除操作，进行其它场景判断。

---

 

结构5：兄为红，父为黑

兄结点为红色，那么它的父结点一定为黑色，因为 《从每个叶子到根的所有路径上不能有两个连续的红结点》。并且，它的孩子，不管有没有，都会是黑色。

这样的结构，删除操作也能一步到位，具体如下：

1. 父结点右旋转（待删除为右孩子，如果为左孩子，则为左旋）。
2. 将父结点与兄结点交换颜色。
3. 将双黑结点变成普通叶结点。

这样，由于旋转导致待删除结点那一侧增加了一个黑结点，所以能就去掉双黑结点的权值，使其变成普通结点啦。

示例：

待删除结点100的兄结点25是红色，且父结点50是黑色，所以删除时，让50进行了右旋，并且互换了50与25的颜色。

---

 

总结

好了，到这红黑树的删除总算讲完了，不知道你有没有睡着。重点是，红黑树的删除 = 删除 + 维护，无论怎样删除结点，都会动态的调整树高。 如果有发现不对的地方，烦请留言，我会第一时间纠正，谢谢。