1

我正在研究CLRS的红黑树。关于讨论红黑树属性的部分,我有两个问题。来自CLRS的段落如下:

红黑树是满足以下红黑性质的二叉树:

  1. 每个节点不是红色就是黑色

  2. 根是黑色的

  3. 每片叶子(NIL)都是黑色的

  4. 如果一个节点是红色的,那么它的两个子节点都是黑色的

  5. 对于每个节点,从节点到后代叶子的所有简单路径都包含相同数量的黑色节点

首先,它说红黑树是二叉树。为什么他们不说红黑树是二叉搜索树。我认为红黑树的全部目的是保持搜索树的平衡以确保logN操作。其次,为什么红黑树中的叶子是NIL

在常规二叉树中,我们习惯于这样:

               4
         5            7
    3        2     Nil Nil
 Nil Nil  Nil Nil

在这种情况下,3、2 和 7 是叶子。为什么在 CLRS 中叶子被描绘成 Nil 的?

4

1 回答 1

1

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

同样在本章中,它们表明标记为nil的节点是实际节点(称为哨兵),具有与普通节点相同的字段,但具有color固定值“黑色”的字段(其他字段可以设置为任意值);这些节点在树中总是显示为叶子。所以它不同于通常的 BST,其中叶子是一个节点,其左子树和右子树都是nil.

于 2015-11-08T00:38:10.810 回答