什麼被認爲是紅黑樹上的一片葉子？

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的節點。