RB-Tree和AVL樹作為BBST，其實現(xiàn)的算法時間復(fù)雜度相同，AVL作為最先提出的BBST，貌似RB-tree實現(xiàn)的功能都可以用AVL樹是代替，那么為什么還需要引入RB-Tree呢？

紅黑樹不追求"完全平衡"，即不像AVL那樣要求節(jié)點的 |balFact| <= 1，它只要求部分達(dá)到平衡，但是提出了為節(jié)點增加顏色，紅黑是用非嚴(yán)格的平衡來換取增刪節(jié)點時候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決，而AVL是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點的時候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。
就插入節(jié)點導(dǎo)致樹失衡的情況，AVL和RB-Tree都是最多兩次樹旋轉(zhuǎn)來實現(xiàn)復(fù)衡rebalance，旋轉(zhuǎn)的量級是O(1)
刪除節(jié)點導(dǎo)致失衡，AVL需要維護從被刪除節(jié)點到根節(jié)點root這條路徑上所有節(jié)點的平衡，旋轉(zhuǎn)的量級為O(logN)，而RB-Tree最多只需要旋轉(zhuǎn)3次實現(xiàn)復(fù)衡，只需O(1)，所以說RB-Tree刪除節(jié)點的rebalance的效率更高，開銷更??！
AVL的結(jié)構(gòu)相較于RB-Tree更為平衡，插入和刪除引起失衡，如2所述，RB-Tree復(fù)衡效率更高；當(dāng)然，由于AVL高度平衡，因此AVL的Search效率更高啦。
針對插入和刪除節(jié)點導(dǎo)致失衡后的rebalance操作，紅黑樹能夠提供一個比較"便宜"的解決方案，降低開銷，是對search，insert ，以及delete效率的折衷，總體來說，RB-Tree的統(tǒng)計性能高于AVL.
故引入RB-Tree是功能、性能、空間開銷的折中結(jié)果。
5.1 AVL更平衡，結(jié)構(gòu)上更加直觀，時間效能針對讀取而言更高；維護稍慢，空間開銷較大。
5.2 紅黑樹，讀取略遜于AVL，維護強于AVL，空間開銷與AVL類似，內(nèi)容極多時略優(yōu)于AVL，維護優(yōu)于AVL。
基本上主要的幾種平衡樹看來，紅黑樹有著良好的穩(wěn)定性和完整的功能，性能表現(xiàn)也很不錯，綜合實力強，在諸如STL的場景中需要穩(wěn)定表現(xiàn)。
紅黑樹的查詢性能略微遜色于AVL樹，因為其比AVL樹會稍微不平衡最多一層，也就是說紅黑樹的查詢性能只比相同內(nèi)容的AVL樹最多多一次比較，但是，紅黑樹在插入和刪除上優(yōu)于AVL樹，AVL樹每次插入刪除會進(jìn)行大量的平衡度計算，而紅黑樹為了維持紅黑性質(zhì)所做的紅黑變換和旋轉(zhuǎn)的開銷，相較于AVL樹為了維持平衡的開銷要小得多

總結(jié)：實際應(yīng)用中，若搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL，如果搜索，插入刪除次數(shù)幾乎差不多，應(yīng)該選擇RB。