從線性時間的排序陣列構建紅黑樹

Question

我知道如何用n個插入（每個都有O（log（n））效率） （n * log（n））整體 ，我也知道2-3-4樹的等價結構也可以用排序後的數組構造線性時間。 任何人都可以提供關於紅黑版本的簡單解釋嗎？

Answer 1

無論你打算建造什麼樣的BST。算法將是相同的。只需要構建均衡的二叉樹。

1. 放置中間元件於當前位置
2. 地點[開始;中間）元素到左子樹。
3. 將（中間;末尾）元素放置到右側子樹。

這是O（N）算法。可以證明，結果樹會被平衡。

我們有平衡樹，這樣的定義：

長（最長路徑） - 長（最短路徑）< = 1

所以，你需要標記所有節點爲黑色，除了最深的節點樹（標記爲紅色）。

Answer 2

一個高度完整的二叉樹H有2^H-1節點。

爲了使紅黑樹從排序列表：

1. 從列表中刪除所有的第二個項目，直到你有2^H-1項目剩餘部分^h。請注意，你將永遠有足夠的。
2. 從剩餘的項目中構建一棵完整的樹，全部爲黑色。
3. 現在將所有移除的項目都附加到樹中。每個項目將是一個紅色節點，連接到其正確位置周圍的黑色節點是葉子。

執行步驟（3）的最簡單方法就是對樹進行預先遍歷，將新的紅色節點附加到每個黑色葉子，直到項目用完。

注意：薩沙的算法也可以，但是這個明顯是的作品。

Answer 3

從功能數據結構的角度來看：有一篇文章爲Constructing Red-Black Trees，它發現了連續插入的模式並將其與1-2數字系統相關聯。

這是一個有趣的閱讀。