《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 7-3紅黑樹

紅黑樹（red－blacktree）的定義紅黑樹是一棵平衡二叉搜索樹，它的深度略高于AVL樹，但可以采用自頂向下(或自底向上)的實現(xiàn)方法，代碼相對簡單，效率高。內(nèi)部結(jié)點外部結(jié)點(虛擬結(jié)點)655070806062510紅黑樹（red－blacktree）的定義為了保證樹的平衡，紅黑樹使用了以下的規(guī)則：RB1:根結(jié)點和外部結(jié)點是黑顏色；RB2:從根結(jié)點到任一外部結(jié)點的路徑上，不能有兩個連續(xù)的紅色結(jié)點；RB3:從根結(jié)點到任一外部結(jié)點的路徑上，黑色結(jié)點個數(shù)相同；紅黑樹（red－blacktree）的性質(zhì)定理1:從根結(jié)點到外部結(jié)點的最短路徑Q和最長路徑P存在以下關(guān)系：length(P)≦2length(Q)證明：由規(guī)則2得知，Q全部由黑色結(jié)點組成，設(shè)有m個黑色結(jié)點（不包括外部結(jié)點），則length(Q)=m。由規(guī)則3得知，P中黑色結(jié)點數(shù)也為m。由條件2得知，紅色結(jié)點只能出現(xiàn)在2個黑色結(jié)點之間，因此，紅色結(jié)點數(shù)為m。因此，length(P)=2m。紅黑樹（red－blacktree）的性質(zhì)令h表示樹的深度，r表示從根結(jié)點到外部結(jié)點路徑中黑色結(jié)點的個數(shù)，n表示樹中結(jié)點個數(shù)（不包括外部結(jié)點）由完全二叉樹的性質(zhì)，n≥2r-1式2根據(jù)定理1,h≦2r式1由式2整理得r≤log2(n+1)式3式1和式3得h≦2log2(n+1)，所以紅黑樹的常用操作的時間復(fù)雜度為O(logn)

AVL樹的深度近似為1.44log2(n+2)紅黑樹（red－blacktree）的性質(zhì)紅黑樹可以像AVL樹那樣采用自底向上的方法實現(xiàn)：首先采用普通的二叉搜索樹的put、remove操作，然后再進行平衡。在平衡過程中，有可能對從插入結(jié)點(刪除結(jié)點)到根結(jié)點路徑上的所有結(jié)點都要平衡，而且，調(diào)整的方向是從插入結(jié)點到根結(jié)點，即從下往上逐一平衡。紅黑樹的優(yōu)勢是采用自頂向下的方法實現(xiàn)：例如put操作首先要從根結(jié)點往下找到插入位置，在找插入位置的過程中就根據(jù)情況進行平衡，當(dāng)找到插入位置時，只插入新結(jié)點即可，而不需要再平衡。自底向上－put1、基本上同二叉搜索樹的put，新插入的結(jié)點x一定是葉子結(jié)點。3、如果結(jié)點x的父結(jié)點的顏色是黑色，則完成。否則，違反規(guī)則BR2，造成出現(xiàn)2個連續(xù)的紅色結(jié)點，需要做調(diào)整。2、紅黑樹的規(guī)則3要求新插入的結(jié)點x必須是紅色（除非插入前是空樹）紅色的表示1棵根結(jié)點為紅色的紅黑樹。黑色的表示1棵根結(jié)點為黑色的紅黑樹。?代表1棵根結(jié)點顏色可紅可黑的紅黑樹下圖中用u表示需要調(diào)整的結(jié)點，pu表示它的父結(jié)點。因為pu是紅色的，并且紅黑樹的根結(jié)點是黑色的，所以，u的祖父結(jié)點gu一定存在。根據(jù)u、pu、gu的左右關(guān)系，有4種形態(tài)，再結(jié)合guR的顏色，有8種情況需要討論。upuguuLuRpuRguR?upuguuLuRpuLguR?upuguuLuRpuLguL?upuguuLuRpuRguL?自底向上－putupuguuLuRpuRguRupuguuLuRpuRguR分析：1、任何從根到以uL、uR、puR、guR為根的子樹中的外部結(jié)點的路徑中黑色結(jié)點的數(shù)目在變換前后沒有發(fā)生變化。2、以gu為根的子樹內(nèi)沒有兩個相鄰的紅色結(jié)點。3、但是，如果gu的父結(jié)點是紅色的，則需要繼續(xù)調(diào)整。如果gu的父結(jié)點是黑色，則結(jié)束。如果gu是根結(jié)點，則將gu的顏色改為黑色（所有路徑的黑色結(jié)點數(shù)增加1個），結(jié)束。改變pu,gu，和guR根結(jié)點的顏色自底向上－put：LLr注：1、紅色結(jié)點變?yōu)楹谏瑫斐山?jīng)過該結(jié)點的從根到外部結(jié)點的路徑黑色的結(jié)點比不經(jīng)過該結(jié)點的路徑多了1個黑色結(jié)點，違背BR3。2、黑色結(jié)點變?yōu)榧t色，可能會造成兩個連續(xù)相鄰的紅色結(jié)點，違背BR2。upuguuLuRpuLguRupuguuLuRpuLguR分析同前，有可能需要繼續(xù)調(diào)整gu。自底向上－put：LRrupuguuLuRpuLguLupuguuLuRpuLguLupuguuLuRpuRguLupuguuLuRpuRguL自底向上－put：RRr、RLr當(dāng)結(jié)點u的叔父結(jié)點為紅色時，無論是LLr、LRr、RRr或RLr，都是改變3個結(jié)點的顏色：pu，gu和guL/R的顏色：紅變黑，黑變紅。然后，如果需要，繼續(xù)調(diào)整gu，直到gu為根結(jié)點或gu不是根結(jié)點但是黑色。注：只要改變3個結(jié)點的顏色，然后繼續(xù)調(diào)整。自底向上－put：XYr小結(jié)upuguuLuRpuRguRupuguuLuRpuRguR旋轉(zhuǎn)，改變pu,gu的顏色upuguuLuRpuLguLupuguuLuRpuLguL旋轉(zhuǎn)，改變pu,gu的顏色自底向上－put：LLb、RRb注：不需要再調(diào)整。旋轉(zhuǎn)upuguuLuRpuLguRupuguuLuRpuLguR旋轉(zhuǎn)，成LLbupuguuLuRpuLguR改變u,gu的顏色注：如果在第1次旋轉(zhuǎn)后，交換pu和u的名字，則第2次旋轉(zhuǎn)和改變顏色的規(guī)則完全同LLb，即1次旋轉(zhuǎn)可以將LRb變換為LLb。自底向上－put：LRb旋轉(zhuǎn)旋轉(zhuǎn)，成RRbupuguuLuRpuRguL改變u,gu的顏色upuguuLuRpuRguLupuguuLuRpuRguL自底向上－put：RLb1、RLb和LRb經(jīng)過1次旋轉(zhuǎn)后，變換為RRb和LLb（同時將u更名為pu）。2、RRb和LLb經(jīng)過1次旋轉(zhuǎn)，然后改變pu和gu的顏色，最終pu為黑色，gu為紅色。3、經(jīng)過旋轉(zhuǎn)后，調(diào)整就結(jié)束，不會繼續(xù)向上調(diào)整。自底向上－put：XYb小結(jié)put－實例50908010初始時插入70，因為70的父結(jié)點是黑色，不需要調(diào)整5090801070初始時插入60，父結(jié)點是紅色，需要調(diào)整。因為是XYr型，改變3個結(jié)點的顏色。5090801070509080107060501060907080自底向上－put：實例插入65，父結(jié)點是紅色，叔父是外部結(jié)點，為黑色。進行2次旋轉(zhuǎn)，改變pu和gu的顏色。5010609070806550106090658070注：如果編程時將所有虛擬的外部結(jié)點用一個實際存在的結(jié)點實現(xiàn)，就不用區(qū)分叔父結(jié)點是空指針還是一般結(jié)點。自底向上－put：實例插入62，父結(jié)點是紅色，叔父是紅色。改變3個結(jié)點的顏色。但65的父結(jié)點是紅色，需要繼續(xù)調(diào)整結(jié)點65。50106090658070625010908062706065自底向上－put：實例65的叔父結(jié)點是10，為黑色。需要進行2次旋轉(zhuǎn)，并改變2個結(jié)點的顏色。5010908062706065旋轉(zhuǎn)5010908062706065自底向上－put：實例旋轉(zhuǎn)，變顏色5010908062706065651090806270605065的叔父結(jié)點是10，為黑色。需要進行2次旋轉(zhuǎn)，并改變2個結(jié)點的顏色。自底向上－put：實例由二叉搜索樹知，被刪除的結(jié)點是葉子結(jié)點或者只有1個孩子結(jié)點。(如果有2個孩子結(jié)點，則已經(jīng)變換為只有1個孩子結(jié)點）對紅黑樹1、如果被刪除的結(jié)點是紅色的，則直接刪除，不會破壞任何規(guī)則。2、如果被刪除的結(jié)點是黑色的，并且孩子結(jié)點是紅色的，則刪除這個結(jié)點，并且把孩子結(jié)點的顏色改為黑色，不會破壞任何規(guī)則。3、如果被刪除的結(jié)點是黑色，并且孩子結(jié)點也是黑色，則刪除這個結(jié)點，會造成從根結(jié)點到外部結(jié)點經(jīng)過這個被刪除結(jié)點的路徑上少了1個黑色結(jié)點，破壞了BR3，需要進行調(diào)整。但是，如果被刪除的結(jié)點是根結(jié)點，則啟用新的根，不用做調(diào)整。自底向上－remove在下面使用y代表以被刪除結(jié)點的孩子結(jié)點為根的子樹，有時也代表這棵子樹的根結(jié)點（如果被刪除結(jié)點是葉子結(jié)點，則該子樹為空），根據(jù)前面的假設(shè)y一定是黑色。y一定有父結(jié)點py（因為需要調(diào)整，所以被刪除的結(jié)點不是根結(jié)點），而且y子樹中少了1個黑色結(jié)點，所以，它一定有1個兄弟結(jié)點v，而且這個兄弟結(jié)點不是外部結(jié)點（否則，從根到兄弟結(jié)點的路徑上就少1個黑色結(jié)點，違反BR3。）根據(jù)兄弟結(jié)點和兄弟結(jié)點的孩子結(jié)點的顏色以及兄弟結(jié)點的位置，可以分別處理：自底向上－remove自底向上－remove：Rb0(i)Rb0:y是右孩子，其兄弟結(jié)點v是黑色，并且v的兩個孩子都是黑色結(jié)點(0個紅色孩子），py是黑色。分析：1、因為v的父、孩子結(jié)點都是黑色，所以不會造成出現(xiàn)2個連續(xù)的紅色結(jié)點。2、但從根結(jié)點到vL和vR中的外部結(jié)點的路徑上就少了1個黑色結(jié)點。3、因為刪除的是黑色結(jié)點，所以，從根結(jié)點到y(tǒng)中的外部結(jié)點的路徑上少了1個黑色結(jié)點。4、綜合2和3，從根結(jié)點到以py為根的子樹中的外部結(jié)點的路徑上少了1個黑色結(jié)點，因此，把py當(dāng)成y，繼續(xù)調(diào)整。5、vL、vR和y的相對位置沒有變化，保證中序遍歷得到的結(jié)點序列仍然是有序的。vpyvLvRyvpyvLvRy改顏色vpyvLvRy改顏色分析：1、從根結(jié)點到vL和vR中外部結(jié)點的路徑上的黑色結(jié)點數(shù)目在改顏色前后沒有變化。2、從根結(jié)點到y(tǒng)中的外部結(jié)點的路徑上的黑色結(jié)點數(shù)目在改顏色后多了1個，補償了因為刪除少的1個黑色結(jié)點。3、以py為根結(jié)點的子樹在的根結(jié)點由紅變?yōu)楹?，不會造成出現(xiàn)連續(xù)的2個紅色結(jié)點，也沒有增加從根結(jié)點到其它外部結(jié)點路徑上黑色結(jié)點的數(shù)目。（因為那些路徑本來就不經(jīng)過py）。4、不需要進一步調(diào)整，調(diào)整結(jié)束5、同前面的分析。py的顏色為紅，其它同Rb0(i)vpyvLvRy自底向上－remove：Rb0(ii)v的左孩子是紅色,其它同前。vpyvLvRyvpyvLvRy分析：驗證沒有造成2個紅色結(jié)點相鄰、從根結(jié)點到vL、vR和y中外部結(jié)點路徑上的黑色結(jié)點沒有變化、3棵子樹的相對位置沒有變化。調(diào)整結(jié)束。py的顏色任意，在轉(zhuǎn)換前后不變化自底向上－remove：Rb1(i)旋轉(zhuǎn)，如果py是黑色，則將vL根結(jié)點改成黑色，否則，vL的顏色不變。即vL與py同顏色。v的右孩子是紅色，其它同前。因為w是紅色，所以它的左右孩子必需都為黑色。旋轉(zhuǎn)vpyvLvRywwLwRvpyvLywwLwRvpyvLywwLwR旋轉(zhuǎn)w繼承py的顏色，py改為黑色分析：同前。調(diào)整結(jié)束。自底向上－remove：Rb1(ii)v的左右孩子都紅色，其它同前。按Rb1(ii)處理。vpyvLvRy自底向上－remove：Rb2y是py的右孩子，v是紅色，vR沒有紅色的孩子(兩個孩子是黑色)。vpyvLvRyvpyvLvRy旋轉(zhuǎn)改變v和vR的顏色分析：v的雙親和兩個孩子一定都是黑色結(jié)點；因為y少了1個黑色結(jié)點，v是紅色，所以vL和vR不會是空樹1、因為假設(shè)子樹vR根結(jié)點的兩個孩子結(jié)點都是黑色的，所以，將vR根結(jié)點改成紅色，不會造成2個紅色結(jié)點相鄰。2、根到vL和vR中外部結(jié)點路徑上的黑色結(jié)點數(shù)在調(diào)整前后沒有變化。3、根到子樹y的外部結(jié)點路徑上多了1個黑色結(jié)點，補償了因刪除少了1個黑色結(jié)點。4、3棵子樹vL、vR和y的相對位置在調(diào)整前后沒有變化。自底向上－remove：Rr0vR的右孩子w(w肯定不是外部結(jié)點)的左孩子是紅色。旋轉(zhuǎn)vpyvLvRywwLwRvpyvLywwLwRvpyvLywwLwR旋轉(zhuǎn)wL改成黑色自底向上－remove：Rr1(i)旋轉(zhuǎn)旋轉(zhuǎn)vpyvLywwLxRxxL2、vR的右孩子的右孩子x是紅色，x的兩個孩子肯定是黑色。vpyvLywwLxRxxLvpyvLywwLxRxxLvpyvLywwLxRxxL旋轉(zhuǎn)將x的顏色改成黑色vR自底向上－remove：Rr1(ii)vR的右孩子w的左右孩子都是紅色。按Rr1(ii)處理。vpyvLvRywwLwR自底向上－remove：Rr2如果y的兄弟結(jié)點是紅色，則要看靠近y的侄孫結(jié)點的顏色進行1-3次旋轉(zhuǎn)并改顏色。自底向上－remove：RrX小結(jié)1、y在左邊，兄弟結(jié)點v是黑色，其兩個孩子都是黑色。處理方法同Rb0(i)，都是將v改成紅色，繼續(xù)調(diào)整pyvpyvLvRyvpyvLvRy繼續(xù)調(diào)整py自底向上－remove：Lb0(i)改顏色vpyvLvRy1、Lb0(ii):同Rb0(ii)。vpyvLvRy分析：根到y(tǒng)中外部結(jié)點的路徑上多了1個黑色結(jié)點，補償了因為刪除少的那個黑色結(jié)點。根到vL和vR中外部結(jié)點路徑上說的黑色結(jié)點數(shù)目沒有變化。自底向上－remove：Lb0(ii)2、Lb1(i):類同Rb1(i)，但旋轉(zhuǎn)方向不一樣，紅色孩子的位置相反。旋轉(zhuǎn)，如果py是黑色，則將vR根結(jié)點改成黑色，否則，vR的顏色不變。即vR與py同顏色。py的顏色任意，在轉(zhuǎn)換前后不變化vpyvLvRyvpyvLvRy自底向上－remove：Lb1(i)2、Lb1(ii)。類同Rb1(ii)，但是旋轉(zhuǎn)方向相反，最終w,py的顏色一致。旋轉(zhuǎn)旋轉(zhuǎn)w繼承py的顏色，py改為黑色調(diào)整結(jié)束。vpywLvRywRwvLvpywLvRywRwvpywLvRywRw自底向上－remove：Lb1(ii)2、Lb2，按Lb1(ii)處理。vpyvLvRy自底向上－remove：Lb21、如果2個侄子都為黑，改顏色。否則2、看侄子結(jié)點的顏色，遠(yuǎn)離y的侄子結(jié)點為紅1次旋轉(zhuǎn)加改顏色，靠近y的侄子結(jié)點為紅，2次旋轉(zhuǎn)加改顏色。3、目的是讓y多1個黑色結(jié)點，其它子樹的黑色結(jié)點數(shù)不變。。自底向上－remove：LbX小結(jié)y是py的左孩子，v是紅色，vL的兩個孩子是黑色。vpyvLvRy旋轉(zhuǎn)改變v和vL的顏色vpyvLvRy自底向上－remove：Lr0vL的左孩子w的右孩子是紅色。旋轉(zhuǎn)vpyvLvRywwLwR旋轉(zhuǎn)vpyvRywwLwRvpyvRywwLwRwR改成黑色自底向上－remove：Lr1(i)旋轉(zhuǎn)旋轉(zhuǎn)vpyvRywwRxRxxLvL的左孩子w的左孩子x是紅色。旋轉(zhuǎn)將x的顏色改成黑色vpyvRywwRxRxxLvpyvRywwRxRxxLvpyvRywwRxRxxL自底向上－remove：Lr1(ii)vL的左孩子w的左右孩子都是紅色。按Lr1(ii)處理。vpyvLvRywwLwR自底向上－remove：Lr2共有：1(刪紅色)+1(刪黑色+孩子紅色)+1(刪根結(jié)點)+刪黑色+孩子結(jié)點黑色：9*2=21種情況自底向上－remove小結(jié)6510908062706050初始刪除90，Rb0(ii)，改變70和80的顏色65108062706050y65107062806050自底向上－remove：實例刪除8065107062806050改變70的顏色651062605070自底向上－remove：實例刪除70Rr1(ii),旋轉(zhuǎn)3次，改變62的顏色6510626050706510626050y6510605062自底向上－remove：實例vpyvLvRy因為v是紅色，所以它的父結(jié)點、左右孩子都是黑色，并且，因為刪除了1個黑色結(jié)點，所以v的左右孩子都不是外部結(jié)點。旋轉(zhuǎn)后，沒有破壞任何規(guī)則，并且y的兄弟結(jié)點是黑色的，可以按照前面的分析處理。v黑色，py紅色vpyvRyvL旋轉(zhuǎn)當(dāng)v是紅色時，除了按照前面的分析處理外，還可以將它變換為v是黑色結(jié)點的情形進行處理。自底向上－remove：變換vpyvLvRy因為v是紅色，所以它的父結(jié)點、左右孩子都是黑色，并且，因為刪除了1個黑色結(jié)點，所以v的左右孩子都不是外部結(jié)點。旋轉(zhuǎn)后，沒有破壞任何規(guī)則，并且y的兄弟結(jié)點是黑色的，可以按照前面的分析處理。v黑色，py紅色vpyvRyvL旋轉(zhuǎn)自底向上－remove：變換自頂向下－put從前面(自底向上的put)的分析可以發(fā)現(xiàn)：1、如果新插入結(jié)點（紅色）的父結(jié)點是黑色，則直接插入即可。2、如果新插入結(jié)點（紅色）的父結(jié)點是紅色，但叔父結(jié)點是黑色，則通過旋轉(zhuǎn)就可以完成調(diào)整，不需要繼續(xù)向上進行調(diào)整?；舅悸罚罕ＷC任何結(jié)點的兩個孩子結(jié)點不會都是紅色：在從根到插入位置的查找過程中，如果某個結(jié)點x是黑色，并且兩個孩子都是紅色，則按照下面的更改父子結(jié)點的顏色：xx這樣可以保證，如果插入結(jié)點的父結(jié)點是紅色，則其叔父結(jié)點一定是黑色。自頂向下－putxx分析：1、改變顏色前后，從根結(jié)點到以x為根的子樹的外部結(jié)點路徑上黑色結(jié)點的數(shù)量沒有改變，所以，不會違反規(guī)則BR3。2、如果x的父結(jié)點是紅色，則改變顏色后，會造成兩個紅色結(jié)點相鄰，但x的叔父結(jié)點一定是黑色，可以用旋轉(zhuǎn)進行調(diào)整，避免違反BR2，不會繼續(xù)向上波及。3、有可能將根結(jié)點改成紅色，最后要改成黑色。自頂向下－put：實例301065580508560157020904055初始插入45，搜索路徑為30->70->60->50->40。在結(jié)點50，需要改變父子結(jié)點的顏色，如下：301065580558560157020905040自頂向下－put：實例改變50的顏色后，出現(xiàn)了50-60兩個連續(xù)紅色結(jié)點，但50的叔父結(jié)點85是黑色的，旋轉(zhuǎn)301065580558560157020905040301065580558570156020905040自頂向下－put：實例301065580558570156020905040插入45，其父結(jié)點是黑色，結(jié)束。30106558055857015602090504045自頂向下－remove從前面的分析可以發(fā)現(xiàn)：1、如果被刪除的結(jié)點是紅色，則直接刪除即可。2、如果被刪除的結(jié)點是黑色，但其孩子結(jié)點是紅色，則改變孩子結(jié)點的顏色即可。3、如果被刪除的結(jié)點是黑色，其孩子結(jié)點也是黑色。如果父結(jié)點是紅色，則可以一次調(diào)整解決問題?；舅悸罚涸趶母絼h除結(jié)點的查找過程中，如果某個結(jié)點x是黑色，則盡可能將它改成紅色，刪除時是1的情形。如果不能調(diào)整成黑色，則延遲處理，保證是情形3。自頂向下－remove首先：引進1個“頭結(jié)點”，讓它的顏色是紅色，并作為根結(jié)點的父結(jié)點：然后，從根結(jié)點開始，在向下的查找過程中，遇到黑色的結(jié)點，就改變顏色為紅色。將要更改顏色的結(jié)點命名為當(dāng)前結(jié)點，用x表示。根結(jié)點頭結(jié)點x的父結(jié)點p一定是紅色，根據(jù)RB2，兄弟結(jié)點s一定是黑色。pxs對x和s孩子結(jié)點的顏色組合進行分析、處理：自頂向下－remove：LBr0x是父結(jié)點的左孩子(L)，x兩個孩子結(jié)點都是黑色(B)，s有0個紅色的孩子結(jié)點(r0)。改變x、p和s的顏色pxssLsRxLxRpxssLsRxLxR自頂向下－remove：LBr1(i)x是父結(jié)點的左孩子，x的兩個孩子結(jié)點都是黑色，s右孩子是紅色。改變x、p、s和sR的顏色pxssLsRxLxRpxssLsRxLxR旋轉(zhuǎn)自頂向下－remove：LBr1(ii)x是父結(jié)點的左孩子，x的兩個孩子結(jié)點都是黑色，s左孩子是紅色。改變x、p的顏色旋轉(zhuǎn)pxssLsRxLxRnnLnRpxssRxLxRnnLnRxpssRxLxRnnLnR旋轉(zhuǎn)自頂向下－remove：LBr2x是父結(jié)點的左孩子，x的兩個孩子結(jié)點都是黑色，s兩個孩子都是紅色。pxssLsRxLxR參照LBr1(i)處理。自頂向下－remove：RBr0x是父結(jié)點的右孩子，x和s的兩個孩子結(jié)點都是黑色。改變x、p和s的顏色psxxLxRsLsRpsxxLxRsLsR自頂向下－remove：RBr1(i)x是父結(jié)點的右孩子，x的兩個孩子結(jié)點都是黑色，s左孩子是紅色。改變x、p、s和sL的顏色psxxLxRsLsRpxssLsRxLxR旋轉(zhuǎn)自頂向下－remove：RBr1(ii)x是父結(jié)點的右孩子，x的兩個孩子結(jié)點都是黑色，s右孩子是紅色。改變x、p的顏色旋轉(zhuǎn)pxssLsRxLxRnnLnR旋轉(zhuǎn)pxssLxLxRnnLnRpxssLxLxRnnLnR自頂向下－remove：RBr2x是父結(jié)點的右孩子，x的兩個孩子結(jié)點都是黑色，s兩個孩子都是紅色。參照RBr1(i)處理。psxxLxRsLsR自頂向下－remove：LBr?和RBr?調(diào)整前，父結(jié)點p是紅色，當(dāng)前結(jié)點x是黑色。調(diào)整后，p是黑色，x是紅色。自頂向下－remove：XR型x是父結(jié)點的左或右孩子，x至少有1個紅色的孩子，如下圖：pxsxLxR此時x的父結(jié)點是紅色，暫緩處理，繼續(xù)向下查找。pxsxLxRpxsxLxRpxsxLxRpxsxLxRpxsxLxR自頂向下－remove：XR型下一個當(dāng)前結(jié)點或者是xL的根結(jié)點或者是xR的根結(jié)點，如果這個結(jié)點是紅色，不需要調(diào)整，繼續(xù)向下。如果是黑色，一種情況如下圖，即xR是當(dāng)前結(jié)點。以x為根的子樹經(jīng)旋轉(zhuǎn)和改顏色后完成了一次變換，調(diào)整后，當(dāng)前結(jié)點仍然是黑色，但父結(jié)點是紅色。旋轉(zhuǎn)xLLxLRpxsxLxRxxRxLxLLxLR自頂向下－remove：XR型另一種情況如下圖，即向xR是當(dāng)前結(jié)點。以x為根的子樹經(jīng)旋轉(zhuǎn)和改顏色后完成了一次變換，調(diào)整后，當(dāng)前結(jié)點仍然是黑色，但父結(jié)點是紅色。旋轉(zhuǎn)xR