qq_35281162 2017-05-26 04:23
浏览 716

关于红黑树删除对兄弟结点的孩子的颜色的困惑

从红黑树上删除一个结点y,如果y没有孩子而且y是红色的,则直接删除。
如果y有一个孩子(单孩子必定是红色,所以y为黑色),则把y的值替换成孩子的值,移除x即可。
如果y有两个孩子,最终删除的是后继,而后继最多只有一个孩子,回归上面情况。
也就是说最终的问题就是:删除一个无孩子的黑色结点。

书上和网站上给了四种情况(设x为要删除的黑结点,没孩子,w是x的兄弟):
1.兄弟w是红色
2.兄弟w是黑色且w有两个黑孩子
3.兄弟w是黑色且w的孩子左红右黑。
4.兄弟w是黑色且w的右孩子是红的。

我的问题:
x是没孩子的黑结点,所以x的兄弟分支内应该只有一个黑结点啊,那情况23,x的兄弟w已经是黑的了,w怎么可能还有黑色的孩子呢?就是这里万分困惑!

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集
    • ¥15 lammps拉伸应力应变曲线分析
    • ¥15 C++ 头文件/宏冲突问题解决
    • ¥15 用comsol模拟大气湍流通过底部加热(温度不同)的腔体
    • ¥50 安卓adb backup备份子用户应用数据失败
    • ¥20 有人能用聚类分析帮我分析一下文本内容嘛
    • ¥15 请问Lammps做复合材料拉伸模拟,应力应变曲线问题
    • ¥30 python代码,帮调试,帮帮忙吧
    • ¥15 #MATLAB仿真#车辆换道路径规划
    • ¥15 java 操作 elasticsearch 8.1 实现 索引的重建