20 红黑（R B）树：节点删除后的平衡性调整（二）
你好，我是王健伟。
这节课我们接着讨论删除黑色叶子节点导致的红黑树平衡性调整问题。现在还有一种情况我们没有讨论到，那就是待删节点的父节点为黑色，兄弟节点也为黑色且兄弟节点不待任何孩子节点的情况。
随着我的讲解，你也可以回想上节课的思考题，看一看你想到的各种情况和解决思路与我即将开始的讲解是否相同，以及是否有一些情况没有想到。
这节课的标号我们接着上节课来。
- 待删除节点是左节点或者右节点都可以（下图中用左节点演示），其父节点为黑色，兄弟节点为黑色且不带孩子。
这是个比较特殊的情形，因为调整后黑高度会变小。为了清晰，把Nil节点也绘制出来，如图1所示：
操作步骤：
- 把节点D删除。
- 把S节点变为红色，如图1中的第2个图所示。
单纯看图1中的第2个图是平衡的，如果此时P节点是整个红黑树的根则平衡调整完毕。但如果P节点不是整棵红黑树的根，那么，比较图1中第1个和第2个图，会发现第2个图比第1个图的黑高度减少了1，所以如果把图1中第1个图放在一个大的红黑树中，当删除节点D并进行平衡性调整后就会出现问题，如图2所示：
在图2的第1个图是一个大的红黑树。其中根节点100的颜色随意，可红可黑。现在需要删除节点D，则操作步骤的前两步与前面相同，即：
- 把节点D删除。
- 把S节点变为红色，如图2中的第2个图所示。
但目前的这棵红黑树变得不平衡了，确切地说已经不是红黑树了，理由是不符合红黑树性质4——因为选择100->P->Nil这个路径，黑高度比选择100->120->110->Nil这条路径的黑高度少了1。
因为图2中的第1个图是一棵红黑树，或者说一棵红黑子树，而P、D、S这三个节点都为黑色，所以，节点120作为节点P的兄弟节点肯定得存在，而且120的两个孩子节点也肯定得存在，否则肯定不是个红黑树，虽然图2中绘制的节点120是黑色，但但节点120是黑色还是红色，并不确定，要分两种情况来看，节点120是黑色和节点120是红色。
第一种情况：如果节点120是黑色。
此时还要细分，前两步与前面相同不赘述，我从第三步说起。
细分1：如果120的父节点100是红色，参考下图3，图中四边形代表该节点可红可黑且带的孩子随意，只要满足红黑树性质。此时额外的步骤为：
- 以100为根左旋，如图3中的第3个图所示。
如果此时120的左孩子110为红色，参考下图4中的第1个图所示的110这个节点，那么110必定带两个黑色节点比如是105和115，此时还需要多进行一步调整：
- 则将节点110和他的两个孩子都变色。即110变为黑色，105和115变为红色。如图4中的第4个图。
细分2：节点120的父亲为黑色，左孩子为红色，右孩子为黑色，如图5第1个图，此时额外的操作步骤为：
- 以节点120为根右旋，如图5中的第3个图所示。
- 将节点110的颜色改变，如图5中的第4个图所示。
- 以节点100为根左旋，如图5中的第5个图所示。
细分3：节点120的父亲为黑色，右孩子为红色，左孩子用四边形代表该节点可红可黑且带的孩子随意，只要满足红黑树性质即可，如图6，此时额外的操作步骤为：
- 以节点100为根左旋，如图6中的第3个图所示。
- 将节点130的颜色改变，如图6中的第4个图所示。
细分1的反向：与图3和4相反，将根的左右子树调换位置，注意，D节点和S节点谁是P节点的左孩子谁是P节点右孩子都可以，如图7和8所示：
细分2的反向：与图5相反，将根的左右子树调换位置，注意，D节点和S节点谁是P节点的左孩子谁是P节点的右孩子都可以，如图9所示：
细分3的反向：与图6相反，将根的左右子树调换位置，注意，D节点和S节点谁是P节点的左孩子谁是P节点的右孩子都可以，如图10所示：
细分4：节点120的父亲和全部孩子节点皆为黑色。如图11所示：
此时并不需要理会110和130下面是否还其他红色子节点。图11中进行了一步操作：
- 将P节点的兄弟节点120调整为红色。如图11中的第2个图。
此时如果100是整个红黑树的根节点，则平衡调整完毕。但如果100不是整个红黑树的根节点，则有些麻烦，因为经过调整后，虽然以100为根的这棵子树是平衡的，但是该子树的黑高却从3降为了2，黑高的减少意味着必须要向树根的方向继续调整，调整的方法就是将节点100当做新的P节点，继续根据上述标号7所描述的各种情形进行调整（类似于递归式的调整），因为不要忘记，标号7所描述的才是黑高减少时的红黑树平衡调整方法。
参考下图12中的第2个图想一想，就可以理解这里说的是什么意思了。
下面来看一个例子增强一下感受，如下图13：
如果要删除图13中左下角的节点8，那么调整为红色的节点是12和52，但是，调整还没完成，因为以32为根的子树的黑高变少了，所以也必须调整以3444为根的子树的黑高，那么我们按照下面的步骤去做。
- 以3444为根右旋，同时把3444节点变为红色，把其左孩子3299变为黑色，如图14所示：
- 以1212为根左旋，如图15所示：
不难看出，因为黑高的变小，导致平衡性调整不断向根的方向进行直到左右子树的黑高调整相同才停止。
情况2：如果节点120是红色
细分1：因为节点120是红色，那么节点120的父亲节点肯定会是黑色，两个孩子110、130肯定都是黑色，而左孩子110带了两个黑色孩子节点（节点105和115），130其下带什么节点无所谓。如图16中的图1所示：
操作步骤如下：
- 把节点D删除。
- 把S节点变为红色，如图16中的第2个图所示。
- 以节点100为根左旋，如图16中的第3个图所示。
- 将节点120变为黑色，节点100变为红色，如图16中的第4个图所示。
- 将节点100再变回黑色，节点110变为红色，如图17中的第5个图所示。
细分2：如果节点105是个红色节点，那么该节点下肯定会带两个黑色节点（节点102和107）。115是个黑色节点（其下带不带节点没所谓）。如图17中的图1所示：
则除了细分1所示的前面4步变换外，还需要增加额外3步变换如下：
- 以节点110为根右旋。如图17中的第5个图所示。
- 将节点105变为黑色，节点110变为红色，如图17中的第6个图所示。
- 以节点100为根左旋。如图17中的第7个图所示。
细分3：如果节点115是个红色节点，那么该节点下肯定会带两个黑色节点（节点112和117）。此时不管105是什么颜色以及带什么子节点，只要满足红黑树性质即可。这里用四边形代表该节点颜色和孩子节点随意，也就是可红可黑且带的孩子随意。如图18中的图1所示：
则除了细分1所示的前面4步变换外，还需要增加额外1步变换：以节点100为根左旋，如图18中的第5个图所示。
细分1的反向：与细分1的图16相反，将根的左右子树调换位置，注意，D节点和S节点谁是P节点的左孩子谁是P节点的右孩子都可以，如图19所示：
细分2的反向：与细分2的图17相反，将根的左右子树调换位置，也就是D节点和S节点谁是P节点的左孩子，谁是P节点的右孩子都可以，如图20所示：
细分3的反向：与细分3的图18相反，将根的左右子树调换位置，注意，D节点和S节点谁是P节点的左孩子谁是P节点的右孩子都可以，如图21所示：
特别提示，如果将来在调整红黑树平衡时遇到未处理自己又不知道如何处理的情况，建议直接使用这个网站构造出相应的红黑树情形（对节点的增加删除等），然后看该网站怎样针对这种红黑树情形做平衡性调整，再根据调整细节来书写处理代码。
另外，红黑树节点删除后平衡性调整代码应该说是整个数据结构与算法知识中最难的知识之一，所以不可避免的会存在程序代码因为考虑不周产生的错误或者考虑不够完善导致遗漏没有处理的情形，只需要不断完善代码，把错误修正，把遗漏的情形补充完善即可。后面会有专门一节课来书写红黑树合法性测试代码来验证调整完平衡后的树是否是一棵合法的红黑树，通过这种验证，可以很方便的找到红黑树插入、删除节点时产生的代码编写错误。
最后，我们来说代码的编写。在类模板RBTree的定义中，继续加入代码，包括DeleteElem()、BlackLeaf_TuneBanance()成员函数(参见课件)。
在main主函数中继续加入如下代码，测试删除一个节点时的效果：
新增代码的执行结果如下：
通过前面介绍的“可视化数据结构算法演示”网站，可以看到删除节点23后，得到的红黑树如图22所示。
再次强调，实际应用中，考虑到红黑树删除操作的复杂性，有些项目中对红黑树节点的删除操作往往不是真正的删除节点，而是对这种节点做一个删除标记，这种做法是否值得借鉴呢？当然由你自己决定。
红黑树合法性测试代码
你可以看到，红黑树插入和删除节点并进行平衡性调整的代码实现是比较复杂的，情况比较多变，尤其是删除一个黑色叶子节点时面临的情况更是复杂。作为上述代码的编写者，如果有些调整红黑树平衡的情形没有考虑到，则很可能导致红黑树调整平衡出现错误，比如调整完后已经不再是一棵红黑树。为此，可以专门书写一个RBTree类模板的成员函数来验证一棵调整完平衡后的树是否是红黑树，以此来证明上述调整红黑树平衡的代码没有错误。
回忆一下，红黑树的平衡性指的是对于每个节点，从该节点到达其所能够到达的叶子节点的所有路径都包含相同数量的黑色节点。不难想象，对于红黑树中的每个“叶子节点”或者“仅有左子树或仅有右子树的节点”，黑高都应该完全相同。计算节点黑高的成员函数名叫做Calc_BH()，代码参见课件。
此外，红黑树要求根节点必须为黑色以及父子关系的两个红色节点不能紧挨着，这些判断代码以及针对Calc_BH成员函数的调用代码都可以放在levelOrder()成员函数中完成。修改后的levelOrder()代码参见课件。
当创建一棵红黑树，对红黑树节点进行插入、删除等操作后，调用levelOrder遍历这棵红黑树的时候，如果这不是一棵合法的红黑树，则可能的结果就会如下：
小结
本节课我向你详细介绍了从红黑树中删除节点的操作，因为红黑树删除节点后的平衡性调整操作几乎算得上是整个课程中最难的主题，所以我用了大量的篇幅阐述。看起来非常多，其实删除操作最终就分为两种情况。
- 删除的是叶子节点；
- 删除的是仅有左子树或仅有右子树的节点。如果最终删除的是一个红色节点，不需要进行平衡性调整。如果最终删除的是一个黑色节点，因为黑色节点的删除会导致黑高的变化，必须进行平衡性调整。
删除节点平衡性调整的各种情况我总结成了下图，你只需要简单理解这些内容即可。其实，不同的资料针对平衡性调整的方法不一，但我认为，从实现代码的角度来讲，我所阐述的调整方法更容易理解：
同时，我也为你提供了一段红黑树合法性测试代码，帮助你测试调整平衡后的红黑树是否会变得不合法，这样会更容易帮你找到代码编写中的错误。
对于红黑树的用途，我的《C++新经典：Linux C++通信架构实战》一书中所讲解的epoll这种支持高并发的典型网络服务器通信技术的部分，就使用了红黑树这种数据结构来保存客户端的TCP连接，如果你有兴趣学习网络通信编程可以阅读这本书。
此外，定时器、时间轮等也常采用红黑树来实现，Linux内核中有很多地方比如文件描述符、进程调度、内存管理等都用到了红黑树，有兴趣可以通过搜索引擎来进一步了解。
课后思考
回想一下，你是否能够理解本节所讲解的各种删除节点后的红黑树平衡性调整情况，是否能看懂本节所提供的课件代码？
另外，你是否曾经手撕过红黑树或者听闻甚至经历过面试手撕红黑树？有没有觉得这个问题很无聊，很难为人？如果面试中真让你手撕红黑树，你怎么回答？
欢迎你在留言区分享自己的思考和经历，如果觉得有所收获，也可以把课程分享给更多的朋友一起学习进步。我们下节课见！
- Geek_0c9a5e 👍（2） 💬（1）
王老师也太牛掰了。每一种数据结构都有具体实现。比不少大学老师敬业的多。
2023-04-06 - 程序员班吉 👍（0） 💬（0）
这个厉害，全网能把红黑树的删除讲明白的几乎没找到。
2023-09-24