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

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

AVL樹和紅黑樹的比較

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

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

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

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

延伸閱讀：

二、紅黑樹特征

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

（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)。

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