红黑树的删除

2023-12-29 18:29:06

导航链接

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

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

?

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

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

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

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

在这里插入图片描述


?

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

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

在这里插入图片描述


?

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

删除有两个孩子的结点,那就必须从后代中找到一个离它最近的子孙,替换当前结点的值,再删除子孙结点。(子孙替我挡刀)
在这里插入图片描述

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

?
?
?
?


红黑树如何删除结点?

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

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

在这里插入图片描述
?

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

在这里插入图片描述

?

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

在这里插入图片描述

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

?


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

场景一:被删结点无孩子,且被删结点为红色

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

在这里插入图片描述


?

场景二:被删结点无孩子,且被删结点为黑色

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

在这里插入图片描述


?

场景三:被删结点有一个孩子(被删结点一定是红色,子结点为黑色)

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

在这里插入图片描述

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

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

在这里插入图片描述


?

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

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

在这里插入图片描述

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

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

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

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

在这里插入图片描述

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

?


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

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

?

结构1:兄为黑,且有一个子结点为红,与兄结点同一斜边上

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

在这里插入图片描述

上图中的123分别代表其它子树,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进行了右旋,并且互换了5025的颜色。


?

总结

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

文章来源:https://blog.csdn.net/I_just_smile/article/details/135294467
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。