傻瓜都能看懂,30张图彻底理解红黑树! (5)

我们把替换结点换到了删除结点的位置时,由于替换结点是红色,删除了也不会影响红黑树的平衡,只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。

处理:颜色变为删除结点的颜色。

删除情景 2:替换结点是黑结点。

当替换结点是黑色时,我们就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点,来做不同的旋转操作,使树重新平衡。

删除情景 2.1:替换结点是其父结点的左子结点。

删除情景 2.1.1:替换结点的兄弟结点是红结点。

傻瓜都能看懂,30张图彻底理解红黑树!

图 21:删除情景 2.1.1

若兄弟结点是红结点,那么根据性质 4,兄弟结点的父结点和子结点肯定为黑色,不会有其他子情景,我们按图 21 处理,得到删除情景 2.1.2.3(后续讲解,这里先记住,此时 R 仍然是替代结点,它的新的兄弟结点 SL 和兄弟结点的子结点都是黑色)。

处理:将 S 设为黑色,将 P 设为红色,对 P 进行左旋,得到情景 2.1.2.3,进行情景 2.1.2.3 的处理。

删除情景 2.1.2:替换结点的兄弟结点是黑结点。

当兄弟结点为黑色时,其父结点和子结点的具体颜色也无法确定(如果也不考虑自底向上的情况,子结点非红即为叶子结点Nil,Nil结点为黑结点),此时又得考虑多种子情景。

删除情景 2.1.2.1:替换结点的兄弟结点的右子结点是红结点,左子结点任意颜色。

傻瓜都能看懂,30张图彻底理解红黑树!

图 22:删除情景 2.1.2.1

即将删除的左子树的一个黑色结点,显然左子树的黑色结点少 1 了,然而右子树又有红色结点,那么我们直接向右子树“借”个红结点来补充黑结点就好啦,此时肯定需要用旋转处理了,如图 22 所示。

处理:将 S 的颜色设为 P 的颜色,将 P 设为黑色,将 SR 设为黑色,对 P 进行左旋。

平衡后的图怎么不满足红黑树的性质?前文提醒过,R 是即将替换的,它还参与树的自平衡,平衡后再替换到删除结点的位置,所以 R 最终可以看作是删除的。

另外图 2.1.2.1 是考虑到第一次替换和自底向上处理的情况,如果只考虑第一次替换的情况,根据红黑树性质,SL 肯定是红色或为 Nil,所以最终结果树是平衡的。

如果是自底向上处理的情况,同样,每棵子树都保持平衡状态,最终整棵树肯定是平衡的。后续的情景同理,不做过多说明了。

删除情景 2.1.2.2:替换结点的兄弟结点的右子结点为黑结点,左子结点为红结点。

兄弟结点所在的子树有红结点,我们总是可以向兄弟子树借个红结点过来,显然该情景可以转换为情景 2.1.2.1。如图 23 所示:

傻瓜都能看懂,30张图彻底理解红黑树!

图 23:删除情景 2.1.2.2

处理:将 S 设为红色,将 SL 设为黑色,对 S 进行右旋,得到情景 2.1.2.1,进行情景 2.1.2.1 的处理。

删除情景 2.1.2.3:替换结点的兄弟结点的子结点都为黑结点。

好了,此次兄弟子树都没红结点“借”了,兄弟帮忙不了,找父母呗,这种情景我们把兄弟结点设为红色,再把父结点当作替代结点,自底向上处理,去找父结点的兄弟结点去“借”。

但为什么需要把兄弟结点设为红色呢?显然是为了在 P 所在的子树中保证平衡(R 即将删除,少了一个黑色结点,子树也需要少一个),后续的平衡工作交给父辈们考虑了,还是那句,当每棵子树都保持平衡时,最终整棵总是平衡的。

傻瓜都能看懂,30张图彻底理解红黑树!

图 24:情景 2.1.2.3

处理:将 S 设为红色,把 P 作为新的替换结点,重新进行删除结点情景处理。

删除情景 2.2:替换结点是其父结点的右子结点。

好啦,右边的操作也是方向相反,不做过多说明了,相信理解了删除情景 2.1 后,肯定可以理解 2.2。

删除情景 2.2.1:替换结点的兄弟结点是红结点。

傻瓜都能看懂,30张图彻底理解红黑树!

图 25:删除情景 2.2.1

处理:将 S 设为黑色,将 P 设为红色,对 P 进行右旋,得到情景 2.2.2.3,进行情景 2.2.2.3 的处理。

删除情景 2.2.2:替换结点的兄弟结点是黑结点。

删除情景 2.2.2.1:替换结点的兄弟结点的左子结点是红结点,右子结点任意颜色。

傻瓜都能看懂,30张图彻底理解红黑树!

图 26:删除情景 2.2.2.1

处理:将 S 的颜色设为 P 的颜色,将 P 设为黑色,将 SL 设为黑色,对 P 进行右旋。

删除情景 2.2.2.2:替换结点的兄弟结点的左子结点为黑结点,右子结点为红结点。

傻瓜都能看懂,30张图彻底理解红黑树!

图 27:删除情景 2.2.2.2

处理:将 S 设为红色,将 SR 设为黑色,对 S 进行左旋,得到情景 2.2.2.1,进行情景 2.2.2.1 的处理。

删除情景 2.2.2.3:替换结点的兄弟结点的子结点都为黑结点。

傻瓜都能看懂,30张图彻底理解红黑树!

图 28:删除情景 2.2.2.3

处理:将 S 设为红色,把 P 作为新的替换结点,重新进行删除结点情景处理。

综上,红黑树删除后自平衡的处理可以总结为:

自己能搞定的自消化(情景 1)

自己不能搞定的叫兄弟帮忙(除了情景 1、情景 2.1.2.3 和情景 2.2.2.3)

兄弟都帮忙不了的,通过父母,找远方亲戚(情景2.1.2.3和情景2.2.2.3)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpdfsy.html