AVL樹、splay樹(伸展樹)和紅黑樹比較

一、AVL樹：

優(yōu)點：查找、插入和刪除，最壞復雜度均為O(logN)。實現(xiàn)操作簡單

? ? 如過是隨機插入或者刪除，其理論上可以得到O(logN)的復雜度，但是實際情況大多不是隨機的。如果是隨機的，則AVL? ??樹能夠達到比RB樹更優(yōu)的結果，因為AVL樹的高度更低。如果只進行插入和查找，則AVL樹是優(yōu)于RB樹的，因為RB樹? ??更多的優(yōu)勢還是在刪除動作上。

缺點：1)借助高度或平衡因子，為此需要改造元素結構，或額外封裝-->伸展樹可以避免。

? ? 2)實測復雜度與理論復雜度上有差距。插入、刪除后的旋轉成本不菲。刪除操作后，最多旋轉O(logN)次，(Knuth證明，平?均最壞情況下概率為0.21次)，若頻繁進行插入/刪除操作，得不償失。

? ?3)單詞動態(tài)調整后，全樹拓撲結構的變化量可達O(logN)次。-->紅黑樹為O(1)

二、伸展樹(splay tree)、

優(yōu)點、1)無需記錄節(jié)點高度和平衡因子，編程實現(xiàn)簡單易行

? ? 2)分攤復雜度為O(logN)

? ? 3)局部性強，緩存命中率極高時，效率甚至可以更高。

?注：伸展樹是根據(jù)數(shù)據(jù)訪問的局部性而來的主要是：1)剛剛被訪問的節(jié)點，極有可能在不就之后再次被訪問到；2)將被訪問?的下一個節(jié)點，極有可能就處于不就之前被訪問過的某個節(jié)點的附近。

缺點：1)仍不能保證單詞最壞情況的出現(xiàn)，不適用效率敏感的場合

? ? 2)復雜度分析比較復雜

三、紅黑樹

優(yōu)點：1)所有的插入、刪除、查找操作的復雜度都是O(logN)

? ? 2)插入操作能夠在最多2次旋轉后達到平衡狀態(tài)，而刪除操作更是能夠在一次旋轉后達到平衡狀態(tài)。刪除操作有可能導致遞歸的雙黑修正，但是在旋轉之前，只是染色而樹的結構沒有任何實質性的改變，因此速度優(yōu)于AVL樹。

3)紅黑樹可以保證在每次插入或刪除操作之后的重平衡過程中，全書拓撲結構的更新僅涉及常數(shù)個節(jié)點。盡管最壞情況下需對O(logN)個節(jié)點重染色，但就分攤意義而言，僅為O(1)個。

缺點：左右子樹高度相差比AVL樹大。

?

---

總結

二叉查找樹：

任意一個節(jié)點所包含的鍵值，大于等于左孩子的鍵值，小于等于右孩子的鍵值。?
此外，無論是左旋還是右旋，若旋轉之前這棵樹是二叉查找樹，旋轉之后它一定還是二叉查找樹。

平衡樹（AVL樹）：

AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1，LL,RR,LR,RL旋轉算法。?
對于1百萬個節(jié)點的平衡樹，樹的高度為12-20之間，對于10億個節(jié)點的平衡樹，樹的高度為18-30之間。

伸展樹：

當某個節(jié)點被訪問時，伸展樹會通過旋轉使該節(jié)點成為樹根。

紅黑樹：

主要是用它來存儲有序的數(shù)據(jù)，它的時間復雜度是O(lgn))，效率非常之高.

AVL樹與紅黑樹比較：

AVL是嚴格平衡樹，因此在增加或者刪除節(jié)點的時候，根據(jù)不同情況，旋轉的次數(shù)比紅黑樹要多。（所以AVL樹插入和刪除時間會稍微多）?
紅黑樹是弱平衡的，用非嚴格的平衡來換取增刪節(jié)點時候旋轉次數(shù)的降低。?
兩者都屬于自平衡二叉樹，那么降低樹的深度自然會提高查找效率。?
兩者查找，插入，刪除的時間復雜度相同O(lgn)

時間復雜度比較

sequential search - 順序查找?
binary search - 二分查找?
BST - 二叉查找樹?
2-3 tree - 平衡樹?
red-black tree - 紅黑樹

?

轉載于:https://www.cnblogs.com/Renyi-Fan/p/8253548.html

總結

以上是生活随笔為你收集整理的AVL树、splay树(伸展树)和红黑树比较的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。