上一篇：Java集合-ConcurrentHashMap工作原理和實(shí)現(xiàn)JDK8

本文學(xué)習(xí)知識(shí)點(diǎn)

1、二叉查找樹(shù)，以及二叉樹(shù)查找?guī)?lái)的問(wèn)題。
2、平衡二叉樹(shù)及好處。
3、紅黑樹(shù)的定義及構(gòu)造。
4、ConcurrentHashMap中紅黑樹(shù)的構(gòu)造。

在正式分析紅黑樹(shù)之前，有必要了解紅黑樹(shù)的發(fā)展過(guò)程，請(qǐng)讀者耐心閱讀。

二叉查找樹(shù)

紅黑樹(shù)的起源得從二叉查找樹(shù)（二叉排序樹(shù)）說(shuō)起。先來(lái)看二叉查找樹(shù)的定義：

1、要么為一顆空樹(shù)，要么就是一顆具有如下特性的二叉樹(shù)。
2、左子節(jié)點(diǎn)的值必須小于等于父節(jié)點(diǎn)的值。
3、右子節(jié)點(diǎn)的值必須大于等于父節(jié)點(diǎn)的值。

每個(gè)節(jié)點(diǎn)都符合這個(gè)特性，所以易于查找，如下圖：

二叉查找樹(shù)-平衡

但二叉查找樹(shù)會(huì)出現(xiàn)不平衡的情況，即左子樹(shù)和右子樹(shù)的深度相差很大，如果一顆二叉查找樹(shù)，只有右子樹(shù)，就演變成一個(gè)鏈表了，查找效率就變的很差，如下圖：

不平衡的二叉查找樹(shù)

對(duì)于查找而言，如果一棵二叉樹(shù)的高度是N，那么最多可以在N步內(nèi)完成查找。也就是說(shuō)，樹(shù)的高度要盡可能矮查找才會(huì)更快?？紤]到查找的平均情況，葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的距離不能差別太大，所以我們都希望二叉查找樹(shù)是一顆矮胖樹(shù)，而不是一條鏈路的二叉樹(shù)。為了優(yōu)化因深度的不穩(wěn)定性對(duì)查找效率的影響，于是就出現(xiàn)了平衡二叉樹(shù)。

時(shí)間復(fù)雜度
1.在一棵二叉查找樹(shù)上，執(zhí)行查找、插入、刪除等操作，的時(shí)間復(fù)雜度為O（lgn）。因?yàn)椋豢糜蒼個(gè)節(jié)點(diǎn)，隨機(jī)構(gòu)造的二叉查找樹(shù)的高度為lgn，所以順理成章，一般操作的執(zhí)行時(shí)間為O（lgn）。至于n個(gè)節(jié)點(diǎn)的二叉樹(shù)高度為lgn的證明，可參考算法導(dǎo)論 第12章 二叉查找樹(shù) 第12.4節(jié)。
2.但若是一棵具有n個(gè)節(jié)點(diǎn)的線性鏈，則此些操作最壞情況運(yùn)行時(shí)間為O（n）。

平衡二叉樹(shù)

定義：

1、要么為一顆空樹(shù)，要么就是一顆具有如下特性的二叉樹(shù)。
2、它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)。
3、它的左子樹(shù)和右子樹(shù)的深度差的絕對(duì)值不超過(guò)1。

兩顆平衡的二叉樹(shù)

在構(gòu)造平衡二插樹(shù)時(shí)，失衡調(diào)整主要是通過(guò)旋轉(zhuǎn)最小失衡子樹(shù)來(lái)實(shí)現(xiàn)的。有必要弄清楚幾個(gè)概念：

1、平衡因子：左子樹(shù)的高度減去右子樹(shù)的高度。由平衡二叉樹(shù)的定義可知，平衡因子的取值只可能為0,1,-1.分別對(duì)應(yīng)著左右子樹(shù)等高，左子樹(shù)比較高，右子樹(shù)比較高。
2、最小失衡子樹(shù)：在新插入的節(jié)點(diǎn)向上查找，以第一個(gè)平衡因子的絕對(duì)值超過(guò)1的節(jié)點(diǎn)為根的子樹(shù)稱(chēng)為最小失衡子樹(shù)。也就是說(shuō)，一棵失衡的樹(shù)，是有可能有多棵子樹(shù)同時(shí)失衡的。而這個(gè)時(shí)候，我們只要調(diào)整最小的不平衡子樹(shù)，就能夠?qū)⒉黄胶獾臉?shù)調(diào)整為平衡的樹(shù)。

在圖1中，例如插入節(jié)點(diǎn)5，那么2節(jié)點(diǎn)（左子樹(shù)樹(shù)高-右子樹(shù)樹(shù)高）的的平衡因子為-2。同理，3節(jié)點(diǎn)的平衡因子也為-2。此時(shí)同時(shí)存在了兩棵不平衡子樹(shù)，但按節(jié)點(diǎn)5往上查找，4節(jié)點(diǎn)的平衡因子為-1，3節(jié)點(diǎn)的平衡因子為-2，因此3節(jié)點(diǎn)是第一個(gè)最小的不平衡子樹(shù)。所以我們將以3節(jié)點(diǎn)為中心，將最小不平衡樹(shù)向左旋轉(zhuǎn)，即可得到平衡二叉樹(shù)，如圖2。

調(diào)整過(guò)程

平衡二叉樹(shù)失衡的全部調(diào)整過(guò)程和代碼就不詳述了，重點(diǎn)在于描述紅黑樹(shù)的調(diào)整過(guò)程。

紅黑樹(shù)

紅黑樹(shù)是一種特殊的二叉查找樹(shù)，在滿足二叉查找樹(shù)的特性外，在每個(gè)節(jié)點(diǎn)上增加了存儲(chǔ)顏色的標(biāo)識(shí)，顏色要么是紅色，要么是黑色，定義：

1、每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
2、根節(jié)點(diǎn)是黑色。
3、所有葉子節(jié)點(diǎn)是黑色，即空節(jié)點(diǎn)（NIL）。
4、如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)必須是黑色的，也就是父子節(jié)點(diǎn)不能都為紅色。
5、從一個(gè)節(jié)點(diǎn)到其所有葉子節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

注意：
(1) 特性3中的葉子節(jié)點(diǎn)，是只為空(NIL或null)的節(jié)點(diǎn)。
(2) 特性5，確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍。因而，紅黑樹(shù)是相對(duì)是接近平衡的二叉樹(shù)。因此在最壞情況下，紅黑樹(shù)能保證時(shí)間復(fù)雜度為O( lgn )

紅黑樹(shù)示意圖

樹(shù)的旋轉(zhuǎn)知識(shí)

當(dāng)我們對(duì)紅黑樹(shù)進(jìn)行插入和刪除操作時(shí)，對(duì)樹(shù)做了結(jié)構(gòu)性修改，那么可能會(huì)違背紅黑樹(shù)的5條性質(zhì)。

為了保持紅黑樹(shù)的性質(zhì)，我們可以通過(guò)對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)，即修改樹(shù)中某些節(jié)點(diǎn)的顏色及父子節(jié)點(diǎn)的指針結(jié)構(gòu)，以維持紅黑樹(shù)的性質(zhì)。
樹(shù)的旋轉(zhuǎn)，分為左旋和右旋，以下借助圖來(lái)做形象的解釋和介紹。

1、左旋

左旋

左旋實(shí)例

2、右旋

右旋和左旋類(lèi)似，只看實(shí)例，理解一個(gè)就可以了：

右旋實(shí)例

3、紅黑樹(shù)的插入

向一棵含有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)插入一個(gè)新節(jié)點(diǎn)的操作可以在O（lgn）時(shí)間內(nèi)完成。
在繼續(xù)插入操作分析前，再來(lái)復(fù)習(xí)下紅黑樹(shù)的特性：

1、每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
2、根節(jié)點(diǎn)是黑色。
3、所有葉子節(jié)點(diǎn)是黑色，即空節(jié)點(diǎn)（NIL）。
4、如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)必須是黑色的，也就是父子節(jié)點(diǎn)不能都為紅色。
5、從一個(gè)節(jié)點(diǎn)到其所有葉子節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)

規(guī)則約定
（1）在紅黑樹(shù)中插入節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)的初始顏色都是紅色。因?yàn)檫@樣可以在插入過(guò)程中盡量避免對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行調(diào)整（參考第5點(diǎn)性質(zhì)）。
（2）初始插入按照二叉查找樹(shù)的性質(zhì)插入，即找到合適大小的節(jié)點(diǎn)，在其左邊或右邊插入子節(jié)點(diǎn)。

我們插入一個(gè)節(jié)點(diǎn)后，可能會(huì)使原樹(shù)的哪些性質(zhì)改變呢？
（1）由于是以二叉查找樹(shù)的性質(zhì)插入，因此節(jié)點(diǎn)的查找性質(zhì)不會(huì)破壞。
（2）如果插入空樹(shù)中，成為根節(jié)點(diǎn)，則性質(zhì)2會(huì)被破壞，需要重新涂色。
（3）如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，則性質(zhì)4會(huì)被破壞，需要以插入的當(dāng)前節(jié)點(diǎn)為中心進(jìn)行旋轉(zhuǎn)或重新涂色來(lái)恢復(fù)紅黑樹(shù)的性質(zhì)。執(zhí)行旋轉(zhuǎn)或重新涂色后有可能紅黑樹(shù)仍然不滿足性質(zhì)，則需要將當(dāng)前節(jié)點(diǎn)變換回溯到其父節(jié)點(diǎn)或祖父節(jié)點(diǎn)，以父節(jié)點(diǎn)或祖父節(jié)點(diǎn)為中心繼續(xù)旋轉(zhuǎn)或重新涂色，如此循環(huán)到根節(jié)點(diǎn)直到滿足紅黑樹(shù)的性質(zhì)。

恢復(fù)紅黑樹(shù)性質(zhì)的策略
根據(jù)上面說(shuō)到的性質(zhì)改變，對(duì)應(yīng)的恢復(fù)策略其實(shí)就簡(jiǎn)單很多。
（1）把出現(xiàn)違背紅黑樹(shù)性質(zhì)的結(jié)點(diǎn)向上移（通過(guò)旋轉(zhuǎn)操作或變換當(dāng)前節(jié)點(diǎn)到父節(jié)點(diǎn)或祖父節(jié)點(diǎn)后再旋轉(zhuǎn)達(dá)到向上移動(dòng)的目的），如果能移到根結(jié)點(diǎn)，那么很容易就能通過(guò)直接修改根結(jié)點(diǎn)的顏色，或旋轉(zhuǎn)根節(jié)點(diǎn)來(lái)恢復(fù)紅黑樹(shù)的性質(zhì)。
（2）旋轉(zhuǎn)或涂色處理可分5種情況進(jìn)行處理。

情況1：空樹(shù)中插入根節(jié)點(diǎn)。
情況2：插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色。
情況3：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)（祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)）也是紅色。
情況4：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是右子節(jié)點(diǎn)。
情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)。

情況1：空樹(shù)中插入根節(jié)點(diǎn)
違反：性質(zhì)2
恢復(fù)策略：初始插入的節(jié)點(diǎn)均為紅色，因此簡(jiǎn)單將紅色重涂為黑色即可。

情況2：插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色
違反：插入的紅色節(jié)點(diǎn)，未違反任何性質(zhì)。
恢復(fù)策略：什么也不做，無(wú)需調(diào)整。

情況3：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)也是紅色
違反：性質(zhì)4
此時(shí)祖父節(jié)點(diǎn)一定存在，否則插入前就已不是紅黑樹(shù)。
與此同時(shí)，又分為父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左子還是右子，由于對(duì)稱(chēng)性，我們只要解開(kāi)一個(gè)方向就可以了。在此，我們只考慮父節(jié)點(diǎn)為祖父左子的情況。
同時(shí)，還可以分為當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子還是右子，但是處理方式是一樣的。我們將此歸為同一類(lèi)。
恢復(fù)策略：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父結(jié)點(diǎn)涂紅，把當(dāng)前結(jié)點(diǎn)指向祖父節(jié)點(diǎn)，以祖父節(jié)點(diǎn)為中心重新開(kāi)始新一輪的旋轉(zhuǎn)或涂色。
以插入節(jié)點(diǎn)4為例，按照恢復(fù)策略，做如下圖的涂色：

情況3——涂色

情況4：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是右子節(jié)點(diǎn)
違反：性質(zhì)4
恢復(fù)策略：以當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，以新的當(dāng)前節(jié)點(diǎn)為支撐，進(jìn)行左旋操作。旋轉(zhuǎn)操作后再按新的情況進(jìn)行旋轉(zhuǎn)或涂色。

情況4——左旋

這里作的操作為：當(dāng)前節(jié)點(diǎn)由原來(lái)的7變換為其父節(jié)點(diǎn)2，以新的當(dāng)前節(jié)點(diǎn)2，作左旋操作，如上圖。操作完成后，發(fā)現(xiàn)父子節(jié)點(diǎn)仍都是紅色，繼續(xù)進(jìn)行旋轉(zhuǎn)或涂色。這里適用于情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)來(lái)進(jìn)行再次調(diào)整，請(qǐng)看下面的情況5如何進(jìn)行調(diào)整。

情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)
違反：性質(zhì)4
恢復(fù)策略：父節(jié)點(diǎn)改變?yōu)楹谏娓腹?jié)點(diǎn)改變?yōu)榧t色，然后再以祖父節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)，做右旋操作。

情況5——涂色和旋轉(zhuǎn)

此時(shí)，樹(shù)已經(jīng)滿足紅黑樹(shù)的性質(zhì)，如果仍不滿足，則仍按照情況1——情況5的方式進(jìn)行旋轉(zhuǎn)和重新涂色。

紅黑樹(shù)的刪除操作就不介紹了，涂色和旋轉(zhuǎn)和這個(gè)類(lèi)似。如何刪除節(jié)點(diǎn)請(qǐng)看二叉查找樹(shù)的刪除即可。

為什么不用平衡二叉樹(shù)作為底層實(shí)現(xiàn)

那是因?yàn)槠胶舛媸歉叨绕胶獾臉?shù), 而每一次對(duì)樹(shù)的修改, 都要 rebalance, 這里的開(kāi)銷(xiāo)會(huì)比紅黑樹(shù)大. 如果插入一個(gè)node引起了樹(shù)的不平衡，平衡二叉樹(shù)和紅黑樹(shù)都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)；但是在刪除node引起樹(shù)的不平衡時(shí)，最壞情況下，平衡二叉樹(shù)需要維護(hù)從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉(zhuǎn)的量級(jí)O(logN)，而紅黑樹(shù)最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度, 所以平衡二叉樹(shù)需要rebalance的頻率會(huì)更高，因此紅黑樹(shù)在大量插入和刪除的場(chǎng)景下效率更高

ConcurrentHashMap二叉樹(shù)的構(gòu)造過(guò)程

前面講了一大堆，終于來(lái)到ConcurrentHashMap二叉樹(shù)的構(gòu)造過(guò)程了，構(gòu)造過(guò)程和前面講的一樣。我們先分析源碼，然后以一個(gè)實(shí)際的例子進(jìn)行分析。

在Java集合-ConcurrentHashMap工作原理和實(shí)現(xiàn)JDK8這篇文章中提到，鏈表的長(zhǎng)度超過(guò)8時(shí)，會(huì)調(diào)用treeifyBin(tab , i)方法將鏈表結(jié)構(gòu)轉(zhuǎn)換為紅黑樹(shù)。
先復(fù)習(xí)下ConcurrentHashMap中節(jié)點(diǎn)的類(lèi)型和繼承關(guān)系：

ConcurrentHashMap幾個(gè)核心內(nèi)部類(lèi)關(guān)系圖

所以理解了上面的紅黑樹(shù)其實(shí)也是一個(gè)鏈表，再來(lái)看源碼就不難理解：

/**
 * Replaces all linked nodes in bin at given index unless table is
 * too small, in which case resizes instead.
 * @param tab table表
 * @param index 轉(zhuǎn)換為紅黑樹(shù)的鏈表在table中的索引下標(biāo)
 */
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // 一開(kāi)始并非直接轉(zhuǎn)換為紅黑樹(shù)，而是通過(guò)擴(kuò)容table到2倍的方式，
        // 只有table的長(zhǎng)度大于64之后，才會(huì)將超過(guò)8個(gè)元素的鏈表轉(zhuǎn)紅黑樹(shù)
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        // b.hash >= 0即為普通的Node鏈表節(jié)點(diǎn)
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {// 鎖住鏈表頭
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    // 將原Node鏈表轉(zhuǎn)換成以TreeBin節(jié)點(diǎn)為元素的鏈表
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // TreeBin的構(gòu)造方法構(gòu)造樹(shù)，根據(jù)TreeBin鏈表構(gòu)造
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

從源碼可以看出，一開(kāi)始并非直接轉(zhuǎn)換為紅黑樹(shù)，而是通過(guò)擴(kuò)容table到2倍的方式，只有table的長(zhǎng)度大于64之后，才會(huì)將超過(guò)8個(gè)元素的鏈表轉(zhuǎn)紅黑樹(shù)。紅黑樹(shù)的構(gòu)造過(guò)程是在TreeBin的構(gòu)造方法中完成的。

紅黑樹(shù)的構(gòu)造過(guò)程

假設(shè)待構(gòu)造的紅黑樹(shù)TreeNode鏈表如下，節(jié)點(diǎn)中的數(shù)值代表元素的hash值：

源碼如下：

/**
 * Creates bin with initial set of nodes headed by b.
 */
TreeBin(TreeNode<K,V> b) {
    super(TREEBIN, null, null, null);
    this.first = b;
    TreeNode<K,V> r = null;
    // 遍歷TreeNode鏈表進(jìn)行構(gòu)造
    for (TreeNode<K,V> x = b, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (r == null) {
            x.parent = null;
            x.red = false;
            r = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = r;;) {
                // 執(zhí)行插入，dir為比對(duì)節(jié)點(diǎn)hash值大小的標(biāo)識(shí),決定插入時(shí)在左還是在右
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                    TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 插入后，執(zhí)行恢復(fù)操作：重新涂色或旋轉(zhuǎn)
                    r = balanceInsertion(r, x);
                    break;
                }
            }
        }
    }
    this.root = r;
    assert checkInvariants(root);
}

源碼中，balanceInsertion方法為恢復(fù)操作。所以根據(jù)上述源碼和紅黑樹(shù)的恢復(fù)策略，依次遍歷鏈表節(jié)點(diǎn)插入到紅黑樹(shù)中，我們構(gòu)造如下：

（1）節(jié)點(diǎn)80。
第一個(gè)節(jié)點(diǎn)80，插入到空樹(shù)中，設(shè)置為根節(jié)點(diǎn)，并為黑色：

鏈表中紅色框節(jié)點(diǎn)表示已經(jīng)完成插入紅黑樹(shù)

（2）節(jié)點(diǎn)60
節(jié)點(diǎn)60按二叉樹(shù)插入后，未違反任何紅黑樹(shù)的性質(zhì)，不做任何動(dòng)作。

紅黑樹(shù)中虛線框?yàn)楫?dāng)前節(jié)點(diǎn)

（3）節(jié)點(diǎn)50
節(jié)點(diǎn)50插入后，違反了性質(zhì)4，按照情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)進(jìn)行恢復(fù)。

節(jié)點(diǎn)50違反紅黑樹(shù)性質(zhì)4

先涂色后恢復(fù)

（4）節(jié)點(diǎn)70
節(jié)點(diǎn)70插入后，違反紅黑樹(shù)性質(zhì)5，按照情況3：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)也是紅色進(jìn)行調(diào)整。

節(jié)點(diǎn)70違反紅黑樹(shù)性質(zhì)4

調(diào)整如下，需要經(jīng)過(guò)兩次涂色調(diào)整，將當(dāng)前節(jié)點(diǎn)70的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)改為黑色，祖父節(jié)點(diǎn)改為紅色。由于祖父節(jié)點(diǎn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)只能為黑色，因此在此將根節(jié)點(diǎn)改為黑色，調(diào)整完成。

涂色和再涂色

節(jié)點(diǎn)20插入后未違反任何特性，無(wú)需調(diào)整

（6）節(jié)點(diǎn)65
節(jié)點(diǎn)65插入后違反性質(zhì)4，按照情況5：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)進(jìn)行恢復(fù)。

節(jié)點(diǎn)65插入后違反性質(zhì)4

恢復(fù)調(diào)整如下，需要經(jīng)過(guò)兩個(gè)步驟，當(dāng)前節(jié)點(diǎn)65的父節(jié)點(diǎn)改為黑色，祖父節(jié)點(diǎn)改為紅色，然后將祖父節(jié)點(diǎn)設(shè)為最新的當(dāng)前節(jié)點(diǎn)。涂色后的新樹(shù)違反了性質(zhì)5，因此還要以最新的當(dāng)前節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋操作：

涂色和右旋

插入節(jié)點(diǎn)40后，違反紅黑樹(shù)性質(zhì)4:父子節(jié)點(diǎn)不能都為紅色

根據(jù)前文的調(diào)整策略，此處當(dāng)前節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)NIL為黑色，且當(dāng)前節(jié)點(diǎn)為右子節(jié)點(diǎn)，按情況4進(jìn)行調(diào)整恢復(fù)：
步驟一：以當(dāng)前節(jié)點(diǎn)40的父節(jié)點(diǎn)20為新的當(dāng)前節(jié)點(diǎn)（見(jiàn)下圖1）；
步驟二：以圖1中新的當(dāng)前節(jié)點(diǎn)20為支點(diǎn)，左旋（見(jiàn)下圖2）；

旋轉(zhuǎn)完成后，發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)20和父節(jié)點(diǎn)40都為紅色，仍然違反了紅黑樹(shù)的性質(zhì)4，需要繼續(xù)回溯當(dāng)前節(jié)點(diǎn)再次旋轉(zhuǎn)或涂色。此時(shí)，當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)，按情況5進(jìn)行調(diào)整恢復(fù)：
步驟一：將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)40重涂為黑色，祖父節(jié)點(diǎn)50重涂為紅色（見(jiàn)下圖3）；得到的紅黑樹(shù)發(fā)現(xiàn)不滿足紅黑樹(shù)的性質(zhì)5：從一個(gè)節(jié)點(diǎn)到其所有葉子節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)，繼續(xù)執(zhí)行步驟二的調(diào)整。
步驟二：以當(dāng)前節(jié)點(diǎn)20的祖父節(jié)點(diǎn)50為新的當(dāng)前節(jié)點(diǎn)，進(jìn)行右旋（見(jiàn)下圖5）；

到此，成功將節(jié)點(diǎn)40插入紅黑樹(shù)，滿足所有紅黑樹(shù)的性質(zhì)。

（8）節(jié)點(diǎn)10
節(jié)點(diǎn)10插入后違反性質(zhì)4，按照情況3：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)（祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)）也是紅色進(jìn)行恢復(fù)。

節(jié)點(diǎn)10插入后違反紅黑樹(shù)的性質(zhì)4

恢復(fù)調(diào)整如下，當(dāng)前節(jié)點(diǎn)10的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)改為黑色，祖父節(jié)點(diǎn)40重涂為紅色，調(diào)整就完成了：

父節(jié)點(diǎn)、叔叔節(jié)點(diǎn)、祖父節(jié)點(diǎn)重新涂色

至此，紅黑樹(shù)的構(gòu)造完成。

推薦閱讀

• 如何快速成長(zhǎng)為技術(shù)大牛？
• Java集合-ConcurrentHashMap工作原理和實(shí)現(xiàn)JDK8
• 分布式全局唯一ID生成策略