红黑树（下）完整删除过程

深藏阁楼爱情的钟 2023-10-18 22:33 110阅读 0赞

红黑树一般用在较为底层的地方作为保证效率的数据结构，

且红黑树的删除算法特别复杂！了解即可，手写出的难度较大。

对于删除算法，很多书上没有提及，或者写的很混乱。

全网亦没有一篇文章通俗易懂的讲清楚了其中过程，

此文也是参考了几篇大牛的博文，部分为笔者原创，部分为引用整合。

红黑树的删除其实就是基于二叉搜索树的删除上加入一个调色过程。

在弄清楚红黑树的删除操作之前，需要明白二叉搜索树的删除方法。

首先要明白几个概念：

直接前继：当前节点左子树的最右节点。此节点是当前节点左子树中的最大值，也就是左子树区间中值最接近当前节点的节点。

直接后继：当前节点右子树的最左节点。此节点是当前节点右子树中的最小值，也就是右子树区间中值最接近当前节点的节点。

所以，二叉搜索树的删除思路就是用所要删除的直接前继或者直接后继节点来代替该节点即可。这样整颗二叉搜索树仍然会保持有序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70][]

接下来以《手撕JAVA（十五）》一文中建立的较为复杂的那棵红黑树为例进行删除演示整个删除过程的算法可总结为：

1.当被删除元素为红时，对五条性质没有什么影响，直接删除。  
2.当被删除元素为黑且为根节点时，直接删除。  
3.当被删除元素为黑，且有一个右子节点为红时，将右子节点涂黑放到被删除元素的位置。

4.当被删除元素为黑，且兄弟节点为黑，兄弟节点两个孩子也为黑，父节点为红，此时，交换兄弟节点与父节点的颜色；NIL元素是指每个叶节点都有两个空的，颜色为黑的NIL元素，需要他的时候就可以把它看成两个黑元素，不需要的时候可以忽视他。

5.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的右支为红色，这个时候需要交换兄弟与父亲的颜色，并把父亲涂黑、兄弟的右支涂黑，并以父节点为中心左转。

6.当被删除元素为黑、并且为父节点的左支，且兄弟颜色为黑，兄弟的左支为红色，这个时候需要先把兄弟与兄弟的左子节点颜色互换，进行右转，然后就变成了规则5一样了，在按照规则5进行旋转。

7.当被删除元素为黑且为父元素的右支时，跟情况5.情况6 互为镜像。  
8.被删除元素为黑且兄弟节点为黑，兄弟节点的孩子为黑，父亲为黑，这个时候需要将兄弟节点变为红，再把父亲看做那个被删除的元素（只是看做，实际上不删除），看看父亲符和哪一条删除规则，

![Center][]

##  ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190729144927213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[Center]: https://img-blog.csdn.net/20131106205029515?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3ptcGVyc2lzdA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center