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

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

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

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

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

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

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

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

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

有些新手可能會想，為什么能保證？

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

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

紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求：
1.節(jié)點是紅色或黑色。
2.根是黑色。
3.所有葉子都是黑色（葉子是NIL節(jié)點）。
4.每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）
5.從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

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

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

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

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

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

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

具體請參考維基百科的證明：

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

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

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

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

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

左旋：

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

右旋：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考資料：

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

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