上一篇：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ù)稱為最小失衡子樹(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溉知、右旋

右旋和左旋類似，只看實(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ì)稱性胚吁，我們只要解開(kāi)一個(gè)方向就可以了牙躺。在此，我們只考慮父節(jié)點(diǎn)為祖父左子的情況腕扶。
同時(shí)孽拷，還可以分為當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子還是右子，但是處理方式是一樣的蕉毯。我們將此歸為同一類乓搬。
恢復(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è)類似昙沦。如何刪除節(jié)點(diǎn)請(qǐng)看二叉查找樹(shù)的刪除即可琢唾。

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

那是因?yàn)槠胶舛媸歉叨绕胶獾臉?shù), 而每一次對(duì)樹(shù)的修改, 都要 rebalance, 這里的開(kāi)銷會(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)的類型和繼承關(guān)系：

ConcurrentHashMap幾個(gè)核心內(nè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生成策略