當紅黑樹是有用的

Question

可能重複：
Red-Black Trees

我對紅黑樹開始看一個lecture在麻省理工學院和15分鐘後放棄了。

當然，我沒有看過以前的10個講座，但爲什麼在進入理論之前沒有現實世界的例子？

有人可以舉一個例子，解釋爲什麼紅黑樹是一個重要的數據結構？

Answer 1

紅黑樹是自我平衡的，所以可以在O（log n）時間插入，刪除和搜索。其他類型的平衡樹（例如AVL樹）對於插入和刪除操作通常較慢。

此外，紅黑樹的代碼往往更簡單。

它們很適合創建Maps或關聯數組以及專用數據存儲。我在高速電信應用中使用了一種實現最低成本的路由系統。

Answer 2

注：我沒有看到講座。

紅黑樹是二元搜索樹，它們是自動平衡當一個項目被添加或刪除。此功能保證了此樹中的每個搜索都具有O(logn)複雜性。

如果構建一棵沒有平衡它的樹，就有可能創建一個退化的樹，它實際上是一個具有O(n)複雜性的鏈表。

Answer 3

Wikipedia說「自平衡二叉搜索樹」。

「簡而言之，紅黑樹是一種二叉搜索樹，插入和刪除的方式使樹總是合理平衡的。」

當數據發生排序時，這有幫助。如果沒有平衡，樹就會轉移到鏈表上。

Answer 4

Wikipedia提供了一個解釋和一個重要的例子。

紅黑樹爲插入時間，刪除時間和搜索時間提供了最壞情況保證。這對實時應用程序非常有用。

現實世界的例子是Linux內核中的完全公平調度器。