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

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