17張圖帶你解析紅黑樹(shù)的原理！保證你能看懂！-創(chuàng)新互聯(lián)

二叉查找樹(shù)

創(chuàng)新互聯(lián)專注于網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站制作、網(wǎng)站開(kāi)發(fā)。公司秉持“客戶至上,用心服務(wù)”的宗旨,從客戶的利益和觀點(diǎn)出發(fā),讓客戶在網(wǎng)絡(luò)營(yíng)銷(xiāo)中找到自己的駐足之地。尊重和關(guān)懷每一位客戶，用嚴(yán)謹(jǐn)?shù)膽B(tài)度對(duì)待客戶，用專業(yè)的服務(wù)創(chuàng)造價(jià)值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

由于紅黑樹(shù)本質(zhì)上就是一棵二叉查找樹(shù)，所以在了解紅黑樹(shù)之前，咱們先來(lái)看下二叉查找樹(shù)。

二叉查找樹(shù)（Binary Search Tree），也稱有序二叉樹(shù)（ordered binary tree）,排序二叉樹(shù)（sorted binary tree），是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：

• 若任意結(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

• 若任意結(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

• 任意結(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)。

• 沒(méi)有鍵值相等的結(jié)點(diǎn)（no duplicate nodes）。

因?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é)）。

但二叉樹(shù)若退化成了一棵具有n個(gè)結(jié)點(diǎn)的線性鏈后，則此些操作最壞情況運(yùn)行時(shí)間為O（n）。后面我們會(huì)看到一種基于二叉查找樹(shù)-紅黑樹(shù)，它通過(guò)一些性質(zhì)使得樹(shù)相對(duì)平衡，使得最終查找、插入、刪除的時(shí)間復(fù)雜度最壞情況下依然為O（lgn）。

紅黑樹(shù)

前面我們已經(jīng)說(shuō)過(guò)，紅黑樹(shù)，本質(zhì)上來(lái)說(shuō)就是一棵二叉查找樹(shù)，但它在二叉查找樹(shù)的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹(shù)相對(duì)平衡，從而保證了紅黑樹(shù)的查找、插入、刪除的時(shí)間復(fù)雜度最壞為O(log n)。

但它是如何保證一棵n個(gè)結(jié)點(diǎn)的紅黑樹(shù)的高度始終保持在h = logn的呢？這就引出了紅黑樹(shù)的5條性質(zhì)：

1）每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。 2）根結(jié)點(diǎn)是黑的。 3）每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹(shù)尾端NIL指針或NULL結(jié)點(diǎn)）是黑的。 4）如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。 5）對(duì)于任一結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹(shù)尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。

正是紅黑樹(shù)的這5條性質(zhì)，使得一棵n個(gè)結(jié)點(diǎn)是紅黑樹(shù)始終保持了logn的高度，從而也就解釋了上面我們所說(shuō)的“紅黑樹(shù)的查找、插入、刪除的時(shí)間復(fù)雜度最壞為O(log n)”這一結(jié)論的原因。

如下圖所示，即是一顆紅黑樹(shù)：

上文中我們所說(shuō)的 "葉結(jié)點(diǎn)" 或"NULL結(jié)點(diǎn)"，它不包含數(shù)據(jù)而只充當(dāng)樹(shù)在此結(jié)束的指示，這些結(jié)點(diǎn)以及它們的父結(jié)點(diǎn)，在繪圖中都會(huì)經(jīng)常被省略。

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

當(dāng)我們?cè)趯?duì)紅黑樹(shù)進(jìn)行插入和刪除等操作時(shí)，對(duì)樹(shù)做了修改，那么可能會(huì)違背紅黑樹(shù)的性質(zhì)。

為了繼續(xù)保持紅黑樹(shù)的性質(zhì)，我們可以通過(guò)對(duì)結(jié)點(diǎn)進(jìn)行重新著色，以及對(duì)樹(shù)進(jìn)行相關(guān)的旋轉(zhuǎn)操作，即修改樹(shù)中某些結(jié)點(diǎn)的顏色及指針結(jié)構(gòu)，來(lái)達(dá)到對(duì)紅黑樹(shù)進(jìn)行插入或刪除結(jié)點(diǎn)等操作后，繼續(xù)保持它的性質(zhì)或平衡。

樹(shù)的旋轉(zhuǎn)，分為左旋和右旋，以下借助圖來(lái)做形象的解釋和介紹：

1.左旋

如上圖所示：

當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為任何不是NIL[T]的左孩子結(jié)點(diǎn)。

左旋以pivot到y(tǒng)之間的鏈為“支軸”進(jìn)行，它使y成為該孩子樹(shù)新的根，而y的左孩子b則成為pivot的右孩子。

左旋操作的參考代碼如下所示（以x代替上述的pivot）：

?LEFT-ROTATE(T,?x)??
1??y?←?right[x]???Set?y.??
2??right[x]?←?left[y]????????Turn?y's?left?subtree?into?x's?right?subtree.??
3??p[left[y]]?←?x??
4??p[y]?←?p[x]???????????????Link?x's?parent?to?y.??
5??if?p[x]?=?nil[T]??
6?????then?root[T]?←?y??
7?????else?if?x?=?left[p[x]]??
8?????????????then?left[p[x]]?←?y??
9?????????????else?right[p[x]]?←?y??
10??left[y]?←?x???????????????Put?x?on?y's?left.??
11??p[x]?←?y

2.右旋

右旋與左旋差不多，再此不做詳細(xì)介紹。

對(duì)于樹(shù)的旋轉(zhuǎn)，能保持不變的只有原樹(shù)的搜索性質(zhì)，而原樹(shù)的紅黑性質(zhì)則不能保持，在紅黑樹(shù)的數(shù)據(jù)插入和刪除后可利用旋轉(zhuǎn)和顏色重涂來(lái)恢復(fù)樹(shù)的紅黑性質(zhì)。

紅黑樹(shù)的插入

要真正理解紅黑樹(shù)的插入和刪除，還得先理解二叉查找樹(shù)的插入和刪除。磨刀不誤砍柴工，咱們?cè)賮?lái)分別了解下二叉查找樹(shù)的插入和刪除。

二叉查找樹(shù)的插入

如果要在二叉查找樹(shù)中插入一個(gè)結(jié)點(diǎn)，首先要查找到結(jié)點(diǎn)插入的位置，然后進(jìn)行插入，假設(shè)插入的結(jié)點(diǎn)為z的話，插入的偽代碼如下：

TREE-INSERT(T,?z)
?1??y?←?NIL
?2??x?←?root[T]
?3??while?x?≠?NIL
?4??????do?y?←??x
?5?????????if?key[z]?<?key[x]
?6????????????then?x?←?left[x]
?7????????????else?x?←?right[x]
?8??p[z]?←?y
?9??if?y?=?NIL
10?????then?root[T]?←?z????????????????Tree?T?was?empty
11?????else?if?key[z]?<?key[y]
12?????????????then?left[y]?←?z
13?????????????else?right[y]?←?z

可以看到，上述第3-7行代碼即是在二叉查找樹(shù)中查找z待插入的位置，如果插入結(jié)點(diǎn)z小于當(dāng)前遍歷到的結(jié)點(diǎn)，則到當(dāng)前結(jié)點(diǎn)的左子樹(shù)中繼續(xù)查找，如果z大于當(dāng)前結(jié)點(diǎn)，則到當(dāng)前結(jié)點(diǎn)的右子樹(shù)中繼續(xù)查找，第9-13行代碼找到待插入的位置，如果z依然比此刻遍歷到的新的當(dāng)前結(jié)點(diǎn)小，則z作為當(dāng)前結(jié)點(diǎn)的左孩子，否則作為當(dāng)前結(jié)點(diǎn)的右孩子。歡迎大家關(guān)注我的公種浩【程序員追風(fēng)】，整理了2019年多家公司java面試題資料100多頁(yè)pdf文檔，文章都會(huì)在里面更新，整理的資料也會(huì)放在里面。

紅黑樹(shù)的插入和插入修復(fù)

現(xiàn)在我們了解了二叉查找樹(shù)的插入，接下來(lái)，咱們便來(lái)具體了解紅黑樹(shù)的插入操作。紅黑樹(shù)的插入相當(dāng)于在二叉查找樹(shù)插入的基礎(chǔ)上，為了重新恢復(fù)平衡，繼續(xù)做了插入修復(fù)操作。

假設(shè)插入的結(jié)點(diǎn)為z，紅黑樹(shù)的插入偽代碼具體如下所示：

RB-INSERT(T,?z)??
?1??y?←?nil[T]??
?2??x?←?root[T]??
?3??while?x?≠?nil[T]??
?4??????do?y?←?x??
?5?????????if?key[z]?<?key[x]??
?6????????????then?x?←?left[x]??
?7????????????else?x?←?right[x]??
?8??p[z]?←?y??
?9??if?y?=?nil[T]??
10?????then?root[T]?←?z??
11?????else?if?key[z]?<?key[y]??
12?????????????then?left[y]?←?z??
13?????????????else?right[y]?←?z??
14??left[z]?←?nil[T]??
15??right[z]?←?nil[T]??
16??color[z]?←?RED??
17??RB-INSERT-FIXUP(T,?z)

我們把上面這段紅黑樹(shù)的插入代碼，跟我們之前看到的二叉查找樹(shù)的插入代碼，可以看出，RB-INSERT(T, z)前面的第1-13行代碼基本就是二叉查找樹(shù)的插入代碼，然后第14-16行代碼把z的左孩子、右孩子都賦為葉結(jié)點(diǎn)nil，再把z結(jié)點(diǎn)著為紅色，最后為保證紅黑性質(zhì)在插入操作后依然保持，調(diào)用一個(gè)輔助程序RB-INSERT-FIXUP來(lái)對(duì)結(jié)點(diǎn)進(jìn)行重新著色，并旋轉(zhuǎn)。

換言之

• 如果插入的是根結(jié)點(diǎn)，因?yàn)樵瓨?shù)是空樹(shù)，此情況只會(huì)違反性質(zhì)2，所以直接把此結(jié)點(diǎn)涂為黑色。

• 如果插入的結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色，由于此不會(huì)違反性質(zhì)2和性質(zhì)4，紅黑樹(shù)沒(méi)有被破壞，所以此時(shí)也是什么也不做。

但當(dāng)遇到下述3種情況時(shí)：

• 插入修復(fù)情況1：如果當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)（叔叔結(jié)點(diǎn)）是紅色

• 插入修復(fù)情況2：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色,叔叔結(jié)點(diǎn)是黑色，當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子

• 插入修復(fù)情況3：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色,叔叔結(jié)點(diǎn)是黑色，當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子

又該如何調(diào)整呢？答案就是根據(jù)紅黑樹(shù)插入代碼RB-INSERT(T, z)最后一行調(diào)用的RB-INSERT-FIXUP（T,z）所示操作進(jìn)行，具體如下所示：

RB-INSERT-FIXUP（T,z）
?1?while?color[p[z]]?=?RED??
?2?????do?if?p[z]?=?left[p[p[z]]]??
?3???????????then?y?←?right[p[p[z]]]??
?4????????????????if?color[y]?=?RED??
?5???????????????????then?color[p[z]]?←?BLACK??????????????????????Case?1??
?6????????????????????????color[y]?←?BLACK?????????????????????????Case?1??
?7????????????????????????color[p[p[z]]]?←?RED?????????????????????Case?1??
?8????????????????????????z?←?p[p[z]]??????????????????????????????Case?1??
?9???????????????????else?if?z?=?right[p[z]]??
10???????????????????????????then?z?←?p[z]?????????????????????????Case?2??
11????????????????????????????????LEFT-ROTATE(T,?z)????????????????Case?2??
12???????????????????????????color[p[z]]?←?BLACK???????????????????Case?3??
13???????????????????????????color[p[p[z]]]?←?RED??????????????????Case?3??
14???????????????????????????RIGHT-ROTATE(T,?p[p[z]])??????????????Case?3??
15???????????else?(same?as?then?clause??
?????????????????????????with?"right"?and?"left"?exchanged)??
16?color[root[T]]?←?BLACK

下面，咱們來(lái)分別處理上述3種插入修復(fù)情況。

插入修復(fù)情況1：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)（叔叔結(jié)點(diǎn)）是紅色。

即如下代碼所示：

?1?while?color[p[z]]?=?RED??
?2?????do?if?p[z]?=?left[p[p[z]]]??
?3???????????then?y?←?right[p[p[z]]]??
?4????????????????if?color[y]?=?RED

此時(shí)父結(jié)點(diǎn)的父結(jié)點(diǎn)一定存在，否則插入前就已不是紅黑樹(shù)。

與此同時(shí)，又分為父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子還是右子，對(duì)于對(duì)稱性，我們只要解開(kāi)一個(gè)方向就可以了。

在此，我們只考慮父結(jié)點(diǎn)為祖父左子的情況。

同時(shí)，還可以分為當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子還是右子，但是處理方式是一樣的。我們將此歸為同一類。

對(duì)策：將當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)涂黑，祖父結(jié)點(diǎn)涂紅，把當(dāng)前結(jié)點(diǎn)指向祖父結(jié)點(diǎn)，從新的當(dāng)前結(jié)點(diǎn)重新開(kāi)始算法。即如下代碼所示：

?5???????????????????then?color[p[z]]?←?BLACK??????????????????????Case?1??
?6????????????????????????color[y]?←?BLACK?????????????????????????Case?1??
?7????????????????????????color[p[p[z]]]?←?RED?????????????????????Case?1??
?8????????????????????????z?←?p[p[z]]??????????????????????????????Case?1

針對(duì)情況1，變化前[當(dāng)前結(jié)點(diǎn)為4結(jié)點(diǎn)]：

變化后：

插入修復(fù)情況2：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色,叔叔結(jié)點(diǎn)是黑色，當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子

對(duì)策：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)做為新的當(dāng)前結(jié)點(diǎn)，以新當(dāng)前結(jié)點(diǎn)為支點(diǎn)左旋。即如下代碼所示：

?9???????????????????else?if?z?=?right[p[z]]
10???????????????????????????then?z?←?p[z]?????????????????????????Case?2
11????????????????????????????????LEFT-ROTATE(T,?z)????????????????Case?2

如下圖所示，變化前[當(dāng)前結(jié)點(diǎn)為7結(jié)點(diǎn)]：

變化后：

插入修復(fù)情況3：當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色,叔叔結(jié)點(diǎn)是黑色，當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子

解法：父結(jié)點(diǎn)變?yōu)楹谏?，祖父結(jié)點(diǎn)變?yōu)榧t色，在祖父結(jié)點(diǎn)為支點(diǎn)右旋，操作代碼為：

12???????????????????????????color[p[z]]?←?BLACK???????????????????Case?3
13???????????????????????????color[p[p[z]]]?←?RED??????????????????Case?3
14???????????????????????????RIGHT-ROTATE(T,?p[p[z]])??????????????Case?3

最后，把根結(jié)點(diǎn)涂為黑色，整棵紅黑樹(shù)便重新恢復(fù)了平衡。

如下圖所示[當(dāng)前結(jié)點(diǎn)為2結(jié)點(diǎn)]

變化后：

紅黑樹(shù)的刪除

ok，接下來(lái)，咱們最后來(lái)了解，紅黑樹(shù)的刪除操作。

"我們刪除的結(jié)點(diǎn)的方法與常規(guī)二叉搜索樹(shù)中刪除結(jié)點(diǎn)的方法是一樣的，如果被刪除的結(jié)點(diǎn)不是有雙非空子女，則直接刪除這個(gè)結(jié)點(diǎn)，用它的唯一子結(jié)點(diǎn)頂替它的位置，如果它的子結(jié)點(diǎn)都是空結(jié)點(diǎn)，那就用空結(jié)點(diǎn)頂替它的位置，如果它的雙子全為非空，我們就把它的直接后繼結(jié)點(diǎn)內(nèi)容復(fù)制到它的位置，之后以同樣的方式刪除它的后繼結(jié)點(diǎn)，它的后繼結(jié)點(diǎn)不可能是雙子非空，因此此傳遞過(guò)程最多只進(jìn)行一次?！?/p>

二叉查找樹(shù)的刪除

繼續(xù)講解之前，補(bǔ)充說(shuō)明下二叉樹(shù)結(jié)點(diǎn)刪除的幾種情況，待刪除的結(jié)點(diǎn)按照兒子的個(gè)數(shù)可以分為三種：

1. 沒(méi)有兒子，即為葉結(jié)點(diǎn)。直接把父結(jié)點(diǎn)的對(duì)應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點(diǎn)就OK了。

2. 只有一個(gè)兒子。那么把父結(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子，刪除兒子結(jié)點(diǎn)也OK了。

3. 有兩個(gè)兒子。這是最麻煩的情況，因?yàn)槟銊h除結(jié)點(diǎn)之后，還要保證滿足搜索二叉樹(shù)的結(jié)構(gòu)。其實(shí)也比較容易，我們可以選擇左兒子中的大元素或者右兒子中的最小元素放到待刪除結(jié)點(diǎn)的位置，就可以保證結(jié)構(gòu)的不變。當(dāng)然，你要記得調(diào)整子樹(shù)，畢竟又出現(xiàn)了結(jié)點(diǎn)刪除。習(xí)慣上大家選擇左兒子中的大元素，其實(shí)選擇右兒子的最小元素也一樣，沒(méi)有任何差別，只是人們習(xí)慣從左向右。這里咱們也選擇左兒子的大元素，將它放到待刪結(jié)點(diǎn)的位置。左兒子的大元素其實(shí)很好找，只要順著左兒子不斷的去搜索右子樹(shù)就可以了，直到找到一個(gè)沒(méi)有右子樹(shù)的結(jié)點(diǎn)。那就是大的了。

二叉查找樹(shù)的刪除代碼如下所示：

TREE-DELETE(T,?z)
?1??if?left[z]?=?NIL?or?right[z]?=?NIL
?2??????then?y?←?z
?3??????else?y?←?TREE-SUCCESSOR(z)
?4??if?left[y]?≠?NIL
?5??????then?x?←?left[y]
?6??????else?x?←?right[y]
?7??if?x?≠?NIL
?8??????then?p[x]?←?p[y]
?9??if?p[y]?=?NIL
10??????then?root[T]?←?x
11??????else?if?y?=?left[p[y]]
12??????????????then?left[p[y]]?←?x
13??????????????else?right[p[y]]?←?x
14??if?y?≠?z
15??????then?key[z]?←?key[y]
16???????????copy?y's?satellite?data?into?z
17??return?y

紅黑樹(shù)的刪除和刪除修復(fù)

OK，回到紅黑樹(shù)上來(lái)，紅黑樹(shù)結(jié)點(diǎn)刪除的算法實(shí)現(xiàn)是：

RB-DELETE(T, z) 單純刪除結(jié)點(diǎn)的總操作

?1?if?left[z]?=?nil[T]?or?right[z]?=?nil[T]??
?2????then?y?←?z??
?3????else?y?←?TREE-SUCCESSOR(z)??
?4?if?left[y]?≠?nil[T]??
?5????then?x?←?left[y]??
?6????else?x?←?right[y]??
?7?p[x]?←?p[y]??
?8?if?p[y]?=?nil[T]??
?9????then?root[T]?←?x??
10????else?if?y?=?left[p[y]]??
11????????????then?left[p[y]]?←?x??
12????????????else?right[p[y]]?←?x??
13?if?y?≠?z??
14????then?key[z]?←?key[y]??
15?????????copy?y's?satellite?data?into?z??
16?if?color[y]?=?BLACK??
17????then?RB-DELETE-FIXUP(T,?x)??
18?return?y

“在刪除結(jié)點(diǎn)后，原紅黑樹(shù)的性質(zhì)可能被改變，如果刪除的是紅色結(jié)點(diǎn)，那么原紅黑樹(shù)的性質(zhì)依舊保持，此時(shí)不用做修正操作，如果刪除的結(jié)點(diǎn)是黑色結(jié)點(diǎn)，原紅黑樹(shù)的性質(zhì)可能會(huì)被改變，我們要對(duì)其做修正操作。那么哪些樹(shù)的性質(zhì)會(huì)發(fā)生變化呢，如果刪除結(jié)點(diǎn)不是樹(shù)唯一結(jié)點(diǎn)，那么刪除結(jié)點(diǎn)的那一個(gè)支的到各葉結(jié)點(diǎn)的黑色結(jié)點(diǎn)數(shù)會(huì)發(fā)生變化，此時(shí)性質(zhì)5被破壞。如果被刪結(jié)點(diǎn)的唯一非空子結(jié)點(diǎn)是紅色，而被刪結(jié)點(diǎn)的父結(jié)點(diǎn)也是紅色，那么性質(zhì)4被破壞。如果被刪結(jié)點(diǎn)是根結(jié)點(diǎn)，而它的唯一非空子結(jié)點(diǎn)是紅色，則刪除后新根結(jié)點(diǎn)將變成紅色，違背性質(zhì)2?！?/p>

RB-DELETE-FIXUP(T, x) 恢復(fù)與保持紅黑性質(zhì)的工作

?1?while?x?≠?root[T]?and?color[x]?=?BLACK??
?2?????do?if?x?=?left[p[x]]??
?3???????????then?w?←?right[p[x]]??
?4????????????????if?color[w]?=?RED??
?5???????????????????then?color[w]?←?BLACK???????????????????????????Case?1??
?6????????????????????????color[p[x]]?←?RED??????????????????????????Case?1??
?7????????????????????????LEFT-ROTATE(T,?p[x])???????????????????????Case?1??
?8????????????????????????w?←?right[p[x]]????????????????????????????Case?1??
?9????????????????if?color[left[w]]?=?BLACK?and?color[right[w]]?=?BLACK??
10???????????????????then?color[w]?←?RED?????????????????????????????Case?2??
11????????????????????????x?←?p[x]???????????????????????????????????Case?2??
12???????????????????else?if?color[right[w]]?=?BLACK??
13???????????????????????????then?color[left[w]]?←?BLACK?????????????Case?3??
14????????????????????????????????color[w]?←?RED?????????????????????Case?3??
15????????????????????????????????RIGHT-ROTATE(T,?w)?????????????????Case?3??
16????????????????????????????????w?←?right[p[x]]????????????????????Case?3??
17?????????????????????????color[w]?←?color[p[x]]????????????????????Case?4??
18?????????????????????????color[p[x]]?←?BLACK???????????????????????Case?4??
19?????????????????????????color[right[w]]?←?BLACK???????????????????Case?4??
20?????????????????????????LEFT-ROTATE(T,?p[x])??????????????????????Case?4??
21?????????????????????????x?←?root[T]???????????????????????????????Case?4??
22????????else?(same?as?then?clause?with?"right"?and?"left"?exchanged)??
23?color[x]?←?BLACK

“上面的修復(fù)情況看起來(lái)有些復(fù)雜，下面我們用一個(gè)分析技巧：我們從被刪結(jié)點(diǎn)后來(lái)頂替它的那個(gè)結(jié)點(diǎn)開(kāi)始調(diào)整，并認(rèn)為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹(shù)的結(jié)點(diǎn)加上除紅與黑的另一種顏色，這里只是一種假設(shè)，我們認(rèn)為我們當(dāng)前指向它，因此空有額外一種黑色，可以認(rèn)為它的黑色是從它的父結(jié)點(diǎn)被刪除后繼承給它的，它現(xiàn)在可以容納兩種顏色，如果它原來(lái)是紅色，那么現(xiàn)在是紅+黑，如果原來(lái)是黑色，那么它現(xiàn)在的顏色是黑+黑。有了這重額外的黑色，原紅黑樹(shù)性質(zhì)5就能保持不變?，F(xiàn)在只要恢復(fù)其它性質(zhì)就可以了，做法還是盡量向根移動(dòng)和窮舉所有可能性。"--saturnman。

如果是以下情況，恢復(fù)比較簡(jiǎn)單：

• a)當(dāng)前結(jié)點(diǎn)是紅+黑色

解法，直接把當(dāng)前結(jié)點(diǎn)染成黑色，結(jié)束此時(shí)紅黑樹(shù)性質(zhì)全部恢復(fù)。

• b)當(dāng)前結(jié)點(diǎn)是黑+黑且是根結(jié)點(diǎn)， 解法：什么都不做，結(jié)束。

但如果是以下情況呢？：

• 刪除修復(fù)情況1：當(dāng)前結(jié)點(diǎn)是黑+黑且兄弟結(jié)點(diǎn)為紅色(此時(shí)父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)分為黑)

• 刪除修復(fù)情況2：當(dāng)前結(jié)點(diǎn)是黑加黑且兄弟是黑色且兄弟結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)全為黑色

• 刪除修復(fù)情況3：當(dāng)前結(jié)點(diǎn)顏色是黑+黑，兄弟結(jié)點(diǎn)是黑色，兄弟的左子是紅色，右子是黑色

• 刪除修復(fù)情況4：當(dāng)前結(jié)點(diǎn)顏色是黑-黑色，它的兄弟結(jié)點(diǎn)是黑色，但是兄弟結(jié)點(diǎn)的右子是紅色，兄弟結(jié)點(diǎn)左子的顏色任意

此時(shí)，我們需要調(diào)用RB-DELETE-FIXUP(T, x)，來(lái)恢復(fù)與保持紅黑性質(zhì)的工作。

下面，咱們便來(lái)分別處理這4種刪除修復(fù)情況。

刪除修復(fù)情況1：當(dāng)前結(jié)點(diǎn)是黑+黑且兄弟結(jié)點(diǎn)為紅色(此時(shí)父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)的子結(jié)點(diǎn)分為黑)。

解法：把父結(jié)點(diǎn)染成紅色，把兄弟結(jié)點(diǎn)染成黑色的，之后重新進(jìn)入算法（我們只討論當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)左孩子時(shí)的情況）。此變換后原紅黑樹(shù)性質(zhì)5不變，而把問(wèn)題轉(zhuǎn)化為兄弟結(jié)點(diǎn)為黑色的情況(注：變化前，原本就未違反性質(zhì)5，只是為了把問(wèn)題轉(zhuǎn)化為兄弟結(jié)點(diǎn)為黑色的情況)。 即如下代碼操作：

//調(diào)用RB-DELETE-FIXUP(T,?x)?的1-8行代碼
?1?while?x?≠?root[T]?and?color[x]?=?BLACK
?2?????do?if?x?=?left[p[x]]
?3???????????then?w?←?right[p[x]]
?4????????????????if?color[w]?=?RED
?5???????????????????then?color[w]?←?BLACK???????????????????????????Case?1
?6????????????????????????color[p[x]]?←?RED??????????????????????????Case?1
?7????????????????????????LEFT-ROTATE(T,?p[x])???????????????????????Case?1
?8????????????????????????w?←?right[p[x]]????????????????????????????Case?1

變化前：

變化后：

刪除修復(fù)情況2：當(dāng)前結(jié)點(diǎn)是黑加黑且兄弟是黑色且兄弟結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)全為黑色。

解法：把當(dāng)前結(jié)點(diǎn)和兄弟結(jié)點(diǎn)中抽取一重黑色追加到父結(jié)點(diǎn)上，把父結(jié)點(diǎn)當(dāng)成新的當(dāng)前結(jié)點(diǎn)，重新進(jìn)入算法。（此變換后性質(zhì)5不變），即調(diào)用RB-INSERT-FIXUP(T, z) 的第9-10行代碼操作，如下：

//調(diào)用RB-DELETE-FIXUP(T,?x)?的9-11行代碼
9????????????????if?color[left[w]]?=?BLACK?and?color[right[w]]?=?BLACK
10???????????????????then?color[w]?←?RED?????????????????????????????Case?2
11????????????????????????x?p[x]?????????????????????????????????????Case?2

變化前：

變化后：

刪除修復(fù)情況3：當(dāng)前結(jié)點(diǎn)顏色是黑+黑，兄弟結(jié)點(diǎn)是黑色，兄弟的左子是紅色，右子是黑色。

解法：把兄弟結(jié)點(diǎn)染紅，兄弟左子結(jié)點(diǎn)染黑，之后再在兄弟結(jié)點(diǎn)為支點(diǎn)解右旋，之后重新進(jìn)入算法。此是把當(dāng)前的情況轉(zhuǎn)化為情況4，而性質(zhì)5得以保持，即調(diào)用RB-INSERT-FIXUP(T, z) 的第12-16行代碼，如下所示：

//調(diào)用RB-DELETE-FIXUP(T,?x)?的第12-16行代碼
12???????????????????else?if?color[right[w]]?=?BLACK
13???????????????????????????then?color[left[w]]?←?BLACK?????????????Case?3
14????????????????????????????????color[w]?←?RED?????????????????????Case?3
15????????????????????????????????RIGHT-ROTATE(T,?w)?????????????????Case?3
16????????????????????????????????w?←?right[p[x]]????????????????????Case?3

變化前：

變化后：

刪除修復(fù)情況4：當(dāng)前結(jié)點(diǎn)顏色是黑-黑色，它的兄弟結(jié)點(diǎn)是黑色，但是兄弟結(jié)點(diǎn)的右子是紅色，兄弟結(jié)點(diǎn)左子的顏色任意。

解法：把兄弟結(jié)點(diǎn)染成當(dāng)前結(jié)點(diǎn)父結(jié)點(diǎn)的顏色，把當(dāng)前結(jié)點(diǎn)父結(jié)點(diǎn)染成黑色，兄弟結(jié)點(diǎn)右子染成黑色的，之后以當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋，此時(shí)算法結(jié)束，紅黑樹(shù)所有性質(zhì)調(diào)整正確，即調(diào)用RB-INSERT-FIXUP(T, z)的第17-21行代碼，如下所示：

//調(diào)用RB-DELETE-FIXUP(T,?x)?的第17-21行代碼
17?????????????????????????color[w]?←?color[p[x]]????????????????????Case?4
18?????????????????????????color[p[x]]?←?BLACK???????????????????????Case?4
19?????????????????????????color[right[w]]?←?BLACK???????????????????Case?4
20?????????????????????????LEFT-ROTATE(T,?p[x])??????????????????????Case?4
21?????????????????????????x?←?root[T]???????????????????????????????Case?4

變化前：

變化后：

本文參考

本文參考了算法導(dǎo)論、STL源碼剖析、計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)等資料。

最后

歡迎大家一起交流，喜歡文章記得點(diǎn)個(gè)贊喲，感謝支持！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)頁(yè)題目：17張圖帶你解析紅黑樹(shù)的原理！保證你能看懂！-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://muchs.cn/article0/djheio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、品牌網(wǎng)站建設(shè)、全網(wǎng)營(yíng)銷(xiāo)推廣、網(wǎng)站策劃、App開(kāi)發(fā)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)