一、樹堆(Treap)和紅黑樹(RB-Tree)的優(yōu)劣
Treap
優(yōu)點(diǎn): 插入刪除簡單直觀,速度也不錯,很好地平衡了編碼復(fù)雜度和時間效率。
缺點(diǎn):由于優(yōu)先級(優(yōu)先級是個堆)是隨機(jī)生成的,所以只能保證它的插入和刪除操作時間復(fù)雜度大概是log(n),你不能保證它的一個操作一定能在很準(zhǔn)確的時限內(nèi)完成。
所以Treap常用于算法競賽需要手動寫B(tài)ST的時候,尤其是擴(kuò)展而來的Rank Tree (名次樹,查詢第k人的元素,set做不了)。
RB-Tree
優(yōu)點(diǎn): 保證平衡并且有平衡限制條件,操作有準(zhǔn)確時限,插入刪除操作比AVL Tree快.
缺點(diǎn): 太復(fù)雜,插入有5種情況,刪除有6種情況,代碼量大,編寫容易出錯。
所以RB-Tree用于大部分語言的set的實現(xiàn),實時系統(tǒng)等。
延伸閱讀:
二、樹堆實現(xiàn)平衡樹的特點(diǎn)
普通的BST具有很強(qiáng)的不確定性,如果數(shù)據(jù)特殊,建樹的時候可能直接變成一條鏈。不僅如此,插入刪除的時候也很麻煩。因為如果插入或者刪除,整個樹原來的結(jié)構(gòu)就會被打亂,這會為遍歷和查找?guī)頌?zāi)難性的后果。
所以我們推出了平衡樹。就是通過將樹旋轉(zhuǎn)來動態(tài)維護(hù)這個樹形態(tài)是平衡的,這樣查找的復(fù)雜度就是O(log)級別的,是一種穩(wěn)定的復(fù)雜度。
樹堆是一種平衡樹,它通過為鍵值(也就是我們需要維護(hù)成BST的)賦予優(yōu)先級,使之也滿足堆結(jié)構(gòu)來進(jìn)行旋轉(zhuǎn),成為一棵平衡樹。
但是我們需要注意一點(diǎn):樹堆的優(yōu)先級是隨機(jī)賦予的。也就是說,這個數(shù)據(jù)結(jié)構(gòu)其實是一個隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)。這不是樹堆的缺點(diǎn),因為只有隨機(jī)化賦予優(yōu)先級,才有可能保證樹堆的復(fù)雜度是O(log)的級別。那么,上述性質(zhì)也說明了,樹堆并不是一個規(guī)則形態(tài)的二叉樹,更不是堆需要滿足的完全二叉樹。甚至它也不符合平衡樹的定義:每個節(jié)點(diǎn)左右子樹高度相差≤1,所以我們說樹堆是近似實現(xiàn)平衡。但是通過形態(tài)定義二叉樹的方式并不絕對。我們換一種方式來對平衡樹進(jìn)行定義:能夠保證時間復(fù)雜度的BST,就是平衡樹。