jiji1995
2015-12-01 13:30
采纳率: 100%
浏览 6.9k
已采纳

为什么红黑树中所有的叶子结点为NIL结点且颜色为黑,而不是NULL?NIL结点存在的意义是什么?

我是这么想的.
在红黑树的删除算法中,有这么一种情况图片说明
这种情况下,S的左孩子与右孩子必为NIL,否则原来的红黑树就不平衡.
那么在对P的向上递归过程中,也会出现这种情况,即对应的S及S的孩子全为黑色.
NIL结点的意义之一是不是就在于:向上递归的过程中识别出这种情况?
又或者?
期待您的回答.
图片来自:http://dongxicheng.org/structure/red-black-tree/

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 代码工匠 2016-02-26 13:04
    已采纳

    是的,你的理解完全正确

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • xiaoxiongxiongshi 2020-02-08 11:43

    我来举个例子图片说明。如果使用NULL的话,这个树就是红黑树(带斜杠的节点为红色节点,方块为NIL节点。)。

    但是如果是NIL节点的话,这个树就很显然不满足红黑树的定义了图片说明

    评论
    解决 无用 3
    打赏 举报

相关推荐 更多相似问题