摘要：用這種范例表示紅黑樹是可能的，但是這會(huì)改變一些性質(zhì)并使算法復(fù)雜。插入會(huì)出現(xiàn)種情況為根節(jié)點(diǎn)，即紅黑樹的根節(jié)點(diǎn)。

說到HashMap，就一定要說到紅黑樹，紅黑樹作為一種自平衡二叉查找樹，是一種用途較廣的數(shù)據(jù)結(jié)構(gòu)，在jdk1.8中使用紅黑樹提升HashMap的性能，今天就來說一說紅黑樹。

限于篇幅，本文只對(duì)紅黑樹的基礎(chǔ)進(jìn)行說明，暫不涉及源碼部分，大部分摘抄自維基百科，這里也貼出對(duì)應(yīng)鏈接：

維基百科(中文)：https://zh.wikipedia.org/wiki...

維基百科：https://en.wikipedia.org/wiki...

筆者這里會(huì)根據(jù)維基百科的講解做些說明，方便初學(xué)者理解。

當(dāng)然，在了解紅黑樹之前，先回顧下樹這種結(jié)構(gòu)的特點(diǎn)(來自維基百科))：

在計(jì)算機(jī)科學(xué)中，樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：
每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無子節(jié)點(diǎn)；
沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；
樹里面沒有環(huán)路(cycle)
紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，紅黑樹和AVL樹一樣都對(duì)插入時(shí)間、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保。
紅黑樹的結(jié)構(gòu)復(fù)雜，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中高效：它可以在O(log n)時(shí)間內(nèi)完成查找，插入和刪除，這里的O(log n) n是樹中元素的數(shù)目。

這些描述說明了紅黑樹結(jié)構(gòu)的一大特點(diǎn)：在增刪查上即使是最壞的一種數(shù)據(jù)結(jié)構(gòu)情況，也保證了性能。

有些新手可能會(huì)想，為什么能保證？

看完整篇文章，你可能就會(huì)了解清楚，紅黑樹概念上其實(shí)也提及了，自平衡這個(gè)詞說明了每次在我們進(jìn)行增刪時(shí)，會(huì)自行調(diào)整結(jié)構(gòu)來滿足紅黑樹特性，這樣在查詢上就能保證性能。

那么，什么樣的二叉樹才是紅黑樹呢？

紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求：
1.節(jié)點(diǎn)是紅色或黑色。
2.根是黑色。
3.所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
4.每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

這里需要注意葉子節(jié)點(diǎn)的概念與一般意義上樹的葉子節(jié)點(diǎn)不同，這里紅黑樹葉子節(jié)點(diǎn)都是黑色且為NIL的。

維基百科上對(duì)于這5種性質(zhì)也做了說明：

這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。結(jié)果是這個(gè)樹大致上是平衡的。因?yàn)椴僮鞅热绮迦?、刪除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
要知道為什么這些性質(zhì)確保了這個(gè)結(jié)果，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了。最短的可能路徑都是黑色節(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。因?yàn)楦鶕?jù)性質(zhì)5所有最長(zhǎng)的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就表明了沒有路徑能多于任何其他路徑的兩倍長(zhǎng)。
在很多樹數(shù)據(jù)結(jié)構(gòu)的表示中，一個(gè)節(jié)點(diǎn)有可能只有一個(gè)子節(jié)點(diǎn)，而葉子節(jié)點(diǎn)包含數(shù)據(jù)。用這種范例表示紅黑樹是可能的，但是這會(huì)改變一些性質(zhì)并使算法復(fù)雜。為此，本文中我們使用"nil葉子"或"空（null）葉子"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示。這些節(jié)點(diǎn)在繪圖中經(jīng)常被省略，導(dǎo)致了這些樹好像同上述原則相矛盾，而實(shí)際上不是這樣。與此有關(guān)的結(jié)論是所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，盡管其中的一個(gè)或兩個(gè)可能是空葉子。

從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)這個(gè)在文中也解釋了原因，因?yàn)樾再|(zhì)4需要被滿足，這樣限制了樹的高度差，使得查找性能提升。

可以多想下，普通的二叉樹，最壞情況如下：

這種情況下使得樹形結(jié)構(gòu)毫無意義，而紅黑樹（其存在的5種特性保證）則不會(huì)出現(xiàn)這種情況。

具體請(qǐng)參考維基百科的證明：

之前的定義我也說了，為了保證紅黑樹的特性，需要在插入刪除時(shí)對(duì)樹進(jìn)行調(diào)整來保證自平衡。那么如何來調(diào)整呢？

這里就說明下紅黑樹平衡的兩種操作：變色和旋轉(zhuǎn)。

變色這個(gè)操作很好理解了吧，在某些情況下，為了保證自平衡，需要改變顏色，來滿足紅黑樹的特性

可以參考維基百科：https://en.wikipedia.org/wiki...

旋轉(zhuǎn)操作相對(duì)要復(fù)雜些，旋轉(zhuǎn)分為左旋和右旋。

左旋：

如下圖所示，逆時(shí)針旋轉(zhuǎn)旋轉(zhuǎn)M,N兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)M變?yōu)镹的子節(jié)點(diǎn)，N變?yōu)楦腹?jié)點(diǎn)，交換之后對(duì)于B節(jié)點(diǎn)就需要進(jìn)行調(diào)整，B節(jié)點(diǎn)變?yōu)镸的右子節(jié)點(diǎn)

右旋：

如下圖所示，順時(shí)針旋轉(zhuǎn)旋轉(zhuǎn)M,N兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)M變?yōu)镹的子節(jié)點(diǎn)，N變?yōu)楦腹?jié)點(diǎn)，交換之后對(duì)于B節(jié)點(diǎn)就需要進(jìn)行調(diào)整，B節(jié)點(diǎn)變?yōu)镸的左子節(jié)點(diǎn)

這里貼出維基上的gif圖，方便各位理解：

無論是變色還是旋轉(zhuǎn)，最終調(diào)整的結(jié)果都是要在插入或者刪除之后滿足紅黑樹的5個(gè)特性。

首先需要明白的是新增加的節(jié)點(diǎn)默認(rèn)標(biāo)記為紅色，至于原因維基上說明了：

如果設(shè)為黑色，就會(huì)導(dǎo)致根到葉子的路徑上有一條路上，多一個(gè)額外的黑節(jié)點(diǎn)，這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后，可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突，那么可以通過顏色調(diào)換（color flips）和樹旋轉(zhuǎn)來調(diào)整。

在說我個(gè)人理解之前，需要理解局部紅黑子樹含義，其實(shí)相當(dāng)于把紅黑樹進(jìn)行切割，一個(gè)大的紅黑樹切割成多個(gè)局部，每次我們調(diào)整都是以一個(gè)局部來完成，局部調(diào)整完之后，整個(gè)樹如果還是不平衡，則繼續(xù)向上回溯調(diào)整，維基上也是這樣做的。下圖中的框算是一個(gè)局部紅黑子樹。

如果添加的節(jié)點(diǎn)默認(rèn)標(biāo)記為黑色，那么這條路徑上比其他路徑多了一個(gè)黑色節(jié)點(diǎn)，不滿足性質(zhì)5，需要調(diào)整，可能會(huì)影響到其他已經(jīng)平衡的局部紅黑子樹，牽一發(fā)而動(dòng)全身，代價(jià)過高，而默認(rèn)為紅色，首先其他已經(jīng)平衡的局部紅黑子樹還未受到影響，在未調(diào)整之前，未平衡的這個(gè)局部紅黑子樹中黑色路徑和平衡之前是相同的，這樣應(yīng)該是要更方便調(diào)整。

將要插入的節(jié)點(diǎn)標(biāo)為N，N的父節(jié)點(diǎn)標(biāo)為P，N的祖父節(jié)點(diǎn)標(biāo)為G，N的叔父節(jié)點(diǎn)標(biāo)為U

這里也能看出來都是以一個(gè)局部來調(diào)整，那么考慮下插入會(huì)出現(xiàn)哪些情況？在考慮的時(shí)候一定要注意，在未插入新節(jié)點(diǎn)和插入新節(jié)點(diǎn)之后變化的地方和需要保持不變的地方。尤其需要注意插入前已經(jīng)平衡了，滿足紅黑樹的5種特性，不是隨便什么狀態(tài)都會(huì)出現(xiàn)，切記。

插入會(huì)出現(xiàn)4種情況：
1.N為根節(jié)點(diǎn)，即紅黑樹的根節(jié)點(diǎn)。
2.N的父節(jié)點(diǎn)（P）是黑色的。
3.N的父節(jié)點(diǎn)（P）是紅色的（因此它不能是樹的根）而N的叔父節(jié)點(diǎn)（U）是紅色的。
4.N的父節(jié)點(diǎn)（P）是紅色的（因此它不能是樹的根）而N的叔父節(jié)點(diǎn)（U）是黑色的。

思考下，上面包含的情況可以從插入節(jié)點(diǎn)N為紅色開始進(jìn)行考慮，判斷父節(jié)點(diǎn)顏色，根據(jù)情況進(jìn)行調(diào)整，先進(jìn)行變色操作，變色保證不了平衡則需要旋轉(zhuǎn)來平衡，而3和4的情況，有人可能會(huì)想為什么要判斷U側(cè)的子樹部分？我們可以想一下，在P為紅色，N為紅色時(shí)，在N這一側(cè)的子樹部分，如何調(diào)整也不會(huì)達(dá)到平衡，此時(shí)只能向上回溯尋求幫助，涉及到了祖父節(jié)點(diǎn)G，那么此時(shí)就會(huì)影響到G的子樹U部分，所以需要考慮U的顏色然后繼續(xù)調(diào)整。

插入時(shí)按順序判斷上述4種情況，注意先對(duì)局部紅黑子樹（從N到G,G相當(dāng)于局部根節(jié)點(diǎn)）進(jìn)行平衡，滿足屬性4和5，最后判斷G節(jié)點(diǎn)是否為黑色，非黑色以G為新增節(jié)點(diǎn)再次遞歸順序判斷（相當(dāng)于向上回溯），這里有一個(gè)要注意的地方，局部根節(jié)點(diǎn)G可以為紅色，除非G是整個(gè)樹的根節(jié)點(diǎn)，這時(shí)直接修改顏色即可完成平衡（相當(dāng)于整個(gè)樹黑色路徑都加一）：

CASE-1：N為根節(jié)點(diǎn)，修改成黑色，同樣滿足紅黑樹的5個(gè)屬性，僅僅黑色路徑增加了1。不滿足當(dāng)前情況，繼續(xù)CASE-2情況判斷處理。

CASE-2：P為黑色，添加節(jié)點(diǎn)N為紅色，N下添加兩個(gè)黑色葉子節(jié)點(diǎn)（NIL），屬性4和5沒有破壞，不需要調(diào)整。不滿足當(dāng)前情況，繼續(xù)CASE-3情況判斷處理。

CASE-3：P(父)和U（叔）為紅色，以N為P的左子節(jié)點(diǎn)為例（右子節(jié)點(diǎn)操作類似），添加節(jié)點(diǎn)N為紅色，先進(jìn)行變色操作，P,U變?yōu)楹谏?，這樣不滿足屬性5，路徑上黑色節(jié)點(diǎn)多了1，將G(祖父)變?yōu)榧t色，到這里可以看出添加節(jié)點(diǎn)之后從G到G下的葉子節(jié)點(diǎn)路徑和未添加N節(jié)點(diǎn)之前的路徑黑色節(jié)點(diǎn)數(shù)是一致的，在這部分局部區(qū)域已經(jīng)滿足屬性4和5，不需要進(jìn)行調(diào)整了，但是G可能違反了屬性2（根節(jié)點(diǎn)為黑色），或?qū)傩?（不能有連續(xù)的兩個(gè)紅色節(jié)點(diǎn)），回到CASE-1再次順序判斷處理，這里注意下，重新判斷是以G節(jié)點(diǎn)為新局部紅黑子樹的新增節(jié)點(diǎn)N,G節(jié)點(diǎn)的子節(jié)點(diǎn)可以當(dāng)做葉子節(jié)點(diǎn)，再重新重頭判斷這個(gè)新的局部子樹（相當(dāng)于向上回溯，直到滿足條件，或者根節(jié)點(diǎn)，滿足CASE-1）。不滿足當(dāng)前情況，繼續(xù)CASE-4情況判斷處理。

CASE-4：P（父）為紅色,U（叔）為黑色，以P為其父節(jié)點(diǎn)左子節(jié)點(diǎn)為例，對(duì)稱情況操作類似，變色也滿足不了G到葉子節(jié)點(diǎn)屬性4和屬性5，這里就需要考慮另一種處理-旋轉(zhuǎn)。

這里會(huì)出現(xiàn)兩種狀態(tài)（對(duì)稱的情況自行參照處理）：

CASE-4-1:新添加節(jié)點(diǎn)N為P（父）節(jié)點(diǎn)右子樹，相當(dāng)于G樹的“內(nèi)部”，參考下圖，在這種情況下，執(zhí)行的P上的左旋轉(zhuǎn)。轉(zhuǎn)換成右側(cè)圖，到此還是違反屬性4，但是不違反屬性5，再繼續(xù)CASE-4-2情況判斷處理。不滿足當(dāng)前情況，也繼續(xù)CASE-4-2情況判斷處理。

CASE-4-2:新添加節(jié)點(diǎn)N為P（父）節(jié)點(diǎn)左子樹，相當(dāng)于G樹的“外部”，和第一種狀態(tài)調(diào)整完一致，參考下圖，在這種情況下，執(zhí)行G上的右旋轉(zhuǎn)，P和G的顏色切換，即可滿足紅黑樹的屬性，變?yōu)橛覀?cè)圖。

從上面分析過程可以看出，局部插入最多兩次旋轉(zhuǎn)，更多的是變色操作，少量的旋轉(zhuǎn)操作可以鎖住某些節(jié)點(diǎn)（變色操作不影響），大部分節(jié)點(diǎn)是可以查詢且修改的，這也是大部分底層實(shí)現(xiàn)使用紅黑樹的原因吧。

刪除操作比較復(fù)雜，下一章再進(jìn)行說明，本章主要從基礎(chǔ)說明紅黑樹的特性以及相關(guān)的平衡操作以及插入新節(jié)點(diǎn)時(shí)不同情況的調(diào)整規(guī)則，希望對(duì)讀者有所幫助，下面通過流程圖來幫助各位更好的理解和實(shí)現(xiàn)紅黑樹插入情況下的自平衡處理。

下一章我就更為復(fù)雜的刪除操作進(jìn)行講解，謝謝各位閱讀，如有錯(cuò)誤，歡迎留言指正，我將盡快驗(yàn)證修改。

參考資料：

https://zh.wikipedia.org/wiki...

https://en.wikipedia.org/wiki...