整篇文章的思路是這樣的，紅黑樹其實(shí)就是一種數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)它的目的就是為了高效地進(jìn)行增刪改查，所以我們文章的順序也會(huì)按照這個(gè)思路來(lái)進(jìn)行。我們先從二叉查找樹逐漸引入到紅黑樹，然后再詳細(xì)的講解。你如果看過其他文章想必也一定清楚，紅黑樹比較麻煩，希望你有點(diǎn)耐心，認(rèn)真理解每一張圖再往下分析。
一、二叉查找樹
在正式開始了解紅黑樹之前呢，我們先來(lái)看一下二叉查找樹的概念，從淺入深，希望你不要著急，下面就是是一顆二叉查找樹：
從這張圖我們會(huì)發(fā)現(xiàn)如下的規(guī)律：
（1）左子樹上所有節(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值。
（2）右子樹上所有節(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。
如果我們想要查找一個(gè)數(shù)字11，過程是怎么樣的呢？
上面的過程已經(jīng)很清晰了，在查找的時(shí)候，先與根節(jié)點(diǎn)比較，比根節(jié)點(diǎn)大則從右子樹查找，比根節(jié)點(diǎn)小則從左子樹查找，然后重復(fù)上面的過程，一直到找到我們需要的元素為止。
這個(gè)過程是查找操作，對(duì)于添加和刪除呢？其實(shí)原理也是一樣的，我們第一步就是找到我們需要插入的位置，然后把元素插入即可。這樣看二叉查找樹挺好的呀？別著急我們繼續(xù)往下看這種情況。
如果我們?cè)趧倓傞_始的時(shí)候還是以9為根節(jié)點(diǎn)，然后依次插入13、15、17、19。我們看會(huì)發(fā)生什么情況：
好好地一棵樹變成了這個(gè)鬼樣子，成了“一邊倒”了。這時(shí)候再去查找19呢？
這效率也太低下了吧，一顆二叉查找樹的優(yōu)勢(shì)完全喪失了。怎么辦呢？既然上面的二叉查找樹在插入的時(shí)候變成了“一條腿”，也就是喪失了平衡，那我們干脆做出一點(diǎn)改進(jìn)，使用平衡二叉樹吧。
二、平衡二叉樹
下面就是一顆平衡二叉樹。
上面這顆二叉樹就是平衡二叉樹，也叫作AVL樹。仔細(xì)分析你會(huì)發(fā)現(xiàn)如下特點(diǎn)：
（1）從任何一個(gè)節(jié)點(diǎn)出發(fā)，左右子樹深度之差的絕對(duì)值不超過1。
（2）左右子樹仍然為平衡二叉樹。
現(xiàn)在我們?cè)偻锊迦胍粋€(gè)元素4，這時(shí)候會(huì)發(fā)生什么呢？
從圖中我們可以看到，插入了4之后破壞了平衡，怎么辦呢？既然破壞了平衡，那就想辦法糾正過來(lái)。
我們發(fā)現(xiàn)經(jīng)過調(diào)整之后，我們二叉樹就重新回到了平衡。對(duì)于其他插入的情況，大家可以自己私下試一遍，最終你會(huì)發(fā)現(xiàn)一個(gè)結(jié)論，那就是平衡二叉樹在插入時(shí)最多只需要兩次旋轉(zhuǎn)就會(huì)重新恢復(fù)平衡。
從上面這個(gè)過程我們會(huì)發(fā)現(xiàn)，平衡二叉樹真的很不錯(cuò)，在查找時(shí)既有著二叉查找樹的優(yōu)越性，在插入時(shí)還能通過調(diào)整繼續(xù)保持著。那么為什么還要使用到紅黑樹呢？我覺得可以從以下兩個(gè)方面來(lái)考慮：
（1）刪除：對(duì)于平衡二叉樹來(lái)說(shuō)，在最壞情況下，需要維護(hù)從被刪節(jié)點(diǎn)到根節(jié)點(diǎn)這條路徑上所有節(jié)點(diǎn)的平衡性，旋轉(zhuǎn)的量級(jí)是O(logN)。但是紅黑樹就不一樣了，最多只需3次旋轉(zhuǎn)就會(huì)重新平衡，旋轉(zhuǎn)的量級(jí)是O(1)。
（2）保持平衡：平衡二叉樹高度平衡，這也就意味著在大量插入和刪除節(jié)點(diǎn)的場(chǎng)景下，平衡二叉樹為了保持平衡需要調(diào)整的頻率會(huì)更高。
注意：在大量查找的情況下，平衡二叉樹的效率更高，也是首要選擇。在大量增刪的情況下，紅黑樹是首選。
鑒于以上原因，因此我們才使用到了紅黑樹這種更好的結(jié)構(gòu)。上面提了這么多次紅黑樹，相信你已經(jīng)迫不及待的想要認(rèn)識(shí)一下了。下面就正式拉開紅黑樹的序幕。
三、紅黑樹
紅黑樹聽名字就知道，里面涉及到兩種顏色：紅色和黑色。我們直接來(lái)看一下：
上面這張圖就是紅黑樹，你會(huì)發(fā)現(xiàn)他有如下特征（下面的特征最好看一個(gè)特征重新看一遍紅黑樹）：
（1）每個(gè)節(jié)點(diǎn)只有兩種顏色：紅色和黑色。
（2）根節(jié)點(diǎn)是黑色的。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）都是黑色的空節(jié)點(diǎn)。
（4）從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，不會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。
（5）從任何一個(gè)節(jié)點(diǎn)出發(fā)，到葉子節(jié)點(diǎn)，這條路徑上都有相同數(shù)目的黑色節(jié)點(diǎn)。
這五條就是紅黑樹的特征，你每看一個(gè)特征最好重新看一遍圖，這樣可以加深理解。這五條特征看起來(lái)真的很復(fù)雜，不過正是由于這些復(fù)雜的特征才保證了紅黑樹的良好特性。如何保證的呢？我們從增刪改查四個(gè)角度來(lái)一個(gè)一個(gè)分析一下：
1、查詢節(jié)點(diǎn)
查詢節(jié)點(diǎn)是最簡(jiǎn)單的一個(gè)，他的查找過程和二叉查找樹一樣，查找元素比當(dāng)前節(jié)點(diǎn)大，就從右子樹繼續(xù)查找比較，查找元素比當(dāng)前節(jié)點(diǎn)小，就從左子樹繼續(xù)查找比較。查找過程就不再贅述了。
2、插入節(jié)點(diǎn)
插入節(jié)點(diǎn)是最麻煩的一個(gè)，它分為三種情況。我們一種一種看，這樣比較有條理性。
第一種情況：新節(jié)點(diǎn)沒有父節(jié)點(diǎn)
沒有父節(jié)點(diǎn)只有一種情況，就是插入的節(jié)點(diǎn)是整棵樹第一個(gè)節(jié)點(diǎn)，也就是根節(jié)點(diǎn)，為此我們只需要把插入節(jié)點(diǎn)涂成黑色就OK了。這也就保證了性質(zhì)2：根節(jié)點(diǎn)是黑色的。
第二種情況：新節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色
為此我們舉一個(gè)例子，比如說(shuō)上面的紅黑樹中，我們插入節(jié)點(diǎn)14。來(lái)看一下會(huì)發(fā)生什么情況？
這種情況我們發(fā)現(xiàn)新插入節(jié)點(diǎn)14的父節(jié)點(diǎn)就是黑色的。現(xiàn)在為了保證紅黑樹的性質(zhì)，我們對(duì)照每個(gè)特性來(lái)檢查一遍。只要有一條不滿足，我們都需要調(diào)整。我們重新對(duì)照之后會(huì)發(fā)現(xiàn)每一條都符合。此時(shí)不需要調(diào)整。
第三種情況：新節(jié)點(diǎn)的父親節(jié)點(diǎn)為紅色
我們還是舉個(gè)例子，比如我們?cè)谧铋_始的紅黑樹基礎(chǔ)之上插入節(jié)點(diǎn)21，此時(shí)會(huì)發(fā)生什么情況呢？
此時(shí)還是老規(guī)矩，對(duì)照著紅黑樹的5個(gè)特征一個(gè)一個(gè)來(lái)看，只要是違反了一條就需要做出調(diào)整。我們來(lái)看一下：
（1）每個(gè)節(jié)點(diǎn)只有兩種顏色：紅色和黑色。這一條滿足。
（2）根節(jié)點(diǎn)是黑色的。這一條也滿足。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）都是黑色的空節(jié)點(diǎn)。這一條滿足。
（4）從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，不會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。這一條發(fā)現(xiàn)不滿足。
就是上面這一條規(guī)則沒有滿足，所以我們此時(shí)需要調(diào)整？問題來(lái)了如何調(diào)整呢？因?yàn)橹苯涌锤腹?jié)點(diǎn)沒辦法實(shí)現(xiàn)，所以還需要觀察另外的節(jié)點(diǎn)，也就是新節(jié)點(diǎn)的叔叔節(jié)點(diǎn)。根據(jù)叔叔節(jié)點(diǎn)的顏色來(lái)調(diào)整。調(diào)整的方式有兩種：變色和旋轉(zhuǎn)。
（1）叔叔節(jié)點(diǎn)是紅色：
此時(shí)插入的節(jié)點(diǎn)是21，但是叔叔節(jié)點(diǎn)是27，更好是紅色。我們直接來(lái)看調(diào)整的步驟：
第一步：把新節(jié)點(diǎn)21的父節(jié)點(diǎn)22變成黑色。
此時(shí)重新看一下是否滿足紅黑樹的五條特征了沒，一條一條發(fā)現(xiàn)，第五條沒有滿足，也就是從任何一個(gè)節(jié)點(diǎn)出發(fā)，到葉子節(jié)點(diǎn)，這條路徑上沒有相同數(shù)目的黑色節(jié)點(diǎn)。比如從25出發(fā)。這時(shí)候怎么辦呢？那就繼續(xù)調(diào)整。
第二步：把22的父節(jié)點(diǎn)25變成紅色
這時(shí)候還是老規(guī)矩，不要嫌棄麻煩，因?yàn)橹挥薪?jīng)歷了一步又一步的麻煩之后，你才能牢記那5條規(guī)則特征。我們對(duì)照之后會(huì)發(fā)現(xiàn)節(jié)點(diǎn)25和節(jié)點(diǎn)27是兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，這時(shí)候又破壞了規(guī)則4。怎么辦呢？那就繼續(xù)調(diào)整就OK了。
難道這時(shí)候還要繼續(xù)往上調(diào)整嗎？如果你這樣做就錯(cuò)了，因?yàn)椴粩嗟赝险{(diào)整最后就會(huì)把根節(jié)點(diǎn)變成了紅色，會(huì)走進(jìn)死胡同。我們往下走。
第三步：把節(jié)點(diǎn)27變成黑色
來(lái)吧，繼續(xù)重新審查那5條規(guī)則特征。很明顯節(jié)點(diǎn)17和節(jié)點(diǎn)25是兩個(gè)連續(xù)的紅色，又破壞了。是不是心太累了，調(diào)整了這么久，還是沒有保證那5條規(guī)則，感覺是不是還沒有平衡二叉樹好。如果你現(xiàn)在有這種感覺，我只能說(shuō)，希望你繼續(xù)堅(jiān)持下去，勝利就在眼前。
第四步：把節(jié)點(diǎn)17和節(jié)點(diǎn)18都變成黑色節(jié)點(diǎn)
來(lái)來(lái)來(lái)，現(xiàn)在你再對(duì)照一下那5條規(guī)則，是不是完全保證了。寫到這真的是太累了，和你讀這篇文章的感覺一樣一樣的，不過這種情況也只是插入情況中的一種。繼續(xù)往下看：
（1）叔叔節(jié)點(diǎn)是黑色：
這種情況下又分了兩種情況：
第一種情況：新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子
第二種情況：新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右孩子
按照第一遍的思路，我們對(duì)這兩種情況執(zhí)行同樣的操作，最終也能保證紅黑樹的5條特征。
到了這一步，插入操作的所有情況就講解完畢。另外關(guān)于左旋和右旋的知識(shí)我在這里不再說(shuō)明了，因?yàn)槟憧吹搅思t黑樹這個(gè)程度，相信也一定看過平衡二叉樹。左旋右旋哪幾種情況，都會(huì)有介紹到。
3、刪除節(jié)點(diǎn)
紅黑樹的刪除說(shuō)實(shí)話更加的復(fù)雜，如果你看過算法導(dǎo)論的話應(yīng)該能明白一點(diǎn)，我們?cè)谶@里也進(jìn)行一個(gè)大概的講解。
刪除大致分了三種情況，
（1）第一種情況：要?jiǎng)h除的節(jié)點(diǎn)有零個(gè)子節(jié)點(diǎn)
這種情況下最簡(jiǎn)單，也就是刪除的是根節(jié)點(diǎn)或者是葉子節(jié)點(diǎn)（這里的葉子節(jié)點(diǎn)都是指非NULL的葉子節(jié)點(diǎn)），根節(jié)點(diǎn)直接刪除即可。如果葉子節(jié)點(diǎn)是紅色的，也可以直接刪除，如果葉子節(jié)點(diǎn)是黑色的，那么就需要進(jìn)行調(diào)整，調(diào)整的步驟和插入時(shí)調(diào)整的步驟一樣。
（2）第二種情況：要?jiǎng)h除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
這時(shí)候。把子節(jié)點(diǎn)的值替換掉要?jiǎng)h除的節(jié)點(diǎn)的值。
現(xiàn)在我們的5把11替換掉之后，又回到了第一種情況。如果節(jié)點(diǎn)5是紅色的，可以直接刪除，如果節(jié)點(diǎn)5是黑色的，那么就需要進(jìn)行調(diào)整，此時(shí)的節(jié)點(diǎn)5就是葉子節(jié)點(diǎn)。調(diào)整的步驟和插入時(shí)調(diào)整的步驟一樣。
（3）第三種情況：要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
現(xiàn)在刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，同樣的我們可以執(zhí)行第二種情況的操作，
若節(jié)點(diǎn)13之前是葉子節(jié)點(diǎn)，那就和第一種情況一樣了，如果節(jié)點(diǎn)13是紅色的，可以直接刪除，如果節(jié)點(diǎn)13是黑色的，那么就需要進(jìn)行調(diào)整，此時(shí)的節(jié)點(diǎn)13就是葉子節(jié)點(diǎn)。調(diào)整的步驟和插入時(shí)調(diào)整的步驟一樣。
若節(jié)點(diǎn)13之前還有子節(jié)點(diǎn)，那就和第二種情況一樣了。那就繼續(xù)替換和判斷。
以上呢就是刪除的情況，最后一種情況是修改，這種情況是查找和插入的結(jié)合體，也就是先找到要修改的元素，修改完值之后，繼續(xù)進(jìn)行調(diào)整即可。
現(xiàn)在還有最后一個(gè)問題了，都說(shuō)紅黑樹很重要，為什么重要呢？我們來(lái)看一下使用場(chǎng)景。
四、使用場(chǎng)景
紅黑樹的應(yīng)用真的是太多了，比如說(shuō)JAVA中的HashMap和TreeMap。還有就是linux也經(jīng)常使用到。這種數(shù)據(jù)結(jié)構(gòu)在面試的時(shí)候是一個(gè)常問問題，希望大家能夠明白和理解。如何用java手撕紅黑樹，在后續(xù)文章中我會(huì)添加。如有問題還請(qǐng)批評(píng)指正。
