一、avl樹/紅黑樹的旋轉為什么不會改變順序

因為右旋轉為左旋轉的鏡像，而雙旋轉可以分解為兩個單旋轉，因此可以推出四種旋轉都不會改變AVL樹的平衡特性，不會改變順序。AVL樹是以二分搜索樹（BST）為底層數據結構而實現的，其特性是需要維護AVL的平衡因子。

AVL樹和紅黑樹的比較

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

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

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

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

延伸閱讀：

二、紅黑樹特征

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

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

（2）根節點是黑色的。

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

（4）從根節點到葉子節點，不會出現兩個連續的紅色節點。

（5）從任何一個節點出發，到葉子節點，這條路徑上都有相同數目的黑色節點。

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