為什麼工程中都用紅黑樹，而不是其他平衡二叉樹？

01-06

linux內存管理，c++stl用的都是紅黑樹，演算法導論給出偽代碼的也是紅黑樹，請問為什麼不是其他的平衡樹

紅黑樹還有一個很重要的特性是每次更新操作的旋轉次數為O(1)，使其特別適合用來實現持久化的搜索樹。

http://benpfaff.org/papers/libavl.pdf Performance Analysis of BSTs in System Software

Comparison of Binary Search Trees (BSTs)

還有一個原因：《演算法導論》上給出了 red-black tree 的完整實現，照抄就行了，不用擔心正確性。

《演算法導論》作者之一Thomas Cormen在Quora上徵詢第四版內容意見（當然目前僅僅是徵詢意見），RB-tree赫然在Remove清單上：http://www.quora.com/As-we-start-planning-the-next-edition-of-Introduction-to-Algorithms-CLRS-what-should-we-add-and-what-should-we-remove

取而代之的是誰呢？skiplist當仁不讓。

首先Mark Allan Weiss的《數據結構與演算法分析C++描述》（我個人非常推薦的演算法書）「確定性跳躍表」*(determistic skiplist)一節說「性能似乎比RB-tree要強」，還有省內存，具體見書。

其次skiplist結構在有兩個RB-tree無法實現的殺手鐧：其一是可以像數組水平順序遍歷key，這也是B+tree對B-tree的優點；其二對key排名(ranking)，見redis實現。

還有代碼，我個人在github上的參考redis的實現，我代碼簡潔，但多用了一個指針（雙鏈表），寫了以後簡直不想寫RB-tree了，尤其是刪除（你看過STL源碼吧）：leo-ma/skiplist · GitHub

同樣作為內存字典結構，skiplist有什麼應用限制嗎？微博上曾有人指出「不是任何場景都能接受 skiplist 的隨機性 」。

問題中的結論有局限性，至少分散式存儲中更傾向於用skiplist取代平衡樹。

除了 @我的上鋪叫路遙提到的優點之外，還有個重要原因：

lock-free skiplist性能更佳且工程實現更容易。

參考：algorithm - Skip List vs. Binary Tree

雖然邵成說的是紅黑樹優秀的一個方面，但是我覺得當年選紅黑樹完全是因為效率...紅黑樹似乎是或者說至少是我已知的表現最好的平衡二叉樹...