我知道如何用n個插入(每個都有O(log(n))效率) (n * log(n))整體 ,我也知道2-3-4樹的等價結構也可以用排序後的數組構造線性時間。 任何人都可以提供關於紅黑版本的簡單解釋嗎?從線性時間的排序陣列構建紅黑樹
1
A
回答
5
無論你打算建造什麼樣的BST。算法將是相同的。只需要構建均衡的二叉樹。
- 放置中間元件於當前位置
- 地點[開始;中間)元素到左子樹。
- 將(中間;末尾)元素放置到右側子樹。
這是O(N)算法。可以證明,結果樹會被平衡。
我們有平衡樹,這樣的定義:
長(最長路徑) - 長(最短路徑)< = 1
所以,你需要標記所有節點爲黑色,除了最深的節點樹(標記爲紅色)。
2
一個高度完整的二叉樹H有2^H-1節點。
爲了使紅黑樹從排序列表:
- 從列表中刪除所有的第二個項目,直到你有2^H-1項目剩餘部分^h。請注意,你將永遠有足夠的。
- 從剩餘的項目中構建一棵完整的樹,全部爲黑色。
- 現在將所有移除的項目都附加到樹中。每個項目將是一個紅色節點,連接到其正確位置周圍的黑色節點是葉子。
執行步驟(3)的最簡單方法就是對樹進行預先遍歷,將新的紅色節點附加到每個黑色葉子,直到項目用完。
注意:薩沙的算法也可以,但是這個明顯是的作品。
0
從功能數據結構的角度來看:有一篇文章爲Constructing Red-Black Trees,它發現了連續插入的模式並將其與1-2數字系統相關聯。
這是一個有趣的閱讀。
相關問題
- 1. 紅黑樹 - 建設
- 2. 紅黑樹的複雜性
- 3. 線性時間排序?
- 4. PHP從4個陣列構建樹型結構陣列
- 5. 紅色的黑色樹與編排
- 6. VBScript來從線陣列創建樹
- 7. 紅黑樹,
- 8. 排序數組2-4 +樹的線性時間
- 9. 紅黑樹:在log(n)時間中拆分/連接時間
- 10. 紅黑樹必須按排序順序嗎?
- 11. 紅黑樹與B樹
- 12. 在另一個紅黑樹的節點中使用紅黑樹
- 13. 陣列樹的線性表示
- 14. 堆或紅黑樹?
- 15. AVL和紅黑樹
- 16. 紅黑樹實現
- 17. 紅黑樹平衡?
- 18. 紅黑樹 - 刪除
- 19. 插入紅黑樹
- 20. 連接紅黑樹
- 21. 紅黑樹證明
- 22. 紅黑樹問題
- 23. 時間排序陣列中的PHP
- 24. 紅黑樹插入操作對排序值的行爲
- 25. 使用紅黑樹進行非線性優化
- 26. 排列2D陣列或排序1D +線性搜索。
- 27. Trie vs紅黑樹:哪個空間和時間更好?
- 28. C中的紅黑樹
- 29. 紅黑樹中的insert_rebalance
- 30. 紅黑樹上的問題
請您詳細說明我們您的努力是否顯示代碼的必要部分? – manetsus
我不想編碼它。只是爲了理解這個概念。 –
如果你知道如何構建一個2-3-4樹,只需要做一樣的事情,但是對於3節點來說是紅色的,而在通常的對應中是4節點的兩個紅色。 – rici