什么被认为是红黑树中的叶子？

Question

我正在研究来自CLRS的红黑树。关于讨论 red-black 树的属性的部分，我有 2 个问题。来自CLRS的文章如下：

一棵red-black树是满足以下red-black属性的二叉树：

每个节点不是红色就是黑色
根是黑的
每一片叶子（NIL）都是黑色的
如果一个节点是红色的，那么它的两个children都是黑色的
对于每个节点，从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点

首先，它说一棵red-black树是一棵二叉树。他们为什么不说 red-black 树是 二叉搜索树 。我认为 red-black 树的全部目的是保持搜索树的平衡以确保 logN 操作。其次，为什么 red-black 树中的叶子是 NIL？

在常规二叉树中，我们已经习惯了：

               4
         5            7
    3        2     Nil Nil
 Nil Nil  Nil Nil

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

Answer 1

在书中，他们将红黑树称为二叉搜索树，就在本章的开头。

同样在本章中，它们表示标记为 nil 的节点是实际节点（称为 sentinels），具有与普通节点相同的字段但具有color字段固定值"black"（其他字段可以设置任意值）；这些节点在树中始终显示为叶子。所以它不同于通常的BST，其中一个叶子是一个节点，其左子树和右子树都是nil。

什么被认为是红黑树中的叶子？

What is considered a leaf in red black trees?

algorithm

red-black-tree

clrs

binary-search-tree