我在研究CLR的红黑树。
关于讨论红黑树性质的部分，我有两个问题。
CLRS的通道如下：
红黑树是满足以下红黑属性的二叉树：
每个节点不是红色就是黑色
根是黑色的
每片叶子（无）都是黑色的
如果一个节点是红色的，那么它的两个子节点都是黑色的
对于每个节点，从节点到子代叶子的所有简单路径都包含相同数量的黑色节点
首先，它说红黑树是二叉树为什么他们不说红黑树是二叉搜索树。我认为红黑树的全部目的是保持搜索树的平衡，以确保logn操作。第二，为什么红黑树上的叶子是零？
在普通的二叉树中，我们习惯于：
4
5 7
3 2 Nil Nil
Nil Nil Nil Nil
在本例中，3、2和7是叶子。为什么在CLRS中叶子被描绘成Nil？
最佳答案
在书中，他们把红黑树称为二叉搜索树，就在本章的开头。
在本章中，它们还指出标记为nil的节点是实际节点（称为sentinels），具有与普通节点相同的字段，但具有固定值“black”的color字段（其他字段可以设置为任意值）；这些节点始终显示为树中的叶。所以它不同于通常的bst，叶是一个节点，其左子树和右子树都nil。