樹堆（Treap）和紅黑樹（RB-Tree）各有哪些優(yōu)劣?

一、樹堆（Treap）和紅黑樹（RB-Tree）的優(yōu)劣

Treap

優(yōu)點: 插入刪除簡單直觀，速度也不錯，很好地平衡了編碼復雜度和時間效率。

缺點:由于優(yōu)先級(優(yōu)先級是個堆)是隨機生成的，所以只能保證它的插入和刪除操作時間復雜度大概是log(n)，你不能保證它的一個操作一定能在很準確的時限內完成。

所以Treap常用于算法競賽需要手動寫B(tài)ST的時候，尤其是擴展而來的Rank Tree (名次樹，查詢第k人的元素，set做不了)。

RB-Tree

優(yōu)點: 保證平衡并且有平衡限制條件，操作有準確時限，插入刪除操作比AVL Tree快.

缺點: 太復雜，插入有5種情況，刪除有6種情況，代碼量大，編寫容易出錯。

所以RB-Tree用于大部分語言的set的實現(xiàn)，實時系統(tǒng)等。

延伸閱讀：

二、樹堆實現(xiàn)平衡樹的特點

普通的BST具有很強的不確定性，如果數(shù)據特殊，建樹的時候可能直接變成一條鏈。不僅如此，插入刪除的時候也很麻煩。因為如果插入或者刪除，整個樹原來的結構就會被打亂，這會為遍歷和查找?guī)頌碾y性的后果。

所以我們推出了平衡樹。就是通過將樹旋轉來動態(tài)維護這個樹形態(tài)是平衡的，這樣查找的復雜度就是O(log)級別的，是一種穩(wěn)定的復雜度。

樹堆是一種平衡樹，它通過為鍵值（也就是我們需要維護成BST的）賦予優(yōu)先級，使之也滿足堆結構來進行旋轉，成為一棵平衡樹。

但是我們需要注意一點：樹堆的優(yōu)先級是隨機賦予的。也就是說，這個數(shù)據結構其實是一個隨機化的數(shù)據結構。這不是樹堆的缺點，因為只有隨機化賦予優(yōu)先級，才有可能保證樹堆的復雜度是O(log)的級別。那么，上述性質也說明了，樹堆并不是一個規(guī)則形態(tài)的二叉樹，更不是堆需要滿足的完全二叉樹。甚至它也不符合平衡樹的定義：每個節(jié)點左右子樹高度相差≤1，所以我們說樹堆是近似實現(xiàn)平衡。但是通過形態(tài)定義二叉樹的方式并不絕對。我們換一種方式來對平衡樹進行定義：能夠保證時間復雜度的BST，就是平衡樹。