[[388563]]

很早之前就想寫一篇關于紅黑樹的文章，但是由于擔心自己理解的不透徹，就一直不敢下筆。于是在重新看了很多篇文章和資料之后，決定徹徹底底的把紅黑樹搞清楚。也希望讓你在面試中游刃有余。OK，廢話不多說，開始今天的文章。

整篇文章的思路是這樣的，紅黑樹其實就是一種數據結構，設計它的目的就是為了高效地進行增刪改查，所以我們文章的順序也會按照這個思路來進行。我們先從二叉查找樹逐漸引入到紅黑樹，然后再詳細的講解。你如果看過其他文章想必也一定清楚，紅黑樹比較麻煩，希望你有點耐心，認真理解每一張圖再往下分析。

一、二叉查找樹

在正式開始了解紅黑樹之前呢，我們先來看一下二叉查找樹的概念，從淺入深，希望你不要著急，下面就是是一顆二叉查找樹：

 

從這張圖我們會發現如下的規律：

(1)左子樹上所有結點的值均小于或等于它的根結點的值。

(2)右子樹上所有結點的值均大于或等于它的根結點的值。

如果我們想要查找一個數字11，過程是怎么樣的呢?

 

上面的過程已經很清晰了，在查找的時候，先與根節點比較，比根節點大則從右子樹查找，比根節點小則從左子樹查找，然后重復上面的過程，一直到找到我們需要的元素為止。

這個過程是查找操作，對于添加和刪除呢?其實原理也是一樣的，我們第一步就是找到我們需要插入的位置，然后把元素插入即可。這樣看二叉查找樹挺好的呀?別著急我們繼續往下看這種情況。

如果我們在剛剛開始的時候還是以9為根節點，然后依次插入13、15、17、19。我們看會發生什么情況：

 

好好地一棵樹變成了這個鬼樣子，成了“一邊倒”了。這時候再去查找19呢?

這效率也太低下了吧，一顆二叉查找樹的優勢完全喪失了。怎么辦呢?既然上面的二叉查找樹在插入的時候變成了“一條腿”，也就是喪失了平衡，那我們干脆做出一點改進，使用平衡二叉樹吧。

二、平衡二叉樹

下面就是一顆平衡二叉樹。

 

上面這顆二叉樹就是平衡二叉樹，也叫作AVL樹。仔細分析你會發現如下特點：

(1)從任何一個節點出發，左右子樹深度之差的絕對值不超過1。

(2)左右子樹仍然為平衡二叉樹。

現在我們再往里插入一個元素4，這時候會發生什么呢?

 

從圖中我們可以看到，插入了4之后破壞了平衡，怎么辦呢?既然破壞了平衡，那就想辦法糾正過來。

 

我們發現經過調整之后，我們二叉樹就重新回到了平衡。對于其他插入的情況，大家可以自己私下試一遍，最終你會發現一個結論，那就是平衡二叉樹在插入時最多只需要兩次旋轉就會重新恢復平衡。

從上面這個過程我們會發現，平衡二叉樹真的很不錯，在查找時既有著二叉查找樹的優越性，在插入時還能通過調整繼續保持著。那么為什么還要使用到紅黑樹呢?我覺得可以從以下兩個方面來考慮：

(1)刪除：對于平衡二叉樹來說，在最壞情況下，需要維護從被刪節點到根節點這條路徑上所有節點的平衡性，旋轉的量級是O(logN)。但是紅黑樹就不一樣了，最多只需3次旋轉就會重新平衡，旋轉的量級是O(1)。

(2)保持平衡：平衡二叉樹高度平衡，這也就意味著在大量插入和刪除節點的場景下，平衡二叉樹為了保持平衡需要調整的頻率會更高。

注意：在大量查找的情況下，平衡二叉樹的效率更高，也是首要選擇。

在大量增刪的情況下，紅黑樹是首選。

鑒于以上原因，因此我們才使用到了紅黑樹這種更好的結構。上面提了這么多次紅黑樹，相信你已經迫不及待的想要認識一下了。下面就正式拉開紅黑樹的序幕。

三、紅黑樹

紅黑樹聽名字就知道，里面涉及到兩種顏色：紅色和黑色。我們直接來看一下：

 

上面這張圖就是紅黑樹，你會發現他有如下特征(下面的特征最好看一個特征重新看一遍紅黑樹)：

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

(2)根節點是黑色的。

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

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

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

這五條就是紅黑樹的特征，你每看一個特征最好重新看一遍圖，這樣可以加深理解。這五條特征看起來真的很復雜，不過正是由于這些復雜的特征才保證了紅黑樹的良好特性。如何保證的呢?我們從增刪改查四個角度來一個一個分析一下：

1、查詢節點

查詢節點是最簡單的一個，他的查找過程和二叉查找樹一樣，查找元素比當前節點大，就從右子樹繼續查找比較，查找元素比當前節點小，就從左子樹繼續查找比較。查找過程就不再贅述了。

2、插入節點

插入節點是最麻煩的一個，它分為三種情況。我們一種一種看，這樣比較有條理性。

第一種情況：新節點沒有父節點

沒有父節點只有一種情況，就是插入的節點是整棵樹第一個節點，也就是根節點，為此我們只需要把插入節點涂成黑色就OK了。這也就保證了性質2：根節點是黑色的。

第二種情況：新節點的父節點是黑色

為此我們舉一個例子，比如說上面的紅黑樹中，我們插入節點14。來看一下會發生什么情況?

 

這種情況我們發現新插入節點14的父節點就是黑色的。現在為了保證紅黑樹的性質，我們對照每個特性來檢查一遍。只要有一條不滿足，我們都需要調整。我們重新對照之后會發現每一條都符合。此時不需要調整。

第三種情況：新節點的父親節點為紅色

我們還是舉個例子，比如我們在最開始的紅黑樹基礎之上插入節點21，此時會發生什么情況呢?

 

此時還是老規矩，對照著紅黑樹的5個特征一個一個來看，只要是違反了一條就需要做出調整。我們來看一下：

(1)每個節點只有兩種顏色：紅色和黑色。這一條滿足。

(2)根節點是黑色的。這一條也滿足。

(3)每個葉子節點(NIL)都是黑色的空節點。這一條滿足。

(4)從根節點到葉子節點，不會出現兩個連續的紅色節點。這一條發現不滿足。

就是上面這一條規則沒有滿足，所以我們此時需要調整?問題來了如何調整呢?因為直接看父節點沒辦法實現，所以還需要觀察另外的節點，也就是新節點的叔叔節點。根據叔叔節點的顏色來調整。調整的方式有兩種：變色和旋轉。

(1)叔叔節點是紅色：

此時插入的節點是21，但是叔叔節點是27，更好是紅色。我們直接來看調整的步驟：

第一步：把新節點21的父節點變成黑色。

 

此時重新看一下是否滿足紅黑樹的五條特征了沒，一條一條發現，第五條沒有滿足，也就是從任何一個節點出發，到葉子節點，這條路徑上沒有相同數目的黑色節點。比如從25出發。這時候怎么辦呢?那就繼續調整。

第二步：把22的父節點25變成紅色

 

這時候還是老規矩，不要嫌棄麻煩，因為只有經歷了一步又一步的麻煩之后，你才能牢記那5條規則特征。我們對照之后會發現節點25和節點27是兩個連續的紅色節點，這時候又破壞了規則4。怎么辦呢?那就繼續調整就OK了。

難道這時候還要繼續往上調整嗎?如果你這樣做就錯了，因為不斷地往上調整最后就會把根節點變成了紅色，會走進死胡同。我們往下走。

第三步：把節點27變成黑色

 

來吧，繼續重新審查那5條規則特征。很明顯節點17和節點25是兩個連續的紅色，又破壞了。是不是心太累了，調整了這么久，還是沒有保證那5條規則，感覺是不是還沒有平衡二叉樹好。如果你現在有這種感覺，我只能說，希望你繼續堅持下去，勝利就在眼前。

第四步：把節點17和節點18都變成黑色節點

 

來來來，現在你再對照一下那5條規則，是不是完全保證了。寫到這真的是太累了，和你讀這篇文章的感覺一樣一樣的，不過這種情況也只是插入情況中的一種。繼續往下看：

(1)叔叔節點是黑色：

這種情況下又分了兩種情況：

第一種情況：新插入節點為父節點的左孩子

 

第二種情況：新插入節點為父節點的右孩子

 

按照第一遍的思路，我們對這兩種情況執行同樣的操作，最終也能保證紅黑樹的5條特征。

到了這一步，插入操作的所有情況就講解完畢。另外關于左旋和右旋的知識我在這里不再說明了，因為你看到了紅黑樹這個程度，相信也一定看過平衡二叉樹。左旋右旋哪幾種情況，都會有介紹到。

3、刪除節點

紅黑樹的刪除說實話更加的復雜，如果你看過算法導論的話應該能明白一點，我們在這里也進行一個大概的講解。

刪除大致分了三種情況，

(1)第一種情況：要刪除的節點有零個子節點

這種情況下最簡單，也就是刪除的是根節點或者是葉子節點(這里的葉子節點都是指非NULL的葉子節點)，根節點直接刪除即可。如果葉子節點是紅色的，也可以直接刪除，如果葉子節點是黑色的，那么就需要進行調整，調整的步驟和插入時調整的步驟一樣。

(2)第二種情況：要刪除的節點有一個子節點

這時候。把子節點的值替換掉要刪除的節點的值。

 

現在我們的5把11替換掉之后，又回到了第一種情況。如果節點5是紅色的，可以直接刪除，如果節點5是黑色的，那么就需要進行調整，此時的節點5就是葉子節點。調整的步驟和插入時調整的步驟一樣。

(3)第三種情況：要刪除的節點有兩個子節點

現在刪除的節點有兩個子節點，同樣的我們可以執行第二種情況的操作，

 

若節點13之前是葉子節點，那就和第一種情況一樣了，如果節點13是紅色的，可以直接刪除，如果節點13是黑色的，那么就需要進行調整，此時的節點13就是葉子節點。調整的步驟和插入時調整的步驟一樣。

若節點13之前還有子節點，那就和第二種情況一樣了。那就繼續替換和判斷。

以上呢就是刪除的情況，最后一種情況是修改，這種情況是查找和插入的結合體，也就是先找到要修改的元素，修改完值之后，繼續進行調整即可。

現在還有最后一個問題了，都說紅黑樹很重要，為什么重要呢?我們來看一下使用場景。

四、使用場景

 

紅黑樹的應用真的是太多了，比如說java中的HashMap和TreeMap。還有就是linux也經常使用到。這種數據結構在面試的時候是一個常問問題，希望大家能夠明白和理解。如何用java手撕紅黑樹，在后續文章中我會添加。如有問題還請批評指正。