紅黑樹的應用

紅黑樹的應用有哪些？有什麼應用程序只有RB樹可以使用，沒有其他數據結構？紅黑樹的應用

2010-10-10 nishant

你總是可以完成一些關於任何數據結構的工作，但在某些情況下它會變成'O（嚇人）'。問題應該是：哪些算法最適合RB樹？（我相信維基百科有一些答案）。 – delnan 2010-10-10 16:45:35

除非您有非常具體的性能要求，否則R-B樹可以被其他一些自平衡二叉樹替代，例如AVL樹。兩者之間的選擇基本上是性能優化 - 它們提供相同的基本操作。

不是他們中的任何一個比另一個明確地「更快」，只是他們不同而已，他們的具體用途往往會有略微不同的表現，其他的都是平等的。因此，如果您足夠仔細地繪製您的要求，或者只是偶然，您可能會以其中一個「足夠快」爲您使用，而另一個則不是。 R-B提供的插入速度比AVL略快，但代價是稍慢一點的查找。

來源

2010-10-10 16:45:24

A red-black tree是self-balancing binary search tree的特定實現，而今天它似乎是最流行的實現選擇。

Binary search trees用於實現有限地圖，其中存儲一組關鍵值和關聯值。您也可以通過僅使用鍵而不存儲任何值來實現集。

爲了保證良好的性能，需要對樹進行平衡，否則樹可能退化爲一個列表，例如，如果插入已經排序的鍵。

搜索樹優於散列表的優點是可以按排序順序有效地遍歷樹。

AVL-trees是平衡二叉搜索樹的另一種變體。他們在知道紅黑樹之前很受歡迎。它們更仔細地平衡，左右子樹的高度之間的最大差異（RB樹最多保證兩倍）。他們的主要缺點是再平衡需要更多努力。

所以紅黑樹肯定是一個很好的但不是這個應用程序的唯一選擇。

來源

2010-10-10 17:20:35 starblue

我認爲AVL樹更好，因爲它們是可以理解的。我還沒有遇到一位瞭解RB樹如何工作的開發人員 - 因此，我的意思是比誦讀平衡規則列表更多的理解。 – 2010-10-12 18:32:20

基本不變並不那麼複雜：在紅黑樹中，每一條葉子的路徑具有相同數量的黑色節點，並且路徑上沒有相鄰的紅色節點。這意味着路徑的長度相差至多兩倍。至於所需的輪轉，這是對兩種樹木的個案分析。 – starblue 2010-10-13 09:55:40

沒有像紅黑這樣的規則只能在特定情況下使用它取決於應用程序的情況下，如何時你必須建立樹只有一次，你必須多次查詢，然後你可以去對於AVL樹來說，因爲在AVL樹中搜索的速度相當快。但它是嚴格平衡的，所以插入和刪除操作可能需要一些時間。 AVl樹可能用於語言文本，其中您必須構建數據結構只需一次和紅色黑樹被用在現在的Linux內核中使用的完全公平調度器中。

在紅黑樹上應用的約束也強制指出，從根到最遠的葉不超過從根到最近的葉的路徑的兩倍。

順便說一句，你可以查找各種SEACH並插入一個紅黑樹需要到這裏

 Average  Worst case 

Space O(n)  O(n) 

Search O(log n) O(log n) 

Insert O(log n) O(log n) 

Delete O(log n) O(log n)

來源

2012-12-19 06:05:48

紅黑樹等的時間是從一類自我平衡BSTS和他人的回答，任何這樣的可以使用自平衡樹。我想補充一點，紅黑樹被廣泛用作系統符號表。例如，它們用於執行以下操作：

Java：java.util.TreeMap，java.util.TreeSet。
C++ STL：map，multimap，multiset。
Linux內核：完全公平調度，LINUX/rbtree.h

來源

2014-03-21 12:27:28

Linux中的進程調度使用紅黑樹。紅色的黑色樹是運行隊列的替代品，隊列中的進程具有優先級，以供調度程序從中選擇。

完全公平調度程序（C.F.S）是一個進程調度程序的名稱，它被合併到2.6.23版本的Linux內核中。它處理執行進程的CPU資源分配，旨在最大限度地提高整體CPU利用率，同時最大限度地提高交互性能。

來源

2016-09-10 06:10:03

紅黑樹的應用

回答

相關問題