data_structure_and_algorithm -- 紅黑樹（下）：掌握這些技巧，你也可以實現一個紅黑樹
今天主要看一下紅黑樹，主要參考：前谷歌工程師王爭的課程，感興趣可以通過下面方式微信掃碼購買：
紅黑樹是一個讓我又愛又恨的資料結構，“愛”是因為它穩定、高效的效能，“恨”是因為實現起來實在太難了。我今天講的紅黑樹的實現，對於基礎不太好的同學，理解起來可能會有些困難。但是，我覺得沒必要去死磕它。
我為什麼這麼說呢？因為，即便你將左右旋背得滾瓜爛熟，我保證你過不幾天就忘光了。因為，學習紅黑樹的程式碼實現，對於你平時做專案開發沒有太大幫助。對於絕大部分開發工程師來說，這輩子你可能都用不著親手寫一個紅黑樹。除此之外，它對於演算法面試也幾乎沒什麼用，一般情況下，靠譜的面試官也不會讓你手寫紅黑樹的。
如果你對資料結構和演算法很感興趣，想要開拓眼界、訓練思維，我還是很推薦你看一看這節的內容。但是如果學完今天的內容你還覺得懵懵懂懂的話，也不要糾結。我們要有的放矢去學習。你先把平時要用的、基礎的東西都搞會了，如果有餘力了，再來深入地研究這節內容。
好，我們現在就進入正式的內容。 上一節，我們講到紅黑樹定義的時候，提到紅黑樹的葉子節點都是黑色的空節點。當時我只是粗略地解釋了，這是為了程式碼實現方便，那更加確切的原因是什麼呢？ 我們這節就來說一說。
實現紅黑樹的基本思想
不知道你有沒有玩過魔方？其實魔方的復原解法是有固定演算法的：遇到哪幾面是什麼樣子，對應就怎麼轉幾下。你只要跟著這個復原步驟，就肯定能將魔方復原。
實際上，紅黑樹的平衡過程跟魔方復原非常神似，大致過程就是： 遇到什麼樣的節點排布，我們就對應怎麼去調整。 只要按照這些固定的調整規則來操作，就能將一個非平衡的紅黑樹調整成平衡的。
還記得我們前面講過的紅黑樹的定義嗎？今天的內容裡，我們會頻繁用到它，所以，我們現在再來回顧一下。一棵合格的紅黑樹需要滿足這樣幾個要求：
（1）根節點是黑色的；
（2）每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不儲存資料；
（3）任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；
（4）每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點。
在插入、刪除節點的過程中，第三、第四點要求可能會被破壞，而我們今天要講的“平衡調整”，實際上就是要把被破壞的第三、第四點恢復過來。
在正式開始之前，我先介紹兩個非常重要的操作， 左旋（rotate left）、右旋（rotate right）。左旋全稱其實是叫圍繞某個節點的左旋，那右旋的全稱估計你已經猜到了，就叫圍繞某個節點的右旋。
我們下面的平衡調整中，會一直用到這兩個操作，所以我這裡畫了個示意圖，幫助你徹底理解這兩個操作。圖中的 a，b，r 表示子樹，可以為空。
前面我說了，紅黑樹的插入、刪除操作會破壞紅黑樹的定義，具體來說就是會破壞紅黑樹的平衡，所以，我們現在就來看下，紅黑樹在插入、刪除資料之後，如何調整平衡，繼續當一棵合格的紅黑樹的。
插入操作的平衡調整
首先，我們來看插入操作。
紅黑樹規定，插入的節點必須是紅色的。而且，二叉查詢樹中新插入的節點都是放在葉子節點上。所以，關於插入操作的平衡調整，有這樣兩種特殊情況，但是也都非常好處理。
（1）如果插入節點的父節點是黑色的，那我們什麼都不用做，它仍然滿足紅黑樹的定義。
（2）如果插入的節點是根節點，那我們直接改變它的顏色，把它變成黑色就可以了。
除此之外，其他情況都會違背紅黑樹的定義，於是我們就需要進行調整，調整的過程包含兩種基礎的操作： 左右旋轉和改變顏色 。
紅黑樹的平衡調整過程是一個迭代的過程。我們把正在處理的節點叫作關注節點。關注節點會隨著不停地迭代處理，而不斷髮生變化。最開始的關注節點就是新插入的節點。
新節點插入之後，如果紅黑樹的平衡被打破，那一般會有下面三種情況。我們只需要根據每種情況的特點，不停地調整，就可以讓紅黑樹繼續符合定義，也就是繼續保持平衡。
我們下面依次來看每種情況的調整過程。提醒你注意下，為了簡化描述，我把父節點的兄弟節點叫作叔叔節點，父節點的父節點叫作祖父節點。
CASE 1：如果關注節點是 a，它的叔叔節點 d 是紅色，我們就依次執行下面的操作：
（1）將關注節點 a 的父節點 b、叔叔節點 d 的顏色都設定成黑色；
（2）將關注節點 a 的祖父節點 c 的顏色設定成紅色；
（3）關注節點變成 a 的祖父節點 c；
（4）跳到 CASE 2 或者 CASE 3。
CASE 2：如果關注節點是 a，它的叔叔節點 d 是黑色，關注節點 a 是其父節點 b 的右子節點，我們就依次執行下面的操作：
（1）關注節點變成節點 a 的父節點 b；
（2）圍繞新的關注節點b 左旋；
（3）跳到 CASE 3。
CASE 3： 如果關注節點是 a，它的叔叔節點 d 是黑色，關注節點 a 是其父節點 b 的左子節點 ，我們就依次執行下面的操作：
（1）圍繞關注節點 a 的祖父節點 c 右旋；
（2）將關注節點 a 的父節點 b、兄弟節點 c 的顏色互換。
（3）調整結束。
刪除操作的平衡調整
紅黑樹插入操作的平衡調整還不是很難，但是它的刪除操作的平衡調整相對就要難多了。不過原理都是類似的，我們依舊只需要根據關注節點與周圍節點的排布特點，按照一定的規則去調整就行了。
刪除操作的平衡調整分為兩步， 第一步是針對刪除節點初步調整。 初步調整隻是保證整棵紅黑樹在一個節點刪除之後，仍然滿足最後一條定義的要求，也就是說，每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點； 第二步是針對關注節點進行二次調整 ，讓它滿足紅黑樹的第三條定義，即不存在相鄰的兩個紅色節點。
1. 針對刪除節點初步調整
這裡需要注意一下，紅黑樹的定義中“只包含紅色節點和黑色節點”，經過初步調整之後，為了保證滿足紅黑樹定義的最後一條要求，有些節點會被標記成兩種顏色，“紅 - 黑”或者“黑 - 黑”。如果一個節點被標記為了“黑 - 黑”，那在計算黑色節點個數的時候，要算成兩個黑色節點。
在下面的講解中，如果一個節點既可以是紅色，也可以是黑色，在畫圖的時候，我會用一半紅色一半黑色來表示。如果一個節點是“紅 - 黑”或者“黑 - 黑”，我會用左上角的一個小黑點來表示額外的黑色。
CASE 1：如果要刪除的節點是 a，它只有一個子節點 b，那我們就依次進行下面的操作：
（1）刪除節點 a，並且把節點 b 替換到節點 a 的位置，這一部分操作跟普通的二叉查詢樹的刪除操作一樣；
（2）節點 a 只能是黑色，節點 b 也只能是紅色，其他情況均不符合紅黑樹的定義。這種情況下，我們把節點 b 改為黑色；
（3）調整結束，不需要進行二次調整。
CASE 2：如果要刪除的節點 a 有兩個非空子節點，並且它的後繼節點就是節點 a 的右子節點 c。我們就依次進行下面的操作：
（1）如果節點 a 的後繼節點就是右子節點 c，那右子節點 c 肯定沒有左子樹。我們把節點 a 刪除，並且將節點 c 替換到節點 a 的位置。這一部分操作跟普通的二叉查詢樹的刪除操作無異；
（2）然後把節點 c 的顏色設定為跟節點 a 相同的顏色；
（3）如果節點 c 是黑色，為了不違反紅黑樹的最後一條定義，我們給節點 c 的右子節點 d 多加一個黑色，這個時候節點 d 就成了“紅 - 黑”或者“黑 - 黑”；
（4）這個時候，關注節點變成了節點 d，第二步的調整操作就會針對關注節點來做。
CASE 3：如果要刪除的是節點 a，它有兩個非空子節點，並且節點 a 的後繼節點不是右子節點，我們就依次進行下面的操作：
（1）找到後繼節點 d，並將它刪除，刪除後繼節點 d 的過程參照 CASE 1；
（2）將節點 a 替換成後繼節點 d；
（3）把節點 d 的顏色設定為跟節點 a 相同的顏色；
（4）如果節點 d 是黑色，為了不違反紅黑樹的最後一條定義，我們給節點 d 的右子節點 c 多加一個黑色，這個時候節點 c 就成了“紅 - 黑”或者“黑 - 黑”；
（4）這個時候，關注節點變成了節點 c，第二步的調整操作就會針對關注節點來做。
2. 針對關注節點進行二次調整
經過初步調整之後，關注節點變成了“紅 - 黑”或者“黑 - 黑”節點。針對這個關注節點，我們再分四種情況來進行二次調整。二次調整是為了讓紅黑樹中不存在相鄰的紅色節點。
CASE 1：如果關注節點是 a，它的兄弟節點 c 是紅色的，我們就依次進行下面的操作：
（1）圍繞關注節點 a 的父節點 b 左旋；
（2）關注節點 a 的父節點 b 和祖父節點 c 交換顏色；
（3）關注節點不變；
（4）繼續從四種情況中選擇適合的規則來調整。
CASE 2：如果關注節點是 a，它的兄弟節點 c 是黑色的，並且節點 c 的左右子節點 d、e 都是黑色的，我們就依次進行下面的操作：
（1）將關注節點 a 的兄弟節點 c 的顏色變成紅色；
（2）從關注節點 a 中去掉一個黑色，這個時候節點 a 就是單純的紅色或者黑色；
（3）給關注節點 a 的父節點 b 新增一個黑色，這個時候節點 b 就變成了“紅 - 黑”或者“黑 - 黑”；
（4）關注節點從 a 變成其父節點 b；
（5）繼續從四種情況中選擇符合的規則來調整。
CASE 3： 如果關注節點是 a，它的兄弟節點 c 是黑色，c 的左子節點 d 是紅色，c 的右子節點 e 是黑色， 我們就依次進行下面的操作：
（1）圍繞關注節點 a 的兄弟節點 c 右旋；
（2）節點 c 和節點 d 交換顏色；
（3）關注節點不變；
（4）跳轉到 CASE 4，繼續調整。
CASE 4：如果關注節點 a 的兄弟節點 c 是黑色的，並且 c 的右子節點是紅色的，我們就依次進行下面的操作：
（1）圍繞關注節點 a 的父節點 b 左旋；
（2）將關注節點 a 的兄弟節點 c 的顏色，跟關注節點 a 的父節點 b 設定成相同的顏色；
（3）將關注節點 a 的父節點 b 的顏色設定為黑色；
（4）從關注節點 a 中去掉一個黑色，節點 a 就變成了單純的紅色或者黑色；
（5）將關注節點 a 的叔叔節點 e 設定為黑色；
（6）調整結束。
解答開篇
紅黑樹的平衡調整就講完了，現在，你能回答開篇的問題了嗎？為什麼紅黑樹的定義中，要求葉子節點是黑色的空節點？
要我說，之所以有這麼奇怪的要求，其實就是為了實現起來方便。只要滿足這一條要求，那在任何時刻，紅黑樹的平衡操作都可以歸結為我們剛剛講的那幾種情況。
還是有點不好理解，我通過一個例子來解釋一下。假設紅黑樹的定義中不包含剛剛提到的那一條“葉子節點必須是黑色的空節點”，我們往一棵紅黑樹中插入一個數據，新插入節點的父節點也是紅色的，兩個紅色的節點相鄰，這個時候，紅黑樹的定義就被破壞了。那我們應該如何調整呢？
你會發現，這個時候，我們前面講的插入時，三種情況下的平衡調整規則，沒有一種是適用的。但是，如果我們把黑色的空節點都給它加上，變成下面這樣，你會發現，它滿足 CASE 2 了。
你可能會說，你可以調整一下平衡調整規則啊。比如把 CASE 2 改為“如果關注節點 a 的叔叔節點 b 是黑色或者不存在，a 是父節點的右子節點，就進行某某操作”。當然可以，但是這樣的話規則就沒有原來簡潔了。
你可能還會說，這樣給紅黑樹新增黑色的空的葉子節點，會不會比較浪費儲存空間呢？答案是不會的。雖然我們在講解或者畫圖的時候，每個黑色的、空的葉子節點都是獨立畫出來的。實際上，在具體實現的時候，我們只需要像下面這樣，共用一個黑色的、空的葉子節點就行了。
內容小結
“紅黑樹一向都很難學”，有這種想法的人很多。但是我感覺，其實主要原因是，很多人試圖去記憶它的平衡調整策略。實際上，你只需要能看懂我講的過程，沒有知識盲點，就算是掌握了這部分內容了。畢竟實際的軟體開發並不是閉卷考試，當你真的需要實現一個紅黑樹的時候，可以對照著我講的步驟，一點一點去實現。
現在，我就來總結一下，如何比較輕鬆地看懂我今天講的操作過程。
第一點， 把紅黑樹的平衡調整的過程比作魔方復原，不要過於深究這個演算法的正確性。 你只需要明白，只要按照固定的操作步驟，保持插入、刪除的過程，不破壞平衡樹的定義就行了。
第二點， 找準關注節點，不要搞丟、搞錯關注節點。 因為每種操作規則，都是基於關注節點來做的，只有弄對了關注節點，才能對應到正確的操作規則中。在迭代的調整過程中，關注節點在不停地改變，所以，這個過程一定要注意，不要弄丟了關注節點。
第三點， 插入操作的平衡調整比較簡單，但是刪除操作就比較複雜。 針對刪除操作，我們有兩次調整，第一次是針對要刪除的節點做初步調整，讓調整後的紅黑樹繼續滿足第四條定義，“每個節點到可達葉子節點的路徑都包含相同個數的黑色節點”。但是這個時候，第三條定義就不滿足了，有可能會存在兩個紅色節點相鄰的情況。第二次調整就是解決這個問題，讓紅黑樹不存在相鄰的紅色節點。