紅黑樹必須按排序順序嗎？

Question

我在這裏有一個非常簡單的問題：紅黑樹必須按排序順序嗎？我問這是因爲維基百科頁面右側的小方塊（http://en.wikipedia.org/wiki/Red-black_tree）表示搜索時間是O（log（n））;然而，如果樹被排序，這隻會是真的。另一方面，雖然屬性s

Answer 1

紅黑樹是排序樹（整個所有RB樹都是排序的二叉樹，但並非所有排序後的二叉樹都是紅黑樹的東西）。普通二叉樹和紅黑樹之間的區別在於RB樹保證搜索時間將是日誌（n），因爲它們是平衡的。實質上，它保證節點的層數永遠不會超過log （n），保持二進制搜索。

沒有平衡的純二叉樹不會總是產生時間複雜度。舉例來說，如果我有這樣的樹：

4 
/\ 
3 6 
    \ 
     7 
     \ 
     10 
     \ 
     12 

對於這種不平衡的樹，實際的搜索時間幾乎是線性的找到12（最壞情況下的時間複雜度，5個比較）。對於具有一個平衡樹至多日誌（n）的層，上面的樹可以是：

 7 
/ \ 
    4 10 
/\  \ 
3 6 12 

所以找到任何最低層節點將至多3個比較（其適合日誌（n）的因爲它實際上是向上舍入，小區[日誌（6）] = 3）

這裏的關鍵是要記住，層的數量在功能上等價到你在根目錄開始時必須進行的比較次數。紅黑樹通過平衡將層數限制爲最小值，而香草，不平衡二叉樹不會。

Answer 2

紅黑樹的搜索時間爲O（log n），因爲它以自然順序設置它們的節點。

當你做一個節點比較時，理論上你在分支上放棄了一半的選項。

既然你只能「半」 log n times你到一個元素之前，那麼您的搜索複雜度是O(log n)

Answer 3

紅黑樹是二叉搜索樹。根據二叉搜索樹的定義，左側子元素（以及所有後代）必須小於父代，右側子代（以及所有後代）必須大於父代。因此有一個命令。

Answer 4

紅黑樹的全部要點是保持樹在某種程度上的平衡。如果你放鬆排序約束，那麼保持樹平衡是微不足道的，因爲你可以把節點放在任何你想要的地方。