8:20 秒处的红黑树的叶子节点（6）为什么是红色的？

Question

1. 关于是否是叶子节点我可以理解成有且只有一个节点的才能成为叶子节点吗？
2. 像是（6-12）这种就不属于叶子节点，对吗？
3. 如果（6-12）不属于叶子节点，应该叫做什么节点呢？

Answer 1

liuyubobobo 2021-12-16 16:51:58

1）

在大多数情况下，树结构的叶子节点的定义是“没有子孩子的节点”。

但是，在红黑树中，把叶子节点定义成最后的“空节点”。即 6 这个节点还有两个 NULL 孩子。这两个孩子才是红黑树定义下的叶子节点。他们才是黑色的。所以 6 可以是红色的。

红黑树对叶子节点的这一个“特殊”定义，下一小节会介绍：

2）

在红黑树定义下，是的，6 和 12 都不是叶子节点。

3）

叫非叶子节点。

继续加油！：）

• 提问者 弦歌ty #1

  谢谢老师，明白了