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

Question

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

Answer 1

liuyubobobo 2021-03-29 23:27:06

nil 节点就是空节点。

  1
 /
2

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

    1
   /
  2
 / \
空  空

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

继续加油！：）

• 提问者 Lymun #1

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