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

Treap

優(yōu)點(diǎn): 插入刪除簡(jiǎn)單直觀，速度也不錯(cuò)，很好地平衡了編碼復(fù)雜度和時(shí)間效率。

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

所以Treap常用于算法競(jìng)賽需要手動(dòng)寫(xiě)B(tài)ST的時(shí)候，尤其是擴(kuò)展而來(lái)的Rank Tree (名次樹(shù)，查詢(xún)第k人的元素，set做不了)。

RB-Tree

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

缺點(diǎn): 太復(fù)雜，插入有5種情況，刪除有6種情況，代碼量大，編寫(xiě)容易出錯(cuò)。

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

延伸閱讀：

二、樹(shù)堆實(shí)現(xiàn)平衡樹(shù)的特點(diǎn)

普通的BST具有很強(qiáng)的不確定性，如果數(shù)據(jù)特殊，建樹(shù)的時(shí)候可能直接變成一條鏈。不僅如此，插入刪除的時(shí)候也很麻煩。因?yàn)槿绻迦牖蛘邉h除，整個(gè)樹(shù)原來(lái)的結(jié)構(gòu)就會(huì)被打亂，這會(huì)為遍歷和查找?guī)?lái)災(zāi)難性的后果。

所以我們推出了平衡樹(shù)。就是通過(guò)將樹(shù)旋轉(zhuǎn)來(lái)動(dòng)態(tài)維護(hù)這個(gè)樹(shù)形態(tài)是平衡的，這樣查找的復(fù)雜度就是O(log)級(jí)別的，是一種穩(wěn)定的復(fù)雜度。

樹(shù)堆是一種平衡樹(shù)，它通過(guò)為鍵值（也就是我們需要維護(hù)成BST的）賦予優(yōu)先級(jí)，使之也滿(mǎn)足堆結(jié)構(gòu)來(lái)進(jìn)行旋轉(zhuǎn)，成為一棵平衡樹(shù)。

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