爲什麼std :: map實現爲紅黑樹？

127

爲什麼std :: map實現爲red-black tree？爲什麼std :: map實現爲紅黑樹？

有幾個平衡binary search trees（BSTs）在那裏。選擇紅黑樹時的設計權衡是什麼？

來源

2011-03-13 Denis Gorodetskiy

+22

儘管我見過的所有實現都使用RB樹，但請注意，這仍然依賴於實現。 – Thomas 2011-03-13 08:38:53

@Thomas。它依賴於實現，爲什麼所有實現都使用RB樹？ – 2011-03-13 13:12:55

我真的很想知道任何STL實現者是否想過使用跳過列表。 – 2011-03-13 13:41:05

也許兩種最常見的自平衡樹算法是Red-Black trees和AVL trees。爲了在插入/更新之後平衡樹，兩種算法都使用旋轉的概念，其中樹的節點被旋轉以執行重新平衡。

在這兩種算法中，插入/刪除操作都是O（log n），在Red-Black樹重新平衡旋轉的情況下是O(1)操作，而對於AVL，這是O(log n)操作，使得紅黑色樹在再平衡階段的這個方面更有效率，並且是更常用的可能原因之一。

大多數收集庫都使用紅黑樹，其中包括Java和Microsoft .NET Framework的產品。

來源

2011-03-13 08:47:40

+34

你讓它聽起來像紅黑樹可以在O（1）時間做樹修改，這是不正確的。對於紅黑樹和AVL樹，樹的修改都是O（log n）。由於主操作已經是O（log n），所以樹修改的平衡部分是O（1）還是O（log n），這使得它沒有實際意義。即使在AVL樹做的所有稍微額外的工作都會導致更緊密平衡的樹中導致略快的查找之後。所以這是一個完全有效的權衡，並且不會使AVL樹劣於紅黑樹。 – necromancer 2011-03-13 08:57:43

@agks mehx，我指的是算法的旋轉部分。我會更新，以便更清楚。 – 2011-03-13 08:59:41

因此，請參閱下面的答案。 – necromancer 2011-03-13 08:59:46

這只是您實現的選擇 - 它們可以作爲任何平衡樹來實現。各種選擇都可以與微小的差異相媲美。所以任何一個都可以。

來源

2011-03-13 08:48:05 necromancer

AVL樹的最大高度爲1.44logn，而RB樹的最大值爲2logn。在AVL中插入元素可能意味着樹中某一點的重新平衡。再平衡完成插入。在插入新的葉子之後，更新該葉子的祖先必須完成到根，或者直到兩個子樹具有相同深度的點。不得不更新k個節點的概率是1/3^k。再平衡是O（1）。去除一個元素可能意味着多次重新平衡（高達樹的一半深度）。

RB樹是以二叉搜索樹表示的4階B樹。 B樹中的4節點在等效的BST中產生兩個級別。在最壞的情況下，樹的所有節點都是2個節點，只有一個3節點的鏈到葉。該葉子將在根部2logn的距離處。

從根節點到插入點，必須將4節點更改爲2節點，以確保任何插入都不會使樹葉飽和。從插入回來後，必須分析所有這些節點，以確保它們正確表示4節點。這也可以在樹中進行。全球成本將是相同的。天下沒有免費的午餐！從樹中刪除元素的順序相同。

所有這些樹都要求節點承載有關高度，重量，顏色等的信息。只有Splay樹沒有這些附加信息。但是大多數人都害怕Splay樹，因爲它們的結構非常夯實！

最後，樹還可以在節點中攜帶權重信息，從而實現重量平衡。可以應用各種方案。當一個子樹包含3倍於另一個子樹的元素數量時，應該重新平衡。再平衡通過單輪或雙輪旋轉再次完成。這意味着2.4logn的最壞情況。人們可以用2次而不是3來獲得，這個比例要好得多，但這可能意味着留下少於1％的子樹在這裏和那裏不平衡。整蠱！

哪種樹是最好的？ AVL肯定。他們是最簡單的代碼，並且他們最靠近logn的最差高度。對於一個1000000個元素的樹，AVL最多隻有高度29，RB40和平衡權重36或50，具體取決於比例。

有很多其他變量：隨機性，增加的比例，刪除，搜索等

來源

2011-07-16 01:52:59 user847376

很好的答案。但是，如果AVL是最好的，爲什麼標準庫實現std :: map作爲RB樹？ – 2011-10-07 00:24:30

+11

我不同意AVL樹無疑是最好的。儘管他們的身高較低，但他們需要（總共）更多的工作來完成重新配合，而不是紅黑樹（O（log n）重新平衡工作與O（1）分期重新平衡工作）。張大樹可能會好得多，你的主張是人們害怕他們是沒有根據的。在那裏沒有一個通用的「最佳」樹木平衡方案。 – templatetypedef 2013-01-04 17:15:57

幾乎完美的答案。你爲什麼說AVL是最好的。這是完全錯誤的，這就是爲什麼大多數通用實現使用紅黑樹。你需要有一個相當高的讀操作比選擇AVL。此外，AVL的內存佔用量比RB少一些。 – 2017-05-30 20:28:03

這真的取決於使用情況。 AVL樹通常具有更多的重新平衡循環。因此，如果您的應用程序沒有太多的插入和刪除操作，但在搜索中佔據重要地位，那麼AVL樹可能是一個不錯的選擇。

std::map使用紅黑樹，因爲它在節點插入/刪除和搜索速度之間得到合理的折衷。

來源

2012-05-26 18:32:09 webbertiger

你確定嗎？我個人認爲紅黑樹不是簡單就是更復雜。唯一的情況是，在Rd-Black樹中，重新平衡發生的次數少於AVL。 – 2017-05-30 20:23:08

@Eric理論上，R/B樹和AVL樹的複雜度爲O（log n））用於插入和刪除。但是運營成本的一大部分是輪換，這在兩棵樹之間是不同的。請參閱http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948 Quote：「平衡一棵AVL樹可能需要O（log n）旋轉，而一棵紅黑樹最多需要兩棵旋轉使其達到平衡（雖然它可能必須檢查O（log n）個節點來決定旋轉的必要位置）。「據此編輯我的意見。 – webbertiger 2017-06-13 22:26:12

更新2017-06-14：webbertiger在我評論後編輯其答案。我應該指出，現在我的眼中的答案現在好多了。但我保持我的答案只是作爲額外的信息...

由於我認爲第一個答案是錯誤的（糾正：不是兩個），第三個錯誤的肯定。我覺得我必須澄清的東西...

2最受歡迎的樹AVL和紅黑（RB）。主要區別在於利用率：

AVL：如果諮詢比率（讀取）大於操縱（修改），則更好。內存腳印略小於RB（由於需要着色）。
RB：在諮詢（閱讀）和操作（修改）或對諮詢進行更多修改之間存在平衡的一般情況下更好。由於存儲紅黑旗，存儲空間稍大。

主要區別來自着色。 RB樹中的重新平衡操作比AVL少，因爲着色使您有時可以跳過或縮短具有相對高成本的重新平衡操作。由於着色，RB樹也具有更高的節點層次，因爲它可以接受黑色節點之間的紅色節點（可能有2倍左右的水平），使得搜索（讀取）效率稍低一點......但是因爲它是一個常數（2x），它保持在O（log n）。

如果考慮到修改樹（有意義）VS樹的諮詢性能（幾乎無關緊要），性能會受到影響，在一般情況下，優先考慮RB比AVL更自然。

來源

2017-05-30 20:33:26

以前的答案只能解決樹替代和紅黑可能只是由於歷史原因。

爲什麼不是一個哈希表？

在樹型結構中，類型只需要部分排序（<比較），以便在地圖中用作鍵。相比之下，散列表要求該類型具有定義的散列函數。由於STL的主要重點是通用編程，因此將這些類型的要求降到最低非常重要。

設計一個好的散列表需要深入瞭解將要使用的上下文它應該使用開放尋址還是鏈接鏈？在調整大小之前應該接受什麼樣的負載水平？它是否應該使用昂貴的散列，但避免碰撞，或者粗糙和快速？

（C++ 11的確添加了散列表unordered_map。您可以從documentation中看到它需要設置策略來配置其中的許多選項。）

由於STL無法預測哪個是您的應用程序的最佳選擇，因此默認設置需要更加靈活。樹結構「正常工作」並很好地縮放。

其他樹呢？

紅黑樹提供快速查找和自我平衡不像BSTs。另一位用戶指出了其優於自平衡AVL樹的優勢。

Alexander Stepanov（STL的創建者）說，如果他再次寫std::map，他應該使用B *樹而不是紅黑樹。這是因爲節點可以連續存儲任意數量的元素，這對現代計算機來說更容易緩存。

自那時以來最大的變化之一是高速緩存的增長。緩存缺失非常昂貴，所以現在參考的地方更重要。基於節點的數據結構，具有較低的參考地址，因此意義不大。如果我今天正在設計STL，我會在中有一組不同的容器。例如，對於實現關聯容器的，內存中的樹* *樹是比紅黑樹更好的選擇。 - 亞歷山大·斯捷潘諾夫

你可以閱讀更多here

是紅黑樹或B *永遠是最好的？

在其他場合，Alex表示std::vector幾乎總是出於類似原因的最佳列表容器。即使對於我們在學校教授的情況（例如從列表中移除元素），使用std::list或std::deque也很少有意義。 std::vector是如此之快，它擊敗那些結構的一切，但大n。

如果使用std::vector和線性搜索可能比樹實現std::map更有效，如果只有少量元素（數百？），應用相同的推理。

來源

2017-12-22 00:46:07

爲什麼std :: map實現爲紅黑樹？

回答

相關問題