我正在研究来自 CLRS 的红黑树。 关于讨论红黑树属性的部分,我有 2 个问题。 来自CLRS的文章如下:
红黑树是满足以下红黑属性的二叉树:
每个节点不是红色就是黑色
根是黑色的
每片叶子(NIL)都是黑色
如果一个节点是红色的,那么它的两个 child 都是黑色的
对于每个节点,从该节点到后代叶子的所有简单路径都包含相同数量的黑色节点
首先,它说红黑树是二叉树。他们为什么不说红黑树是二叉搜索树。我认为红黑树的全部目的是保持搜索树的平衡以确保logN 操作。其次,为什么红黑树的叶子是NIL?
在常规二叉树中,我们习惯于:
4
5 7
3 2 Nil Nil
Nil Nil Nil Nil
在这种情况下,3、2 和 7 是叶子。为什么叶子在 CLRS 中被描述为 Nil 的?
最佳答案
在书中,他们将红黑树称为二叉搜索树,就在本章的开头。
同样在本章中,它们表明标记为 nil
的节点是实际节点(称为 sentinels),具有与普通节点相同的字段但具有 color
固定值为“black”的字段(其他字段可以设置为任意值);这些节点在树中始终显示为叶子。所以它不同于通常的 BST,其中 叶子 是一个节点,其左子树和右子树都是 nil
。
关于algorithm - 什么被认为是红黑树中的叶子?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33589460/