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

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

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

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

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

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

當然，在了解紅黑樹之前，先回顧下樹這種結構的特點(來自維基百科))：

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

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

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

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

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

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

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

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

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

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

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

這種情況下使得樹形結構毫無意義，而紅黑樹（其存在的5種特性保證）則不會出現這種情況。

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

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

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

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

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

旋轉操作相對要復雜些，旋轉分為左旋和右旋。

左旋：

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

右旋：

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

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

無論是變色還是旋轉，最終調整的結果都是要在插入或者刪除之后滿足紅黑樹的5個特性。

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

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

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

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

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

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

插入會出現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為紅色開始進行考慮，判斷父節(jié)點顏色，根據情況進行調整，先進行變色操作，變色保證不了平衡則需要旋轉來平衡，而3和4的情況，有人可能會想為什么要判斷U側的子樹部分？我們可以想一下，在P為紅色，N為紅色時，在N這一側的子樹部分，如何調整也不會達到平衡，此時只能向上回溯尋求幫助，涉及到了祖父節(jié)點G，那么此時就會影響到G的子樹U部分，所以需要考慮U的顏色然后繼續(xù)調整。

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

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

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

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

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

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

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

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

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

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

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

參考資料：

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

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