20｜红黑（R-B）树：节点删除后的平衡性调整（二）
王健伟
你好，我是王健伟。
这节课我们接着讨论删除黑色叶子节点导致的红黑树平衡性调整问题。现在还有一种情况我们没有讨论到，那就是待删节点的父节点为黑色，兄弟节点也为黑色且兄弟节点不待任何孩子节点的情况。
随着我的讲解，你也可以回想上节课的思考题，看一看你想到的各种情况和解决思路与我即将开始的讲解是否相同，以及是否有一些情况没有想到。
这节课的标号我们接着上节课来。
待删除节点是左节点或者右节点都可以（下图中用左节点演示），其父节点为黑色，兄弟节点为黑色且不带孩子。
这是个比较特殊的情形，因为调整后黑高度会变小。为了清晰，把 Nil 节点也绘制出来，如图 1 所示：
图1 待删除节点的父节点为黑色，兄弟节点为黑色且不带孩子
操作步骤：
把节点 D 删除。
把 S 节点变为红色，如图 1 中的第 2 个图所示。
单纯看图 1 中的第 2 个图是平衡的，如果此时 P 节点是整个红黑树的根则平衡调整完毕。但如果 P 节点不是整棵红黑树的根，那么，比较图 1 中第 1 个和第 2 个图，会发现第 2 个图比第 1 个图的黑高度减少了 1，所以如果把图 1 中第 1 个图放在一个大的红黑树中，当删除节点 D 并进行平衡性调整后就会出现问题，如图 2 所示：
图2 待删除节点的父节点为黑色，兄弟节点为黑色且不带孩子，作为一棵子树的情形之一
在图 2 的第 1 个图是一个大的红黑树。其中根节点 100 的颜色随意，可红可黑。现在需要删除节点 D，则操作步骤的前两步与前面相同，即：
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
红黑树是一种常用的自平衡二叉查找树，用于实现动态集合的高效操作。本文讨论了在删除节点后，红黑树的平衡性调整问题。特别是当待删节点的父节点和兄弟节点都为黑色且兄弟节点没有任何孩子节点时，需要进行平衡性调整以保持红黑树的性质。文章详细介绍了在这种情况下的操作步骤和调整方法，包括节点颜色的变化和旋转操作。通过图示和详细的步骤说明，读者可以清晰地了解在不同情况下如何进行平衡性调整，以维持红黑树的性质。文章还提供了多个具体的例子，帮助读者更好地理解平衡性调整的过程。此外，文章还强调了红黑树合法性测试代码的重要性，以及对于删除操作的复杂性，有些项目中对红黑树节点的删除操作往往不是真正的删除节点，而是对这种节点做一个删除标记的做法。总的来说，本文对于想深入了解红黑树的工程师和计算机科学学生来说是一篇很有价值的技术参考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(2)
- 最新
- 精选
- Geek_0c9a5e王老师也太牛掰了。每一种数据结构都有具体实现。比不少大学老师敬业的多。
作者回复: 我多付出点时间，就能帮你们省点时间
2023-04-06归属地：河南2 
程序员班吉这个厉害，全网能把红黑树的删除讲明白的几乎没找到。2023-09-24归属地：四川
收起评论