前言

以前本科同學在找工作的時候，就被面試官問到過關于紅黑樹的問題。因為當時我的知識面不廣，所以也不知道紅黑樹是個什么東西，也沒放在心上。在看過了STL源碼后才知道原來有很多底層實現都用的紅黑樹。簡單的查閱了相關概念后，我覺得它和AVL沒啥差別，而且AVL更好理解，平衡性也更優，那為什么還要使用紅黑樹？

于是我開始查閱相關資料，百度紅黑樹的概念及性質，在網上看到了一些回復，感覺講的很有道理。但我沒有簡單的接受他們的答案，而是在Github上找代碼，以驗證他們所說的紅黑樹的優勢。本篇博文不向各位介紹紅黑樹原理及旋轉操作的過程，只介紹一些基本的概念，然后通過使用AVL和RB-Tree處理數據的時間驗證紅黑樹的優勢。

?

基本概念

AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。查找、插入和刪除在平均和最壞情況下都是O(logn)。

紅黑樹（Red Black Tree）是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。紅黑樹和AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的：它可以在O(logn)時間內做查找，插入和刪除。

紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹有如下的額外要求:

性質1. 節點是紅色或黑色。

性質2. 根節點是黑色。

性質3 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質4. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

從以上概念和性質可知紅黑樹不是高度平衡的二叉樹，它用非嚴格的平衡結構來換取增刪節點時旋轉次數的降低。雖然它放棄了嚴格的高度平衡，但完成查詢、插入、刪除操作的時間復雜性度依然為O(logn)。此外，由算法導論里的分析，我們可以得到這么一個結論：任何不平衡都會在三次旋轉之內解決。

?

CSDN、知乎上的回答

1. 如果插入一個node引起了樹的不平衡，AVL和RB-Tree都是最多只需要2次旋轉操作，即兩者都是O(1)；但是在刪除node引起樹的不平衡時，最壞情況下，AVL需要維護從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉的量級O(logn)，而RB-Tree最多只需3次旋轉，只需要O(1)的復雜度。

2. 其次，AVL的結構相較RB-Tree來說更為平衡，在插入和刪除node更容易引起Tree的unbalance，因此在大量數據需要插入或者刪除時，AVL需要rebalance的頻率會更高。因此，RB-Tree在需要大量插入和刪除node的場景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

3. map的實現只是折衷了兩者在search、insert以及delete下的效率。總體來說，RB-tree的統計性能是高于AVL的。

4.紅黑樹的查詢性能略微遜色于AVL樹，因為他比avl樹會稍微不平衡最多一層，也就是說紅黑樹的查詢性能只比相同內容的avl樹最多多一次比較，但是，紅黑樹在插入和刪除上完爆avl樹，avl樹每次插入刪除會進行大量的平衡度計算，而紅黑樹為了維持紅黑性質所做的紅黑變換和旋轉的開銷，相較于avl樹為了維持平衡的開銷要小得多

注意：因為每次插入和刪除都要進行查找元素的操作，所以插入和刪除的時間復雜性的都是O(logn)，其實插入和刪除操作本身的時間復雜度是O(1)。

?

實驗驗證

以上代碼是我在Github上找到的，作者的目的是實現和Linux下的紅黑樹一樣快的AVL。其中分析了AVL和紅黑樹在處理數據時的性能，也是驗證上述回答的非常好的一個實驗。實驗分為靜態內存評估和動態內存評估，而我只關注于兩者在插入、查找和刪除元素所耗費的時間上。網址在文章結尾。

靜態內存情況下運行結果：

RB-Tree和AVL在處理10000000個結點時的數據對比: insert time: 3400ms, height=32 insert time: 3618ms, height=27search time: 2790ms error=0 search time: 2912ms error=0delete time: 510ms delete time: 612mstotal: 6700ms total: 7142msRB-Tree和AVL在處理1000000個結點時的數據對比: insert time: 292ms, height=26 insert time: 315ms, height=24search time: 167ms error=0 search time: 170ms error=0delete time: 56ms delete time: 62mstotal: 515ms total: 547ms

?

動態內存情況下運行結果：

RB-Tree和AVL在處理10000000個結點時的數據對比: insert time: 3832ms, height=32 insert time: 4138ms, height=27search time: 2901ms error=0 search time: 2945ms error=0delete time: 484ms delete time: 574mstotal: 7217ms total: 7657msRB-Tree和AVL在處理1000000個結點時的數據對比: insert time: 342ms, height=26 insert time: 373ms, height=24search time: 187ms error=0 search time: 171ms error=0delete time: 44ms delete time: 53mstotal: 573ms total: 597ms

?

分析

以下是程序運行時間的柱狀圖，這里只做了靜態內存的圖表，因為無論是靜態還是動態，程序處理數據的優劣情況是一樣的。

從上面的兩張圖片可以看出，隨著數據量的增加，RB-Tree的優勢更為明顯。當這兩個樹型結構在處理百萬元素的時候，在刪除方面，RB-Tree比AVL快6ms，但兩者的刪除操作總共花費時間為60ms左右。相比插入和搜索時間占比而言，在刪除操作方面，RB-Tree的表現更好。當數據量增加了一個量級后，RB-Tree的刪除操作比AVL快將近100ms(節約的時間占比變高)。所以當處理大量數據，且刪除操作較為頻繁的情況下，RB-Tree的性能要優于AVL。綜上所述，如果你的應用中，查詢的次數遠遠大于插入和刪除，那么應該選擇AVL。如果搜索，插入刪除次數幾乎差不多，則應該選擇RB-Tree。

?

結論

結合實驗和網友的回答，可知AVL在查詢上是優于RB-Tree，但在刪除元素方面，RB-Tree所花費的時間要小于AVL的用時。這里我不能對插入效率做出評判，因為插入一個結點引起的不平衡，AVL和RB-Tree都是最多只需要2次旋轉操作，所以從理論上講，兩者的時間應該是差不多的(或者多次實驗的好壞是交替出現的)。但實驗數據往往是RB-Tree優于AVL，這點和代碼有關。在尋找AVL和RB-Tree做對比實驗的代碼時，我就發現了網上所給的代碼效率參差不齊。原本我使用的是嚴蔚敏數據結構的AVL代碼做實驗，但是嚴奶奶的書上沒有給出刪除操作的代碼，所以我就在網上找完整的代碼。在找代碼的過程中發現，有很多代碼能用，但效率太低了(而且我想找的是AVL和RB-Tree運行時間差距不是很大的代碼)。我甚至還發了一條Blink求助網友，但是沒有得到有效的回應，最后終于在Github上找到了可以用于驗證以上回答的代碼。可能各位也會對代碼本身有疑問，但這是我目前找到的最符合需求的代碼了。

?

參考：

https://github.com/skywind3000/avlmini

https://blog.csdn.net/mmshixing/article/details/51692892

http://www.zhihu.com/question/20545708/answer/58717264

http://www.zhihu.com/question/43744788/answer/9825888

總結

以上是生活随笔為你收集整理的红黑树(RB-Tree)比AVL强在哪？的全部內容，希望文章能夠幫你解決所遇到的問題。

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