jiji1995
jiji1995
2015-12-01 13:30

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

2
  • 算法
  • 数据结构

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

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答