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

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

一、二叉查找樹

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

 

 

從這張圖我們會發(fā)現(xiàn)如下的規(guī)律：

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

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

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

 

 

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

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

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

 

 

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

 

 

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

二、平衡二叉樹

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

 

 

上面這顆二叉樹就是平衡二叉樹，也叫作AVL樹。仔細(xì)分析你會發(fā)現(xiàn)如下特點：

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

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

現(xiàn)在我們再往里插入一個元素4，這時候會發(fā)生什么呢?

 

 

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

 

 

我們發(fā)現(xiàn)經(jīng)過調(diào)整之后，我們二叉樹就重新回到了平衡。對于其他插入的情況，大家可以自己私下試一遍，最終你會發(fā)現(xiàn)一個結(jié)論，那就是平衡二叉樹在插入時最多只需要兩次旋轉(zhuǎn)就會重新恢復(fù)平衡。

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

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

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

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

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

三、紅黑樹

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

 

 

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

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

(2)根節(jié)點是黑色的。

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

(4)從根節(jié)點到葉子節(jié)點，不會出現(xiàn)兩個連續(xù)的紅色節(jié)點。

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

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

1、查詢節(jié)點

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

2、插入節(jié)點

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

第一種情況：新節(jié)點沒有父節(jié)點

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

第二種情況：新節(jié)點的父節(jié)點是黑色

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

 

 

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

第三種情況：新節(jié)點的父親節(jié)點為紅色

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

 

 

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

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

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

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

(4)從根節(jié)點到葉子節(jié)點，不會出現(xiàn)兩個連續(xù)的紅色節(jié)點。這一條發(fā)現(xiàn)不滿足。

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

(1)叔叔節(jié)點是紅色：

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

第一步：把新節(jié)點21的父節(jié)點22變成黑色。

 

 

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

第二步：把22的父節(jié)點25變成紅色

 

 

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

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

第三步：把節(jié)點27變成黑色

 

 

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

第四步：把節(jié)點17和節(jié)點18都變成黑色節(jié)點

 

 

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

(1)叔叔節(jié)點是黑色：

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

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

 

 

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

 

 

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

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

3、刪除節(jié)點

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

刪除大致分了三種情況，

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

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

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

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

 

 

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

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

現(xiàn)在刪除的節(jié)點有兩個子節(jié)點，同樣的我們可以執(zhí)行第二種情況的操作，

 

 

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

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

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

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

四、使用場景

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