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

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

AVL樹和紅黑樹的比較

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

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

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

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

延伸閱讀：

二、紅黑樹特征

紅黑樹聽名字就知道，里面涉及到兩種顏色：紅色和黑色。

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

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

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

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

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

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