一、avl樹(shù)/紅黑樹(shù)的旋轉(zhuǎn)為什么不會(huì)改變順序

因?yàn)橛倚D(zhuǎn)為左旋轉(zhuǎn)的鏡像，而雙旋轉(zhuǎn)可以分解為兩個(gè)單旋轉(zhuǎn)，因此可以推出四種旋轉(zhuǎn)都不會(huì)改變AVL樹(shù)的平衡特性，不會(huì)改變順序。AVL樹(shù)是以二分搜索樹(shù)（BST）為底層數(shù)據(jù)結(jié)構(gòu)而實(shí)現(xiàn)的，其特性是需要維護(hù)AVL的平衡因子。

AVL樹(shù)和紅黑樹(shù)的比較

經(jīng)常在網(wǎng)上看到關(guān)于AVL樹(shù)和紅黑樹(shù)的討論，討論的雙方往往各執(zhí)一詞，都在試圖證明到底哪個(gè)更加優(yōu)越。并且似乎都可以給出充足的理論依據(jù)，但最后的結(jié)果往往是誰(shuí)也不能說(shuō)服誰(shuí)。我認(rèn)為問(wèn)題的根源在于沒(méi)有對(duì)齊討論對(duì)象，當(dāng)我們?cè)诒容^AVL樹(shù)和紅黑樹(shù)時(shí)，首先需要明確的是：我們到底在比較什么？

空間開(kāi)銷。AVL樹(shù)的每個(gè)節(jié)點(diǎn)需要額外兩比特來(lái)表示左斜、平衡、右斜三種狀態(tài)，而紅黑樹(shù)的每個(gè)節(jié)點(diǎn)只需要額外一比特來(lái)表示紅、黑兩種顏色，看起來(lái)是紅黑樹(shù)占據(jù)了優(yōu)勢(shì)。但是結(jié)構(gòu)體空間的分配不可能是以比特為單位來(lái)進(jìn)行的，因此在以字節(jié)為單位分配內(nèi)存的情況下紅黑樹(shù)的優(yōu)勢(shì)便沒(méi)有了。從另一個(gè)角度來(lái)講，不管是兩比特還是一比特，都可以把它編碼到某個(gè)指針域的最低兩位，理由是內(nèi)存對(duì)齊使得指針域的最低兩位必然為零。在這種騷操作的情況下，AVL樹(shù)和紅黑樹(shù)的空間開(kāi)銷也是一模一樣的。順帶提一點(diǎn)不太相關(guān)的，父指針域要不要都可以，區(qū)別是不要父指針域可以使空間開(kāi)銷更小，然而代價(jià)是循環(huán)的時(shí)候需要維護(hù)一個(gè)棧結(jié)構(gòu)，因此主流的實(shí)現(xiàn)是犧牲這一點(diǎn)微弱的空間開(kāi)銷以獲取更快的運(yùn)行速度。實(shí)現(xiàn)難度。有一種觀點(diǎn)認(rèn)為紅黑樹(shù)插入和刪除后的調(diào)整過(guò)程需要考慮太多的場(chǎng)景了，而AVL樹(shù)只需要比較左右子樹(shù)的高度決定如何旋轉(zhuǎn)即可，因此AVL樹(shù)的實(shí)現(xiàn)難度要低于紅黑樹(shù)。事實(shí)上我以前學(xué)習(xí)的時(shí)候在網(wǎng)上看過(guò)不下十份的AVL樹(shù)代碼，幾乎沒(méi)有正確的(有的版本不保存平衡因子而保存高度，有的版本甚至每一次都用遞歸來(lái)求高度)。這兩種樹(shù)我都親自實(shí)現(xiàn)過(guò)，就以自己的經(jīng)驗(yàn)來(lái)看，在考慮各種Corner case、常數(shù)時(shí)間返回最值元素、指針向前向后迭代、對(duì)重復(fù)元素進(jìn)行支持等等條件的限制下，要無(wú)誤且優(yōu)雅地實(shí)現(xiàn)這兩者之間的任意一個(gè)都是很困難的。鑒于實(shí)現(xiàn)難度是個(gè)比較主觀的東西，這里就不做過(guò)多的評(píng)價(jià)了。時(shí)間開(kāi)銷。也是大家通常說(shuō)的時(shí)間復(fù)雜度，這個(gè)恐怕才是爭(zhēng)議的核心，后面所有的篇幅都將針對(duì)它來(lái)討論。

一般說(shuō)來(lái)，不管是AVL樹(shù)還是紅黑樹(shù)，不管是插入還是刪除(我們不專門(mén)另討論查找，它包含在了插入和刪除中)，操作的開(kāi)銷大致都可以分解成如下兩部分：

查找開(kāi)銷。插入前總是需要查找到具體的位置才行，需要不斷向下查找直至外節(jié)點(diǎn)。刪除前一般也要查找到對(duì)應(yīng)元素，雖然這不是必要的，但是將查找和刪除合在一起討論顯得更加方便一些。調(diào)整開(kāi)銷。插入和刪除都有可能打破原來(lái)的平衡約束，因此需要一層一層地向上調(diào)整。每一次的調(diào)整開(kāi)銷里面具體又會(huì)包含：a.?變色開(kāi)銷，即修改節(jié)點(diǎn)的顏色(或者平衡因子)帶來(lái)的開(kāi)銷；b.?旋轉(zhuǎn)開(kāi)銷，即旋轉(zhuǎn)操作中修改各種指針指向帶來(lái)的開(kāi)銷。這兩種開(kāi)銷的系數(shù)是不一樣的，在需要精確討論的時(shí)候應(yīng)該嚴(yán)格區(qū)分而不能把它們混為一談。

延伸閱讀：

二、紅黑樹(shù)特征

紅黑樹(shù)聽(tīng)名字就知道，里面涉及到兩種顏色：紅色和黑色。

（1）每個(gè)節(jié)點(diǎn)只有兩種顏色：紅色和黑色。

（2）根節(jié)點(diǎn)是黑色的。

（3）每個(gè)葉子節(jié)點(diǎn)（NIL）都是黑色的空節(jié)點(diǎn)。

（4）從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，不會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。

（5）從任何一個(gè)節(jié)點(diǎn)出發(fā)，到葉子節(jié)點(diǎn)，這條路徑上都有相同數(shù)目的黑色節(jié)點(diǎn)。

這五條就是紅黑樹(shù)的特征，你每看一個(gè)特征較好重新看一遍圖，這樣可以加深理解。這五條特征看起來(lái)真的很復(fù)雜，不過(guò)正是由于這些復(fù)雜的特征才保證了紅黑樹(shù)的良好特性。