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 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
    • ¥50 NT4.0系统 STOP:0X0000007B
    • ¥15 想问一下stata17中这段代码哪里有问题呀
    • ¥15 flink cdc无法实时同步mysql数据
    • ¥100 有人会搭建GPT-J-6B框架吗?有偿