什么被认为是红黑树上的一片叶子？

Question

我正在研究从CLRS红黑树。 我有两个关于红黑树属性讨论部分的问题。 从CLRS通道如下：

红黑树是二叉树满足以下红黑属性：

1. 每个节点是红色或黑色

2. 根是黑色

3. 每个叶（NIL）是黑

4. 如果一个节点是红色的，那么这两个其子黑

5. 对于每个节点，从该节点的所有简单路径，以后代叶中含有相同数量的黑色节点

首先的，它说为红色黑树是二叉树。为什么他们不说红黑树是二叉查找树。我认为红黑树的全部目的是为了在搜索树中保持平衡以确保操作。第二，为什么红黑树的叶子无？

在常规的二叉树，我们已经习惯了这一点：

   4 
     5   7 
    3  2  Nil Nil 
Nil Nil Nil Nil 

在这种情况下，3个，2个和7是叶子。为什么叶片被描述为CLRS中的Nil？

Answer 1

在这本书中，他们将红黑树称为二进制搜索树，它正好在本章的开头。

另外的一章中，它们表明标记为nil节点是实际节点（称为哨兵）中，用相同的字段作为一个普通的节点，但与固定值“黑”一个color字段（其他字段可以被设置为任意值）;这些节点始终显示为树中的叶子。所以它与通常的BST不同，其中叶是其左子树和右子树都是nil的节点。