RB-Tree和AVL樹(shù)作為BBST幼东，其實(shí)現(xiàn)的算法時(shí)間復(fù)雜度相同，AVL作為最先提出的BBST，貌似RB-tree實(shí)現(xiàn)的功能都可以用AVL樹(shù)是代替根蟹，那么為什么還需要引入RB-Tree呢脓杉？
- 紅黑樹(shù)不追求"完全平衡"，即不像AVL那樣要求節(jié)點(diǎn)的
|balFact| <= 1简逮，它只要求部分達(dá)到平衡球散，但是提出了為節(jié)點(diǎn)增加顏色，紅黑是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低散庶，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決蕉堰，而AVL是嚴(yán)格平衡樹(shù)，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候悲龟，根據(jù)不同情況嘁灯，旋轉(zhuǎn)的次數(shù)比紅黑樹(shù)要多。 - 就插入節(jié)點(diǎn)導(dǎo)致樹(shù)失衡的情況躲舌，AVL和RB-Tree都是最多兩次樹(shù)旋轉(zhuǎn)來(lái)實(shí)現(xiàn)復(fù)衡rebalance丑婿，旋轉(zhuǎn)的量級(jí)是O(1)
刪除節(jié)點(diǎn)導(dǎo)致失衡，AVL需要維護(hù)從被刪除節(jié)點(diǎn)到根節(jié)點(diǎn)root這條路徑上所有節(jié)點(diǎn)的平衡没卸，旋轉(zhuǎn)的量級(jí)為O(logN)羹奉，而RB-Tree最多只需要旋轉(zhuǎn)3次實(shí)現(xiàn)復(fù)衡，只需O(1)约计，所以說(shuō)RB-Tree刪除節(jié)點(diǎn)的rebalance的效率更高诀拭，開(kāi)銷(xiāo)更小煤蚌！ - AVL的結(jié)構(gòu)相較于RB-Tree更為平衡耕挨，插入和刪除引起失衡，如2所述尉桩，RB-Tree復(fù)衡效率更高筒占；當(dāng)然，由于AVL高度平衡蜘犁，因此AVL的Search效率更高啦翰苫。
- 針對(duì)插入和刪除節(jié)點(diǎn)導(dǎo)致失衡后的rebalance操作，紅黑樹(shù)能夠提供一個(gè)比較"便宜"的解決方案这橙，降低開(kāi)銷(xiāo)奏窑，是對(duì)search，insert 屈扎，以及delete效率的折衷埃唯，總體來(lái)說(shuō)，RB-Tree的統(tǒng)計(jì)性能高于AVL.
- 故引入RB-Tree是功能鹰晨、性能墨叛、空間開(kāi)銷(xiāo)的折中結(jié)果滑沧。
5.1 AVL更平衡，結(jié)構(gòu)上更加直觀巍实，時(shí)間效能針對(duì)讀取而言更高滓技；維護(hù)稍慢，空間開(kāi)銷(xiāo)較大棚潦。
5.2 紅黑樹(shù)令漂，讀取略遜于AVL，維護(hù)強(qiáng)于AVL丸边，空間開(kāi)銷(xiāo)與AVL類(lèi)似叠必，內(nèi)容極多時(shí)略?xún)?yōu)于AVL，維護(hù)優(yōu)于AVL妹窖。
基本上主要的幾種平衡樹(shù)看來(lái)纬朝，紅黑樹(shù)有著良好的穩(wěn)定性和完整的功能，性能表現(xiàn)也很不錯(cuò)骄呼，綜合實(shí)力強(qiáng)共苛，在諸如STL的場(chǎng)景中需要穩(wěn)定表現(xiàn)。
紅黑樹(shù)的查詢(xún)性能略微遜色于AVL樹(shù)蜓萄，因?yàn)槠浔華VL樹(shù)會(huì)稍微不平衡最多一層隅茎，也就是說(shuō)紅黑樹(shù)的查詢(xún)性能只比相同內(nèi)容的AVL樹(shù)最多多一次比較，但是嫉沽，紅黑樹(shù)在插入和刪除上優(yōu)于AVL樹(shù)辟犀，AVL樹(shù)每次插入刪除會(huì)進(jìn)行大量的平衡度計(jì)算，而紅黑樹(shù)為了維持紅黑性質(zhì)所做的紅黑變換和旋轉(zhuǎn)的開(kāi)銷(xiāo)绸硕，相較于AVL樹(shù)為了維持平衡的開(kāi)銷(xiāo)要小得多
- 總結(jié)：實(shí)際應(yīng)用中堂竟，若搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL玻佩，如果搜索出嘹，插入刪除次數(shù)幾乎差不多，應(yīng)該選擇RB夺蛇。
