爲什麼RB-Tree不能成爲一個列表？

Question

我有一個rb-trees的問題。根據維基百科，rb-tree需要遵循以下內容：

1. 節點是紅色或黑色。
2. 根部是黑色的。 （這條規則在一些定義，而不是別人使用。因爲根總是可以從紅色變成黑色，但並不一定反之亦然這個規則對分析影響不大。）
3. 所有的葉子都是黑色的。
4. 每個紅色節點的兩個孩子都是黑色的。
5. 從給定節點到任何其後代的葉子每一個簡單路徑都包含相同數目的黑色節點。

正如我們所知，rb-tree需要平衡並且具有O（log（n））的高度。 但是，如果我們插入一個越來越一系列數字（1,2,3,4,5 ...），並在理論上，我們將得到一個樹看起來像一個名單，將有O（n）的高度與所有它的節點是黑色的，這與上面提到的rb-tree屬性不矛盾。那麼，我錯在哪裏？

謝謝。

Answer 1

你的例子與屬性號碼5矛盾，所以它不是一個有效的紅黑樹。

我們的樹是：

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil))))) 

所以獲得了最後兩個葉（節點5的孩子），我們要參觀五個黑節點（每個b表示），去下節點4葉我們必須訪問四個黑節點等這意味着，有簡單路徑從根到一些含不同數量的黑色節點，其中無效屬性5.

Answer 2

甲在the article位進一步向下：

插入通過添加 多達二叉搜索樹插入 確實和由着色它紅的節點開始。