红黑树性质3，叶子节点（最后的空节点，而不是左右子树都为空的节点）是黑色的

来源：13-4 红黑树的基本性质和复杂度分析

Lymun

2021-03-29

请问老师，红黑树的性质3：“每一个叶子节点（最后的空节点，而不是左右子树都为空的节点）是黑色的。”这里，最后的空节点到底怎么理解呢？还有就是网上的说法：叶子是NIL节点，这里的NIL节点又是什么呢？

写回答

1回答

liuyubobobo

2021-03-29

已采纳

nil 节点就是空节点。

  1
 /
2

在这棵树中，在这个顶一下，2 不是叶子节点。2 有两个孩子，这两个孩子是空。我们一般画图把这两个孩子省略，但可以补充画成这样：

    1
   /
  2
 / \
空  空

这两个空是这个定义下的叶子节点。

继续加油！：）

Lymun

明白了，谢谢老师的解答～

2021-03-30

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1