二叉查找樹
由于紅黑樹本質(zhì)上就是一棵二叉查找樹，所以在了解紅黑樹之前，咱們先來看下二叉查找樹。
二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：
若任意結(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
若任意結(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
任意結(jié)點的左、右子樹也分別為二叉查找樹。
沒有鍵值相等的結(jié)點（no duplicate nodes）。
因為，一棵由n個結(jié)點，隨機構(gòu)造的二叉查找樹的高度為lgn，所以順理成章，一般操作的執(zhí)行時間為O（lgn）.（至于n個結(jié)點的二叉樹高度為lgn的證明，可參考算法導(dǎo)論 第12章 二叉查找樹 第12.4節(jié)）。
但二叉樹若退化成了一棵具有n個結(jié)點的線性鏈后，則此些操作最壞情況運行時間為O（n）。后面我們會看到一種基于二叉查找樹-紅黑樹，它通過一些性質(zhì)使得樹相對平衡，使得最終查找、插入、刪除的時間復(fù)雜度最壞情況下依然為O（lgn）。
紅黑樹
前面我們已經(jīng)說過，紅黑樹，本質(zhì)上來說就是一棵二叉查找樹，但它在二叉查找樹的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)。
但它是如何保證一棵n個結(jié)點的紅黑樹的高度始終保持在h = logn的呢？這就引出了紅黑樹的5條性質(zhì)：
1）每個結(jié)點要么是紅的，要么是黑的。 2）根結(jié)點是黑的。 3）每個葉結(jié)點（葉結(jié)點即指樹尾端NIL指針或NULL結(jié)點）是黑的。 4）如果一個結(jié)點是紅的，那么它的倆個兒子都是黑的。 5）對于任一結(jié)點而言，其到葉結(jié)點樹尾端NIL指針的每一條路徑都包含相同數(shù)目的黑結(jié)點。
正是紅黑樹的這5條性質(zhì)，使得一棵n個結(jié)點是紅黑樹始終保持了logn的高度，從而也就解釋了上面我們所說的“紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log n)”這一結(jié)論的原因。
如下圖所示，即是一顆紅黑樹：
上文中我們所說的 "葉結(jié)點" 或"NULL結(jié)點"，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示，這些結(jié)點以及它們的父結(jié)點，在繪圖中都會經(jīng)常被省略。
樹的旋轉(zhuǎn)知識
當(dāng)我們在對紅黑樹進行插入和刪除等操作時，對樹做了修改，那么可能會違背紅黑樹的性質(zhì)。
為了繼續(xù)保持紅黑樹的性質(zhì)，我們可以通過對結(jié)點進行重新著色，以及對樹進行相關(guān)的旋轉(zhuǎn)操作，即修改樹中某些結(jié)點的顏色及指針結(jié)構(gòu)，來達(dá)到對紅黑樹進行插入或刪除結(jié)點等操作后，繼續(xù)保持它的性質(zhì)或平衡。
樹的旋轉(zhuǎn)，分為左旋和右旋，以下借助圖來做形象的解釋和介紹：
1.左旋
如上圖所示：
當(dāng)在某個結(jié)點pivot上，做左旋操作時，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為任何不是NIL[T]的左孩子結(jié)點。
左旋以pivot到y(tǒng)之間的鏈為“支軸”進行，它使y成為該孩子樹新的根，而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ì)介紹。
對于樹的旋轉(zhuǎn)，能保持不變的只有原樹的搜索性質(zhì)，而原樹的紅黑性質(zhì)則不能保持，在紅黑樹的數(shù)據(jù)插入和刪除后可利用旋轉(zhuǎn)和顏色重涂來恢復(fù)樹的紅黑性質(zhì)。
紅黑樹的插入
要真正理解紅黑樹的插入和刪除，還得先理解二叉查找樹的插入和刪除。磨刀不誤砍柴工，咱們再來分別了解下二叉查找樹的插入和刪除。
二叉查找樹的插入
如果要在二叉查找樹中插入一個結(jié)點，首先要查找到結(jié)點插入的位置，然后進行插入，假設(shè)插入的結(jié)點為z的話，插入的偽代碼如下：
TREE-INSERT(T,?z) ?1??y?←?NIL ?2??x?←?root[T] ?3??while?x?≠?NIL ?4??????do?y?←??x ?5?????????if?key[z]?可以看到，上述第3-7行代碼即是在二叉查找樹中查找z待插入的位置，如果插入結(jié)點z小于當(dāng)前遍歷到的結(jié)點，則到當(dāng)前結(jié)點的左子樹中繼續(xù)查找，如果z大于當(dāng)前結(jié)點，則到當(dāng)前結(jié)點的右子樹中繼續(xù)查找，第9-13行代碼找到待插入的位置，如果z依然比此刻遍歷到的新的當(dāng)前結(jié)點小，則z作為當(dāng)前結(jié)點的左孩子，否則作為當(dāng)前結(jié)點的右孩子。歡迎大家關(guān)注我的公種浩【程序員追風(fēng)】，整理了2019年多家公司java面試題資料100多頁pdf文檔，文章都會在里面更新，整理的資料也會放在里面。
紅黑樹的插入和插入修復(fù)
現(xiàn)在我們了解了二叉查找樹的插入，接下來，咱們便來具體了解紅黑樹的插入操作。紅黑樹的插入相當(dāng)于在二叉查找樹插入的基礎(chǔ)上，為了重新恢復(fù)平衡，繼續(xù)做了插入修復(fù)操作。
假設(shè)插入的結(jié)點為z，紅黑樹的插入偽代碼具體如下所示：
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]?我們把上面這段紅黑樹的插入代碼，跟我們之前看到的二叉查找樹的插入代碼，可以看出，RB-INSERT(T, z)前面的第1-13行代碼基本就是二叉查找樹的插入代碼，然后第14-16行代碼把z的左孩子、右孩子都賦為葉結(jié)點nil，再把z結(jié)點著為紅色，最后為保證紅黑性質(zhì)在插入操作后依然保持，調(diào)用一個輔助程序RB-INSERT-FIXUP來對結(jié)點進行重新著色，并旋轉(zhuǎn)。
換言之
如果插入的是根結(jié)點，因為原樹是空樹，此情況只會違反性質(zhì)2，所以直接把此結(jié)點涂為黑色。
如果插入的結(jié)點的父結(jié)點是黑色，由于此不會違反性質(zhì)2和性質(zhì)4，紅黑樹沒有被破壞，所以此時也是什么也不做。
但當(dāng)遇到下述3種情況時：
插入修復(fù)情況1：如果當(dāng)前結(jié)點的父結(jié)點是紅色且祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色
插入修復(fù)情況2：當(dāng)前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當(dāng)前結(jié)點是其父結(jié)點的右子
插入修復(fù)情況3：當(dāng)前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當(dāng)前結(jié)點是其父結(jié)點的左子
又該如何調(diào)整呢？答案就是根據(jù)紅黑樹插入代碼RB-INSERT(T, z)最后一行調(diào)用的RB-INSERT-FIXUP（T,z）所示操作進行，具體如下所示：
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
下面，咱們來分別處理上述3種插入修復(fù)情況。
插入修復(fù)情況1：當(dāng)前結(jié)點的父結(jié)點是紅色且祖父結(jié)點的另一個子結(jié)點（叔叔結(jié)點）是紅色。
即如下代碼所示：
?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
此時父結(jié)點的父結(jié)點一定存在，否則插入前就已不是紅黑樹。
與此同時，又分為父結(jié)點是祖父結(jié)點的左子還是右子，對于對稱性，我們只要解開一個方向就可以了。
在此，我們只考慮父結(jié)點為祖父左子的情況。
同時，還可以分為當(dāng)前結(jié)點是其父結(jié)點的左子還是右子，但是處理方式是一樣的。我們將此歸為同一類。
對策：將當(dāng)前結(jié)點的父結(jié)點和叔叔結(jié)點涂黑，祖父結(jié)點涂紅，把當(dāng)前結(jié)點指向祖父結(jié)點，從新的當(dāng)前結(jié)點重新開始算法。即如下代碼所示：
?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
針對情況1，變化前[當(dāng)前結(jié)點為4結(jié)點]：
變化后：
插入修復(fù)情況2：當(dāng)前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當(dāng)前結(jié)點是其父結(jié)點的右子
對策：當(dāng)前結(jié)點的父結(jié)點做為新的當(dāng)前結(jié)點，以新當(dāng)前結(jié)點為支點左旋。即如下代碼所示：
?9???????????????????else?if?z?=?right[p[z]] 10???????????????????????????then?z?←?p[z]?????????????????????????Case?2 11????????????????????????????????LEFT-ROTATE(T,?z)????????????????Case?2
如下圖所示，變化前[當(dāng)前結(jié)點為7結(jié)點]：
變化后：
插入修復(fù)情況3：當(dāng)前結(jié)點的父結(jié)點是紅色,叔叔結(jié)點是黑色，當(dāng)前結(jié)點是其父結(jié)點的左子
解法：父結(jié)點變?yōu)楹谏?，祖父結(jié)點變?yōu)榧t色，在祖父結(jié)點為支點右旋，操作代碼為：
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é)點涂為黑色，整棵紅黑樹便重新恢復(fù)了平衡。
如下圖所示[當(dāng)前結(jié)點為2結(jié)點]
變化后：
紅黑樹的刪除
ok，接下來，咱們最后來了解，紅黑樹的刪除操作。
"我們刪除的結(jié)點的方法與常規(guī)二叉搜索樹中刪除結(jié)點的方法是一樣的，如果被刪除的結(jié)點不是有雙非空子女，則直接刪除這個結(jié)點，用它的唯一子結(jié)點頂替它的位置，如果它的子結(jié)點都是空結(jié)點，那就用空結(jié)點頂替它的位置，如果它的雙子全為非空，我們就把它的直接后繼結(jié)點內(nèi)容復(fù)制到它的位置，之后以同樣的方式刪除它的后繼結(jié)點，它的后繼結(jié)點不可能是雙子非空，因此此傳遞過程最多只進行一次?！?/p>
二叉查找樹的刪除
繼續(xù)講解之前，補充說明下二叉樹結(jié)點刪除的幾種情況，待刪除的結(jié)點按照兒子的個數(shù)可以分為三種：
沒有兒子，即為葉結(jié)點。直接把父結(jié)點的對應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點就OK了。
只有一個兒子。那么把父結(jié)點的相應(yīng)兒子指針指向兒子的獨生子，刪除兒子結(jié)點也OK了。
有兩個兒子。這是最麻煩的情況，因為你刪除結(jié)點之后，還要保證滿足搜索二叉樹的結(jié)構(gòu)。其實也比較容易，我們可以選擇左兒子中的大元素或者右兒子中的最小元素放到待刪除結(jié)點的位置，就可以保證結(jié)構(gòu)的不變。當(dāng)然，你要記得調(diào)整子樹，畢竟又出現(xiàn)了結(jié)點刪除。習(xí)慣上大家選擇左兒子中的大元素，其實選擇右兒子的最小元素也一樣，沒有任何差別，只是人們習(xí)慣從左向右。這里咱們也選擇左兒子的大元素，將它放到待刪結(jié)點的位置。左兒子的大元素其實很好找，只要順著左兒子不斷的去搜索右子樹就可以了，直到找到一個沒有右子樹的結(jié)點。那就是大的了。
二叉查找樹的刪除代碼如下所示：
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
紅黑樹的刪除和刪除修復(fù)
OK，回到紅黑樹上來，紅黑樹結(jié)點刪除的算法實現(xiàn)是：
RB-DELETE(T, z) 單純刪除結(jié)點的總操作
?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é)點后，原紅黑樹的性質(zhì)可能被改變，如果刪除的是紅色結(jié)點，那么原紅黑樹的性質(zhì)依舊保持，此時不用做修正操作，如果刪除的結(jié)點是黑色結(jié)點，原紅黑樹的性質(zhì)可能會被改變，我們要對其做修正操作。那么哪些樹的性質(zhì)會發(fā)生變化呢，如果刪除結(jié)點不是樹唯一結(jié)點，那么刪除結(jié)點的那一個支的到各葉結(jié)點的黑色結(jié)點數(shù)會發(fā)生變化，此時性質(zhì)5被破壞。如果被刪結(jié)點的唯一非空子結(jié)點是紅色，而被刪結(jié)點的父結(jié)點也是紅色，那么性質(zhì)4被破壞。如果被刪結(jié)點是根結(jié)點，而它的唯一非空子結(jié)點是紅色，則刪除后新根結(jié)點將變成紅色，違背性質(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ù)情況看起來有些復(fù)雜，下面我們用一個分析技巧：我們從被刪結(jié)點后來頂替它的那個結(jié)點開始調(diào)整，并認(rèn)為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹的結(jié)點加上除紅與黑的另一種顏色，這里只是一種假設(shè)，我們認(rèn)為我們當(dāng)前指向它，因此空有額外一種黑色，可以認(rèn)為它的黑色是從它的父結(jié)點被刪除后繼承給它的，它現(xiàn)在可以容納兩種顏色，如果它原來是紅色，那么現(xiàn)在是紅+黑，如果原來是黑色，那么它現(xiàn)在的顏色是黑+黑。有了這重額外的黑色，原紅黑樹性質(zhì)5就能保持不變?，F(xiàn)在只要恢復(fù)其它性質(zhì)就可以了，做法還是盡量向根移動和窮舉所有可能性。"--saturnman。
如果是以下情況，恢復(fù)比較簡單：
a)當(dāng)前結(jié)點是紅+黑色
解法，直接把當(dāng)前結(jié)點染成黑色，結(jié)束此時紅黑樹性質(zhì)全部恢復(fù)。
b)當(dāng)前結(jié)點是黑+黑且是根結(jié)點， 解法：什么都不做，結(jié)束。
但如果是以下情況呢？：
刪除修復(fù)情況1：當(dāng)前結(jié)點是黑+黑且兄弟結(jié)點為紅色(此時父結(jié)點和兄弟結(jié)點的子結(jié)點分為黑)
刪除修復(fù)情況2：當(dāng)前結(jié)點是黑加黑且兄弟是黑色且兄弟結(jié)點的兩個子結(jié)點全為黑色
刪除修復(fù)情況3：當(dāng)前結(jié)點顏色是黑+黑，兄弟結(jié)點是黑色，兄弟的左子是紅色，右子是黑色
刪除修復(fù)情況4：當(dāng)前結(jié)點顏色是黑-黑色，它的兄弟結(jié)點是黑色，但是兄弟結(jié)點的右子是紅色，兄弟結(jié)點左子的顏色任意
此時，我們需要調(diào)用RB-DELETE-FIXUP(T, x)，來恢復(fù)與保持紅黑性質(zhì)的工作。
下面，咱們便來分別處理這4種刪除修復(fù)情況。
刪除修復(fù)情況1：當(dāng)前結(jié)點是黑+黑且兄弟結(jié)點為紅色(此時父結(jié)點和兄弟結(jié)點的子結(jié)點分為黑)。
解法：把父結(jié)點染成紅色，把兄弟結(jié)點染成黑色的，之后重新進入算法（我們只討論當(dāng)前結(jié)點是其父結(jié)點左孩子時的情況）。此變換后原紅黑樹性質(zhì)5不變，而把問題轉(zhuǎn)化為兄弟結(jié)點為黑色的情況(注：變化前，原本就未違反性質(zhì)5，只是為了把問題轉(zhuǎn)化為兄弟結(jié)點為黑色的情況)。 即如下代碼操作：
//調(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é)點是黑加黑且兄弟是黑色且兄弟結(jié)點的兩個子結(jié)點全為黑色。
解法：把當(dāng)前結(jié)點和兄弟結(jié)點中抽取一重黑色追加到父結(jié)點上，把父結(jié)點當(dāng)成新的當(dāng)前結(jié)點，重新進入算法。（此變換后性質(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é)點顏色是黑+黑，兄弟結(jié)點是黑色，兄弟的左子是紅色，右子是黑色。
解法：把兄弟結(jié)點染紅，兄弟左子結(jié)點染黑，之后再在兄弟結(jié)點為支點解右旋，之后重新進入算法。此是把當(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é)點顏色是黑-黑色，它的兄弟結(jié)點是黑色，但是兄弟結(jié)點的右子是紅色，兄弟結(jié)點左子的顏色任意。
解法：把兄弟結(jié)點染成當(dāng)前結(jié)點父結(jié)點的顏色，把當(dāng)前結(jié)點父結(jié)點染成黑色，兄弟結(jié)點右子染成黑色的，之后以當(dāng)前結(jié)點的父結(jié)點為支點進行左旋，此時算法結(jié)束，紅黑樹所有性質(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源碼剖析、計算機程序設(shè)計藝術(shù)等資料。
最后
歡迎大家一起交流，喜歡文章記得點個贊喲，感謝支持！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
重慶分公司
重慶分公司
