很早之前就想寫一篇關於紅黑樹的文章，但是由於擔心自己理解的不透徹，就一直不敢下筆。於是在重新看了很多篇文章和資料之後，決定徹徹底底的把紅黑樹搞清楚。也希望讓你在面試中游刃有餘。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的父節點22變成黑色。
此時重新看一下是否滿足紅黑樹的五條特徵了沒，一條一條發現，第五條沒有滿足，也就是從任何一個節點出發，到葉子節點，這條路徑上沒有相同數目的黑色節點。比如從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手撕紅黑樹，在後續文章中我會添加。如有問題還請批評指正。
閱讀更多 Java的架構師技術棧 的文章
