一、為什么要引入紅黑樹(shù)

因?yàn)锳VL樹(shù)比紅黑樹(shù)更加平衡，但AVL樹(shù)在插入和刪除的時(shí)候也會(huì)存在大量的旋轉(zhuǎn)操作。所以當(dāng)你的應(yīng)用涉及到頻繁的插入和刪除操作，切記放棄AVL樹(shù)，選擇性能更好的紅黑樹(shù)。

紅黑樹(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)銷更小！

延伸閱讀：

二、什么樣的數(shù)據(jù)結(jié)構(gòu)稱為紅黑樹(shù)

紅黑樹(shù)（Red Black Tree）是一種自平衡的二叉查找樹(shù)，它與平衡二叉樹(shù)相同的地方在于都是為了維護(hù)查找樹(shù)的平衡而構(gòu)建的數(shù)據(jù)結(jié)構(gòu)，它的主要特征是在二叉查找樹(shù)的每個(gè)節(jié)點(diǎn)上添加了一個(gè)屬性表示顏色，顏色有兩種，紅與黑。

性質(zhì)：

每個(gè)節(jié)點(diǎn)是紅色或者黑色；

根節(jié)點(diǎn)是黑色；

所有葉子節(jié)點(diǎn)都是黑色（葉子是NIL節(jié)點(diǎn)，也稱為外節(jié)點(diǎn)）;

每個(gè)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)都是黑色（從每個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）；

從紅黑樹(shù)的任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（包含黑色節(jié)點(diǎn)的數(shù)目稱為該節(jié)點(diǎn)的黑高度）。