詳細(xì)分析與c++實(shí)現(xiàn))
紅黑樹(shù)的刪除紅黑樹(shù)刪除極其復(fù)雜,實(shí)現(xiàn)難度比AVL樹(shù)刪除更大要考慮的各種分支情況繁多編程實(shí)現(xiàn)時(shí)在瑣碎的細(xì)節(jié)上容易出錯(cuò)但只要用心正確實(shí)現(xiàn)刪除算法不難對(duì)紅黑樹(shù)按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式執(zhí)行刪除,如果實(shí)際刪除的節(jié)點(diǎn)是紅節(jié)點(diǎn),按正常方式刪除刪除后原樹(shù)仍為紅黑樹(shù)結(jié)束若實(shí)際刪除的是黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)并且有唯一子女節(jié)點(diǎn)且該子女節(jié)點(diǎn)為紅將該子女節(jié)點(diǎn)染黑,并按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式刪掉實(shí)際刪除的節(jié)點(diǎn)即可結(jié)束若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)沒(méi)有子女節(jié)點(diǎn)直接刪除實(shí)際刪除節(jié)點(diǎn)將父節(jié)點(diǎn)對(duì)應(yīng)指針域置空令g父節(jié)點(diǎn),unullptr若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)有唯一女節(jié)點(diǎn)該子女節(jié)點(diǎn)為黑則按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式正常執(zhí)行刪除并令g實(shí)際刪除節(jié)點(diǎn)父節(jié)點(diǎn) u實(shí)際刪除節(jié)點(diǎn)子女節(jié)點(diǎn)若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)若該節(jié)點(diǎn)沒(méi)有子樹(shù)直接刪除啦若該節(jié)點(diǎn)有左子樹(shù)沒(méi)有右子樹(shù)刪除該黑節(jié)點(diǎn)然后若左子樹(shù)根節(jié)點(diǎn)為紅染黑結(jié)束 無(wú)左子樹(shù)有右子樹(shù)類似至于既有左子樹(shù)又有右子樹(shù)的情形已經(jīng)被之前所述情形包括在內(nèi)了不用考慮經(jīng)過(guò)上述步驟后如果刪除操作未結(jié)束我們有子樹(shù)gg為其根節(jié)點(diǎn),u為g左子樹(shù)或右子樹(shù)根節(jié)點(diǎn),注意u可能為nullptr即外節(jié)點(diǎn)而且可以發(fā)現(xiàn)u子樹(shù)滿足條件A:在u中刪除一個(gè)節(jié)點(diǎn)并在u中做或不做顏色調(diào)整和平衡化旋轉(zhuǎn)后根節(jié)點(diǎn)u為黑色,從原紅黑樹(shù)根節(jié)點(diǎn)到子樹(shù)u各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目比刪除前原紅黑樹(shù)黑高度小一,從根節(jié)點(diǎn)u至子樹(shù)u各外節(jié)點(diǎn)的路徑上沒(méi)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn),子樹(shù)u為二叉搜索樹(shù),子樹(shù)u的節(jié)點(diǎn)非紅即黑現(xiàn)設(shè)有執(zhí)行刪除操作的紅黑樹(shù)的子樹(shù)gg為其根節(jié)點(diǎn)以u(píng)為根節(jié)點(diǎn)的子樹(shù)為g左子樹(shù)或右子樹(shù),u可以為nullptr并且u子樹(shù)滿足條件A首先注意任意非外節(jié)點(diǎn)的節(jié)點(diǎn)都有兩個(gè)子女兩個(gè)子女要么都是外節(jié)點(diǎn)要么其中一個(gè)是要么都不是當(dāng)然了紅色節(jié)點(diǎn)都不是外節(jié)點(diǎn)所以必有兩個(gè)子女黑色節(jié)點(diǎn)可能為也可能不為外節(jié)點(diǎn)若u為g的右子女則有以下幾種情形g的左子女v為黑色,g為紅色此時(shí)v不可能是外節(jié)點(diǎn),若v是外節(jié)點(diǎn)注意原紅黑樹(shù)根節(jié)點(diǎn)到外節(jié)點(diǎn)v的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目等于刪除前原紅黑樹(shù)黑高度r,而原紅黑樹(shù)根節(jié)點(diǎn)到子樹(shù)u的各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目等于r-1(子樹(shù)u滿足條件A),因此g到v路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目減一即為g到子樹(shù)u各外節(jié)點(diǎn)的路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目由假設(shè)v是外節(jié)點(diǎn)故g到v路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目為1因此g到子樹(shù)u各外節(jié)點(diǎn)的路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目為0這是不可能的因?yàn)閡為黑色v不是外節(jié)點(diǎn)所以有左子女w,這里若w為紅色即如上圖所示此時(shí)交換g,w和v的顏色,對(duì)子樹(shù)g右單旋轉(zhuǎn),然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為紅色,v的左子女w為黑色,v的有子女r為紅色對(duì)g先左后右雙旋轉(zhuǎn),將g染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為紅色,v的左子女w為黑色,v的有子女r為黑色,此時(shí)交換g,v顏色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v(由上述理由它不是外節(jié)點(diǎn))的左子女w為紅色,此時(shí)對(duì)g右單旋轉(zhuǎn)然后將w染黑然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v的左子女w為黑色,v的右子女r為紅色,此時(shí)對(duì)g做先左后右雙旋轉(zhuǎn)然后將r染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v的左子女w為黑色,v的右子女r為黑色,此時(shí)對(duì)g作右單旋轉(zhuǎn),并將g染紅色于是根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證g樹(shù)旋轉(zhuǎn)后為紅黑樹(shù)而且恰好滿足條件A那么若旋轉(zhuǎn)后的g樹(shù)的根已為執(zhí)行刪除操作的紅黑樹(shù)根節(jié)點(diǎn)則可以結(jié)束平衡化過(guò)程,若不為根節(jié)點(diǎn)由于旋轉(zhuǎn)后的g樹(shù)滿足條件A所以原紅黑樹(shù)仍然不平衡于是令u旋轉(zhuǎn)后g樹(shù)根節(jié)點(diǎn) g旋轉(zhuǎn)前g樹(shù)根節(jié)點(diǎn)父節(jié)點(diǎn),回溯至上一層按所列各情形執(zhí)行平衡化這樣做是合理的因?yàn)樾D(zhuǎn)后的g樹(shù)滿足條件A。g的左子女v為紅色,g為黑色,v的右子女r為黑色(顯然),按和上述同樣的理由r不可能是外節(jié)點(diǎn),所以r必有左子女s,若s為紅色,則對(duì)g做先左后右雙旋轉(zhuǎn),將s染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為紅色,g為黑色,v的右子女r為黑色,r的左子女s為黑色,r的右子女t為紅色,此時(shí)對(duì)子樹(shù)r做左單旋轉(zhuǎn),旋轉(zhuǎn)完后將其根節(jié)點(diǎn)鏈接至v的右指針域,然后對(duì)子樹(shù)g做先左后右雙旋轉(zhuǎn)并把t染成黑色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為紅色,g為黑色,v的右子女r為黑色,r的左子女s為黑色,r的右子女t為黑色,此時(shí)對(duì)子樹(shù)g做右單旋轉(zhuǎn)并交換v和r的顏色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束若u為g的右子女則有如下幾種情形這些情形和u為g的右子女時(shí)對(duì)應(yīng)的情形是對(duì)稱的以下所列這些情形從上之下依次和上文所列各情形從上至下保持對(duì)應(yīng)的對(duì)稱關(guān)系平衡化操作和顏色調(diào)整操作也保持對(duì)應(yīng)顏色調(diào)整操作不便平衡化操作正好相反分析是類似就不一一分析只簡(jiǎn)單地列出平衡化操作的類型和顏色調(diào)整操作。g左單旋轉(zhuǎn),交換w,g和v顏色,結(jié)束g先右后左雙旋轉(zhuǎn),g染黑結(jié)束交換g,v顏色,結(jié)束g左單旋轉(zhuǎn),w染黑,結(jié)束g先右后左雙旋轉(zhuǎn),r染黑結(jié)束g左單旋轉(zhuǎn),g染紅,若旋轉(zhuǎn)后的g樹(shù)的根已為執(zhí)行刪除操作的紅黑樹(shù)根節(jié)點(diǎn),結(jié)束否則令u旋轉(zhuǎn)后g樹(shù)根節(jié)點(diǎn) g旋轉(zhuǎn)前g樹(shù)根節(jié)點(diǎn)父節(jié)點(diǎn),回溯至上一層按所列各情形執(zhí)行平衡化g先右后左雙旋轉(zhuǎn),s染黑,結(jié)束r右單旋轉(zhuǎn),g先右后左雙旋轉(zhuǎn),t染黑結(jié)束g左單旋轉(zhuǎn),改變u和r的顏色,結(jié)束從以上討論就可以看出循環(huán)不變量了它就是u子樹(shù)滿足的條件A利用該循環(huán)不變量結(jié)合前面的介紹和博主所寫的AVL樹(shù)插入刪除算法分析一文中的分析思路就可總結(jié)出紅黑樹(shù)的刪除算法這里省略可自行分析。紅黑樹(shù)刪除算法的具體實(shí)現(xiàn)請(qǐng)參考下方代碼。下面討論紅黑樹(shù)的插入在空樹(shù)中插入可直接插入再把插入節(jié)點(diǎn)染黑如果在非空紅黑樹(shù)中插入設(shè)插入的新節(jié)點(diǎn)為uu在節(jié)點(diǎn)p下插入那么無(wú)論u是在p的左子樹(shù)還是右子樹(shù)中插入,以u(píng)為根的子樹(shù)(左右子樹(shù)為外節(jié)點(diǎn))總滿足以下條件B按對(duì)二叉搜索樹(shù)執(zhí)行插入的方式在子樹(shù)u中插入新節(jié)點(diǎn)后在u中做或不做顏色調(diào)整及平衡化旋轉(zhuǎn)后子樹(shù)u根節(jié)點(diǎn)u為紅色從執(zhí)行插入操作的紅黑樹(shù)根節(jié)點(diǎn)至子樹(shù)u各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括該紅黑樹(shù)根節(jié)點(diǎn))的數(shù)目都等于插入前原紅黑樹(shù)的黑高度u至子樹(shù)u任意外節(jié)點(diǎn)的路徑上沒(méi)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn),子樹(shù)u為二叉搜索樹(shù),子樹(shù)u所有節(jié)點(diǎn)非紅即黑。先設(shè)有執(zhí)行插入操作的紅黑樹(shù)的子樹(shù)u它滿足條件B,u的父節(jié)點(diǎn)為p,u為p的左子女或右子女。若u為p的左子女則有如下幾種情形p為黑色,此時(shí)由子樹(shù)u滿足條件B不難驗(yàn)證執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)平衡結(jié)束平衡化過(guò)程p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,若g的右子女r為紅色則交換g和p,r的顏色若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑此時(shí)由子樹(shù)u滿足條件B不難驗(yàn)證子樹(shù)g為紅黑樹(shù)于是結(jié)束平衡化過(guò)程 。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)子樹(shù)g滿足條件B但g的顏色由黑變紅意味著g和其父節(jié)點(diǎn)有可能組成一對(duì)連續(xù)紅節(jié)點(diǎn)所以此時(shí)應(yīng)令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理以消除可能出現(xiàn)的一對(duì)連續(xù)紅色節(jié)點(diǎn)這樣做是合理的因?yàn)榻粨Q顏色后的子樹(shù)g滿足條件B。p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,若g的左子女r為紅色則同樣交換g和p,r的顏色和上一情形類似若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn),則令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,g的右子女r為黑色此時(shí)g做右單旋轉(zhuǎn)并交換p,g顏色然后由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)紅黑樹(shù)特性結(jié)束平衡化過(guò)程。p為紅色,p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,g的左子女r為黑色此時(shí)對(duì)g先右后左雙旋轉(zhuǎn)并交換v,g顏色然后由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)紅黑樹(shù)特性結(jié)束平衡化過(guò)程。若u為p的右子女也有類似諸情形這些情形和以上對(duì)應(yīng)各情形保持對(duì)稱每一種情形和其對(duì)應(yīng)的以上情形相比顏色調(diào)整操作不便旋轉(zhuǎn)操作互為鏡像下面將這些情形及相應(yīng)的處理方式列出這些情形從上至下和上述情形從上至下保持對(duì)應(yīng)和對(duì)稱p為黑色已平衡結(jié)束p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,若g的左子女r為紅色則交換g和p,r顏色,若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束平衡化過(guò)程 。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,若g的右子女r為紅色則同樣交換g和p,r顏色然后若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn),則令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,g的左子女r為黑色此時(shí)g做左單旋轉(zhuǎn)并交換p,g顏色然后已平衡結(jié)束平衡化過(guò)程。p為紅色,p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,g的右子女r為黑色此時(shí)對(duì)g先左后右雙旋轉(zhuǎn)并交換v,g顏色然后結(jié)束平衡化過(guò)程。從以上討論就可以看出循環(huán)不變量就是u子樹(shù)滿足的條件B由此可總結(jié)出紅黑樹(shù)的插入算法這里省略可自行分析。紅黑樹(shù)插入算法的具體實(shí)現(xiàn)請(qǐng)參考下方代碼。下面是實(shí)現(xiàn)紅黑樹(shù)插入與刪除操作的具體代碼(c),代碼中加入了判斷節(jié)點(diǎn)顏色非紅即黑的二叉樹(shù)是否為紅黑樹(shù)的函數(shù)用其在每次插入刪除成功后檢驗(yàn)插入刪除后的二叉樹(shù)是否仍為紅黑樹(shù)以判斷插入刪除算法的正確性#include string #include vector #include iostream #include stack #include random #include ctime using namespace std; #define TYPE int enum ColorFlag { RED, BLACK }; template typename T struct RBTreeNode { T data; //節(jié)點(diǎn)數(shù)據(jù)域 ColorFlag color; //節(jié)點(diǎn)顏色 RBTreeNode* left; RBTreeNode* right; RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {} }; template typename T void RotateLR(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行先左后右雙旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-left; RBTreeNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; ptr q; } template typename T void RotateRL(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行先右后左雙旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-right; RBTreeNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; ptr q; } template typename T void RotateR(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行右單旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-left; ptr-left p-right; p-right ptr; ptr p; } template typename T void RotateL(RBTreeNodeT* ptr) ////對(duì)以ptr為根的子樹(shù)執(zhí)行左單旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-right; ptr-right p-left; p-left ptr; ptr p; } bool examineBlackHeight(bool TF, int preroadblacknum, const int blacknum) { if (TF false) { TF true; preroadblacknum blacknum; } else { if (preroadblacknum ! blacknum) { cout 從根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上黑節(jié)點(diǎn)數(shù)目不等,非紅黑樹(shù) endl; return false; } } return true; } template typename T void addBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) blacknum; } template typename T void reduceBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) --blacknum; } template typename T bool isRB(RBTreeNodeT* root) //判斷以root為根的二叉樹(shù)是否為紅黑樹(shù)(已假定節(jié)點(diǎn)顏色不是為紅色就是為黑色) { if (root-color ColorFlag::RED) { cout 根節(jié)點(diǎn)不為黑色,非紅黑樹(shù) endl; return false; } struct memory { RBTreeNodeT* p; int direction; T lmin; memory(RBTreeNodeT* p, int d) :p(p), direction(d) {} }; T lmax; T rmin; T rmax; int d 0; RBTreeNodeT* ptr root; RBTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int blacknum 0; //統(tǒng)計(jì)路徑上黑節(jié)點(diǎn)個(gè)數(shù)的變量 int preroadblacknum 0; //當(dāng)前路徑的前一路徑上黑節(jié)點(diǎn)數(shù)目 while (true) { int result; if ((result Searchd(ptr, d)) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { addBlackNum(ptr, blacknum); if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax ptr-data; } else { rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax ptr-data; } else { rmin lmin; rmax ptr-data; } } else { if (rmin ptr-data) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; } else rmin ptr-data; } else { T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax rmax; } else rmin lmin; } } } reduceBlackNum(ptr, blacknum); ptr arrange.top().p; d arrange.top().direction; } else { RBTreeNodeT* interval nullptr; if (d 0) { if (ptr-color ColorFlag::RED) { if (result 2) { if (ptr-right-color ColorFlag::RED) { cout 在根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上存在兩個(gè)連續(xù)紅色節(jié)點(diǎn),非紅黑樹(shù) endl; return false; } } else { if (ptr-left-color ColorFlag::RED || ptr-right ! nullptr ptr-right-color ColorFlag::RED) { cout 在根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上存在兩個(gè)連續(xù)紅色節(jié)點(diǎn),非紅黑樹(shù) endl; return false; } } } else blacknum; if (ptr-left nullptr || ptr-right nullptr) { if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; } arrange.push(memory(ptr, result)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void linkWithUpper(RBTreeNodeT* parent, RBTreeNodeT* original, RBTreeNodeT* _new) { if (original parent-left) { parent-left _new; } else { parent-right _new; } } template typename T bool executeDelete(RBTreeNodeT* p, RBTreeNodeT* q) { p-data q-data; if (q-color ColorFlag::RED) //如果被刪節(jié)點(diǎn)為紅色,直接刪除即可 { delete q; return true; //已平衡返回根節(jié)點(diǎn) } if (q-right ! nullptr q-right-color ColorFlag::RED) //被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)為紅色 //右子樹(shù)根節(jié)點(diǎn)染黑,刪除被刪節(jié)點(diǎn),紅黑樹(shù)恢復(fù)平衡,結(jié)束 { q-right-color ColorFlag::BLACK; delete q; return true; } //或被刪節(jié)點(diǎn)及其右子女均為黑色,直接刪除被刪節(jié)點(diǎn)//被刪節(jié)點(diǎn)為葉子黑節(jié)點(diǎn),直接刪除,子樹(shù)q滿足循環(huán)不變條件,向下進(jìn)入do-while循環(huán) delete q; return false; } template typename T RBTreeNodeT* executeDelete(RBTreeNodeT*p, RBTreeNodeT* root, RBTreeNodeT* stackforflashback_top, RBTreeNodeT* p_left_or_right) { if (stackforflashback_top ! nullptr) //被刪節(jié)點(diǎn)有父節(jié)點(diǎn) { if (stackforflashback_top-left p) stackforflashback_top-left p_left_or_right; //將被刪節(jié)點(diǎn)左子樹(shù)或右子樹(shù)鏈接至被刪節(jié)點(diǎn)父節(jié)點(diǎn)相應(yīng)鏈指針 else stackforflashback_top-right p_left_or_right; //被刪節(jié)點(diǎn)一定為黑其左子女一定為紅,左子女染黑,刪除被刪節(jié)點(diǎn),已平衡返回根節(jié)點(diǎn) } else //被刪節(jié)點(diǎn)為根節(jié)點(diǎn)且只有左子樹(shù)或只有右子樹(shù) root p_left_or_right; //直接刪除被刪節(jié)點(diǎn),左子女直接染黑,這樣左子樹(shù)為紅黑樹(shù),結(jié)束 p_left_or_right-color ColorFlag::BLACK; delete p; return root; } template typename T RBTreeNodeT* DelRB(RBTreeNodeT* root, T key) { //紅黑樹(shù)刪除 RBTreeNodeT* p root; stackRBTreeNodeT* stackforflashback; while (p ! nullptr) //搜索被刪除節(jié)點(diǎn),同時(shí)將回溯路徑記錄在棧中 { if (p-data key) break; else { stackforflashback.push(p); if (key p-data) { p p-left; } else { p p-right; } } } if (p ! nullptr) //被刪除節(jié)點(diǎn)存在,被p指向 { RBTreeNodeT* parent nullptr; RBTreeNodeT* q nullptr; if (p-left ! nullptr p-right ! nullptr) //被刪節(jié)點(diǎn)左右子樹(shù)均存在 { q p-right; parent p; if (q-left ! nullptr) //被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)有左子樹(shù) { while (q-left ! nullptr) //在被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)左子樹(shù)中搜索中序遍歷的第一個(gè)節(jié)點(diǎn),同時(shí)用棧記錄回溯路徑 { stackforflashback.push(parent); parent q; q q-left; } parent-left q-right; //用該節(jié)點(diǎn)數(shù)據(jù)域替換被刪節(jié)點(diǎn)數(shù)據(jù)域,將其右子樹(shù)鏈接至其父節(jié)點(diǎn)左鏈指針 if (executeDelete(p, q)) return root; q parent-left; //parent為需要做或不做平衡化旋轉(zhuǎn)及顏色調(diào)整的第一棵子樹(shù)根節(jié)點(diǎn)指針,q為該子樹(shù)左子樹(shù)根節(jié)點(diǎn)指針 } else { p-right q-right; //用被刪節(jié)點(diǎn)右子女?dāng)?shù)據(jù)域替換被刪節(jié)點(diǎn)指針域,將右子女右子樹(shù)鏈接至被刪節(jié)點(diǎn)右鏈指針 if (executeDelete(p, q)) return root; q p-right; //parent為需要做或不做平衡化旋轉(zhuǎn)的第一棵子樹(shù)根節(jié)點(diǎn)指針,q為該子樹(shù)左子樹(shù)根節(jié)點(diǎn)指針 } } else { if (p-left ! nullptr) //被刪節(jié)點(diǎn)左子樹(shù)不空,右子樹(shù)空 return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-left); if (p-right ! nullptr) //處理過(guò)程和以上情形完全對(duì)稱{ return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-right); //被刪節(jié)點(diǎn)為葉節(jié)點(diǎn) if (stackforflashback.empty()) { delete p; //被刪葉節(jié)點(diǎn)為根節(jié)點(diǎn),直接刪除,結(jié)束 return nullptr; } parent stackforflashback.top(); //被刪葉節(jié)點(diǎn)有父節(jié)點(diǎn) stackforflashback.pop(); if (parent-left p) parent-left nullptr; else //將葉節(jié)點(diǎn)的父節(jié)點(diǎn)對(duì)應(yīng)指針域置空 parent-right nullptr; q nullptr; if (p-color ColorFlag::RED) { delete p; return root; } delete p; //被刪葉節(jié)點(diǎn)為黑,直接刪除,此時(shí)q為需要做或不做平衡化旋轉(zhuǎn)和顏色調(diào)整的第一棵子樹(shù)根節(jié)點(diǎn)指針,q子樹(shù)滿足循環(huán)不變條件,向下進(jìn)入do-while循環(huán) } enum class condition_be_processed {C1, C2, C3, C4, C5, C6, C7, C8, C9, _C1, _C10, _C3, _C4, _C5, _C6, _C7, _C8, _C9} distinguish; bool TF false; do //do-while循環(huán)所做工作是,從滿足循環(huán)不變條件的第一棵子樹(shù)起,沿父節(jié)點(diǎn)到第一棵子樹(shù)根節(jié)點(diǎn)的路徑向上平衡化旋轉(zhuǎn)或調(diào)整顏色,直到原紅黑樹(shù)重新恢復(fù)平衡為止 { if (TF true) { linkWithUpper(stackforflashback.top(), q, parent); if (q-color ! ColorFlag::RED) return root; q parent; parent stackforflashback.top(); stackforflashback.pop(); } else TF true; if (parent-right q) { p parent-left; if (parent-color ColorFlag::RED) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C1; else if(p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C2; else distinguish condition_be_processed::C3; } else { if (p-color ColorFlag::BLACK) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C4; else if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C5; else distinguish condition_be_processed::C6; } else { q p-right; if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::C7; else if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::C8; else distinguish condition_be_processed::C9; } } } else { p parent-right; if (parent-color ColorFlag::RED) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C1; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C10; else distinguish condition_be_processed::_C3; } else { if (p-color ColorFlag::BLACK) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C4; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C5; else distinguish condition_be_processed::_C6; } else { q p-left; if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::_C7; else if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::_C8; else distinguish condition_be_processed::_C9; } } } if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1 || distinguish condition_be_processed::C2 || distinguish condition_be_processed::_C10) { q parent; parent-color ColorFlag::BLACK; if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1) { p-color ColorFlag::RED; if (distinguish condition_be_processed::C1) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else { if (distinguish condition_be_processed::C2) RotateLR(parent); else RotateRL(parent); } } else if (distinguish condition_be_processed::C3 || distinguish condition_be_processed::_C3) { parent-color ColorFlag::BLACK; p-color ColorFlag::RED; return root; } else if (distinguish condition_be_processed::C4 || distinguish condition_be_processed::_C4) { q parent; if (distinguish condition_be_processed::C4) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else if (distinguish condition_be_processed::C5 || distinguish condition_be_processed::_C5) { q parent; if (distinguish condition_be_processed::C5) { p-right-color ColorFlag::BLACK; RotateLR(parent); } else { p-left-color ColorFlag::BLACK; RotateRL(parent); } } else if (distinguish condition_be_processed::C6 || distinguish condition_be_processed::_C6) { q parent; parent-color ColorFlag::RED; if (distinguish condition_be_processed::C6) RotateR(parent); else RotateL(parent); } else if (distinguish condition_be_processed::C7 || distinguish condition_be_processed::_C8) { q-left-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::C7) RotateLR(parent); else { RotateR(p-left); RotateRL(parent); } } else if (distinguish condition_be_processed::_C7 || distinguish condition_be_processed::C8) { q-right-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::_C7) RotateRL(parent); else { RotateL(p-right); RotateLR(parent); } } else if (distinguish condition_be_processed::C9 || distinguish condition_be_processed::_C9) { p-color ColorFlag::BLACK; q-color ColorFlag::RED; q parent; if (distinguish condition_be_processed::C9) RotateR(parent); else RotateL(parent); } } while (stackforflashback.empty() false); parent-color ColorFlag::BLACK; return parent; } else { cout 紅黑樹(shù)中不存在要?jiǎng)h除的數(shù)據(jù)元素,刪除失敗 endl; return nullptr; } } template typename T RBTreeNodeT* InsertRB(RBTreeNodeT* root, T key) { //紅黑樹(shù)插入 if (root nullptr) return new RBTreeNodeT(key, ColorFlag::BLACK); else { stackRBTreeNodeT* stackforflashback; RBTreeNodeT* p root; while (p ! nullptr) //搜索插入位置 { stackforflashback.push(p); if (key p-data) p p-left; else if (key p-data) p p-right; else { cout 要插入的關(guān)鍵字在AVL樹(shù)中已存在,插入失敗 endl; return nullptr; } } if (key stackforflashback.top()-data) { p stackforflashback.top()-left new RBTreeNodeT(key, ColorFlag::RED); } else { p stackforflashback.top()-right new RBTreeNodeT(key, ColorFlag::RED); } enum class condition_be_processed {L1, L2, L3, _L1, _L2, _L3}distinguish; RBTreeNodeT* q nullptr; RBTreeNodeT* g nullptr; while (stackforflashback.empty() false) //從第一棵滿足循環(huán)不變條件的子樹(shù)(就是新插入的節(jié)點(diǎn))開(kāi)始逐步向上調(diào)整顏色或進(jìn)行平衡化旋轉(zhuǎn),直到原紅黑樹(shù)重新恢復(fù)平衡為止 { if (g ! nullptr) { if (g-color ColorFlag::BLACK) { linkWithUpper(stackforflashback.top(), p, g); return root; } else p g; } q stackforflashback.top(); //進(jìn)入新一輪循環(huán)后p為滿足循環(huán)不變條件的子樹(shù)的根節(jié)點(diǎn),stackforflashback棧頂指針為其父節(jié)點(diǎn)指針 stackforflashback.pop(); if (q-color ColorFlag::BLACK) return root; g stackforflashback.top(); stackforflashback.pop(); if (q g-left) { if (g-right ! nullptr g-right-color ColorFlag::RED) distinguish condition_be_processed::L1; else if (p q-left) distinguish condition_be_processed::L2; else distinguish condition_be_processed::L3; } else if (g-left ! nullptr g-left-color ColorFlag::RED) distinguish condition_be_processed::_L1; else if (p q-left) distinguish condition_be_processed::_L2; else distinguish condition_be_processed::_L3; g-color ColorFlag::RED; if (distinguish condition_be_processed::L1 || distinguish condition_be_processed::_L1) { q-color ColorFlag::BLACK; if (distinguish condition_be_processed::L1) g-right-color ColorFlag::BLACK; else g-left-color ColorFlag::BLACK; } else if (distinguish condition_be_processed::L2 || distinguish condition_be_processed::_L3) { q-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::L2) RotateR(g); else RotateL(g); } else if (distinguish condition_be_processed::_L2 || distinguish condition_be_processed::L3) { p-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::_L2) RotateRL(g); else RotateLR(g); } } g-color ColorFlag::BLACK; return g; } } template typename T int Searchd(RBTreeNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T void output(RBTreeNodeT* ptr) //輸出以ptr為根的紅黑樹(shù)對(duì)應(yīng)的廣義表形式 { struct memory { RBTreeNodeT* p; int direction; int last; memory(RBTreeNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; int d 0; RBTreeNodeT* const dest ptr; stackmemory arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data; arrange.top().last 1; } else { cout , ptr-data; arrange.top().last 2; } } else { cout ,; cout ptr-data; arrange.top().last 2; } } else { if (arrange.top().last 2) cout ); else { cout , ); } arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { RBTreeNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data (; arrange.top().last 1; } else { cout , ptr-data (; arrange.top().last 2; } } else { cout ,; cout ptr-data (; arrange.top().last 2; } } else { cout ptr-data (; } arrange.push(memory(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) interval ptr-left; else interval ptr-right; } else { arrange.top().direction 2; interval ptr-right; } d 0; ptr interval; } } } int main() { const int N 1000; //vectorTYPE insertvalue{ 13, 2}; vectorTYPE insertvalue; for (int i 1; i N; i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); RBTreeNodeTYPE* root nullptr; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { root InsertRB(root, *p); cout 插入 *p endl; //output(root); cout endl; if (isRB(root) true) { cout 當(dāng)前樹(shù)是紅黑樹(shù); cout endl; } else { cerr 錯(cuò)誤當(dāng)前樹(shù)不是紅黑樹(shù)! endl; exit(0); } } cout endl; //cout 插入完成后刪除前紅黑樹(shù)對(duì)應(yīng)的廣義表形式為: endl; //output(root); cout endl; cout endl; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 刪除節(jié)點(diǎn) *p endl; root DelRB(root, *p); if (root ! nullptr) { //output(root); cout endl; if (isRB(root) true) { cout 當(dāng)前樹(shù)是紅黑樹(shù); cout endl; } else { cerr 錯(cuò)誤當(dāng)前樹(shù)不是紅黑樹(shù)! endl; exit(0); } } else cout NULL; cout endl; } return 0; } 紅黑樹(shù)詳細(xì)分析與c++實(shí)現(xiàn)
紅黑樹(shù)的刪除紅黑樹(shù)刪除極其復(fù)雜,實(shí)現(xiàn)難度比AVL樹(shù)刪除更大要考慮的各種分支情況繁多編程實(shí)現(xiàn)時(shí)在瑣碎的細(xì)節(jié)上容易出錯(cuò)但只要用心正確實(shí)現(xiàn)刪除算法不難對(duì)紅黑樹(shù)按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式執(zhí)行刪除,如果實(shí)際刪除的節(jié)點(diǎn)是紅節(jié)點(diǎn),按正常方式刪除刪除后原樹(shù)仍為紅黑樹(shù)結(jié)束若實(shí)際刪除的是黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)并且有唯一子女節(jié)點(diǎn)且該子女節(jié)點(diǎn)為紅將該子女節(jié)點(diǎn)染黑,并按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式刪掉實(shí)際刪除的節(jié)點(diǎn)即可結(jié)束若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)沒(méi)有子女節(jié)點(diǎn)直接刪除實(shí)際刪除節(jié)點(diǎn)將父節(jié)點(diǎn)對(duì)應(yīng)指針域置空令g父節(jié)點(diǎn),unullptr若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)有父節(jié)點(diǎn)有唯一女節(jié)點(diǎn)該子女節(jié)點(diǎn)為黑則按對(duì)二叉搜索樹(shù)執(zhí)行刪除的方式正常執(zhí)行刪除并令g實(shí)際刪除節(jié)點(diǎn)父節(jié)點(diǎn) u實(shí)際刪除節(jié)點(diǎn)子女節(jié)點(diǎn)若實(shí)際刪除黑節(jié)點(diǎn)該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)若該節(jié)點(diǎn)沒(méi)有子樹(shù)直接刪除啦若該節(jié)點(diǎn)有左子樹(shù)沒(méi)有右子樹(shù)刪除該黑節(jié)點(diǎn)然后若左子樹(shù)根節(jié)點(diǎn)為紅染黑結(jié)束 無(wú)左子樹(shù)有右子樹(shù)類似至于既有左子樹(shù)又有右子樹(shù)的情形已經(jīng)被之前所述情形包括在內(nèi)了不用考慮經(jīng)過(guò)上述步驟后如果刪除操作未結(jié)束我們有子樹(shù)gg為其根節(jié)點(diǎn),u為g左子樹(shù)或右子樹(shù)根節(jié)點(diǎn),注意u可能為nullptr即外節(jié)點(diǎn)而且可以發(fā)現(xiàn)u子樹(shù)滿足條件A:在u中刪除一個(gè)節(jié)點(diǎn)并在u中做或不做顏色調(diào)整和平衡化旋轉(zhuǎn)后根節(jié)點(diǎn)u為黑色,從原紅黑樹(shù)根節(jié)點(diǎn)到子樹(shù)u各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目比刪除前原紅黑樹(shù)黑高度小一,從根節(jié)點(diǎn)u至子樹(shù)u各外節(jié)點(diǎn)的路徑上沒(méi)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn),子樹(shù)u為二叉搜索樹(shù),子樹(shù)u的節(jié)點(diǎn)非紅即黑現(xiàn)設(shè)有執(zhí)行刪除操作的紅黑樹(shù)的子樹(shù)gg為其根節(jié)點(diǎn)以u(píng)為根節(jié)點(diǎn)的子樹(shù)為g左子樹(shù)或右子樹(shù),u可以為nullptr并且u子樹(shù)滿足條件A首先注意任意非外節(jié)點(diǎn)的節(jié)點(diǎn)都有兩個(gè)子女兩個(gè)子女要么都是外節(jié)點(diǎn)要么其中一個(gè)是要么都不是當(dāng)然了紅色節(jié)點(diǎn)都不是外節(jié)點(diǎn)所以必有兩個(gè)子女黑色節(jié)點(diǎn)可能為也可能不為外節(jié)點(diǎn)若u為g的右子女則有以下幾種情形g的左子女v為黑色,g為紅色此時(shí)v不可能是外節(jié)點(diǎn),若v是外節(jié)點(diǎn)注意原紅黑樹(shù)根節(jié)點(diǎn)到外節(jié)點(diǎn)v的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目等于刪除前原紅黑樹(shù)黑高度r,而原紅黑樹(shù)根節(jié)點(diǎn)到子樹(shù)u的各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括原紅黑樹(shù)根節(jié)點(diǎn))數(shù)目等于r-1(子樹(shù)u滿足條件A),因此g到v路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目減一即為g到子樹(shù)u各外節(jié)點(diǎn)的路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目由假設(shè)v是外節(jié)點(diǎn)故g到v路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目為1因此g到子樹(shù)u各外節(jié)點(diǎn)的路徑(節(jié)點(diǎn)g不算在內(nèi))上黑色節(jié)點(diǎn)數(shù)目為0這是不可能的因?yàn)閡為黑色v不是外節(jié)點(diǎn)所以有左子女w,這里若w為紅色即如上圖所示此時(shí)交換g,w和v的顏色,對(duì)子樹(shù)g右單旋轉(zhuǎn),然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為紅色,v的左子女w為黑色,v的有子女r為紅色對(duì)g先左后右雙旋轉(zhuǎn),將g染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為紅色,v的左子女w為黑色,v的有子女r為黑色,此時(shí)交換g,v顏色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v(由上述理由它不是外節(jié)點(diǎn))的左子女w為紅色,此時(shí)對(duì)g右單旋轉(zhuǎn)然后將w染黑然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v的左子女w為黑色,v的右子女r為紅色,此時(shí)對(duì)g做先左后右雙旋轉(zhuǎn)然后將r染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為黑色,g為黑色,v的左子女w為黑色,v的右子女r為黑色,此時(shí)對(duì)g作右單旋轉(zhuǎn),并將g染紅色于是根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證g樹(shù)旋轉(zhuǎn)后為紅黑樹(shù)而且恰好滿足條件A那么若旋轉(zhuǎn)后的g樹(shù)的根已為執(zhí)行刪除操作的紅黑樹(shù)根節(jié)點(diǎn)則可以結(jié)束平衡化過(guò)程,若不為根節(jié)點(diǎn)由于旋轉(zhuǎn)后的g樹(shù)滿足條件A所以原紅黑樹(shù)仍然不平衡于是令u旋轉(zhuǎn)后g樹(shù)根節(jié)點(diǎn) g旋轉(zhuǎn)前g樹(shù)根節(jié)點(diǎn)父節(jié)點(diǎn),回溯至上一層按所列各情形執(zhí)行平衡化這樣做是合理的因?yàn)樾D(zhuǎn)后的g樹(shù)滿足條件A。g的左子女v為紅色,g為黑色,v的右子女r為黑色(顯然),按和上述同樣的理由r不可能是外節(jié)點(diǎn),所以r必有左子女s,若s為紅色,則對(duì)g做先左后右雙旋轉(zhuǎn),將s染黑,然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為紅色,g為黑色,v的右子女r為黑色,r的左子女s為黑色,r的右子女t為紅色,此時(shí)對(duì)子樹(shù)r做左單旋轉(zhuǎn),旋轉(zhuǎn)完后將其根節(jié)點(diǎn)鏈接至v的右指針域,然后對(duì)子樹(shù)g做先左后右雙旋轉(zhuǎn)并把t染成黑色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束g的左子女v為紅色,g為黑色,v的右子女r為黑色,r的左子女s為黑色,r的右子女t為黑色,此時(shí)對(duì)子樹(shù)g做右單旋轉(zhuǎn)并交換v和r的顏色然后根據(jù)子樹(shù)u滿足條件A不難驗(yàn)證此時(shí)原樹(shù)為紅黑樹(shù)已平衡結(jié)束若u為g的右子女則有如下幾種情形這些情形和u為g的右子女時(shí)對(duì)應(yīng)的情形是對(duì)稱的以下所列這些情形從上之下依次和上文所列各情形從上至下保持對(duì)應(yīng)的對(duì)稱關(guān)系平衡化操作和顏色調(diào)整操作也保持對(duì)應(yīng)顏色調(diào)整操作不便平衡化操作正好相反分析是類似就不一一分析只簡(jiǎn)單地列出平衡化操作的類型和顏色調(diào)整操作。g左單旋轉(zhuǎn),交換w,g和v顏色,結(jié)束g先右后左雙旋轉(zhuǎn),g染黑結(jié)束交換g,v顏色,結(jié)束g左單旋轉(zhuǎn),w染黑,結(jié)束g先右后左雙旋轉(zhuǎn),r染黑結(jié)束g左單旋轉(zhuǎn),g染紅,若旋轉(zhuǎn)后的g樹(shù)的根已為執(zhí)行刪除操作的紅黑樹(shù)根節(jié)點(diǎn),結(jié)束否則令u旋轉(zhuǎn)后g樹(shù)根節(jié)點(diǎn) g旋轉(zhuǎn)前g樹(shù)根節(jié)點(diǎn)父節(jié)點(diǎn),回溯至上一層按所列各情形執(zhí)行平衡化g先右后左雙旋轉(zhuǎn),s染黑,結(jié)束r右單旋轉(zhuǎn),g先右后左雙旋轉(zhuǎn),t染黑結(jié)束g左單旋轉(zhuǎn),改變u和r的顏色,結(jié)束從以上討論就可以看出循環(huán)不變量了它就是u子樹(shù)滿足的條件A利用該循環(huán)不變量結(jié)合前面的介紹和博主所寫的AVL樹(shù)插入刪除算法分析一文中的分析思路就可總結(jié)出紅黑樹(shù)的刪除算法這里省略可自行分析。紅黑樹(shù)刪除算法的具體實(shí)現(xiàn)請(qǐng)參考下方代碼。下面討論紅黑樹(shù)的插入在空樹(shù)中插入可直接插入再把插入節(jié)點(diǎn)染黑如果在非空紅黑樹(shù)中插入設(shè)插入的新節(jié)點(diǎn)為uu在節(jié)點(diǎn)p下插入那么無(wú)論u是在p的左子樹(shù)還是右子樹(shù)中插入,以u(píng)為根的子樹(shù)(左右子樹(shù)為外節(jié)點(diǎn))總滿足以下條件B按對(duì)二叉搜索樹(shù)執(zhí)行插入的方式在子樹(shù)u中插入新節(jié)點(diǎn)后在u中做或不做顏色調(diào)整及平衡化旋轉(zhuǎn)后子樹(shù)u根節(jié)點(diǎn)u為紅色從執(zhí)行插入操作的紅黑樹(shù)根節(jié)點(diǎn)至子樹(shù)u各外節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)(不包括該紅黑樹(shù)根節(jié)點(diǎn))的數(shù)目都等于插入前原紅黑樹(shù)的黑高度u至子樹(shù)u任意外節(jié)點(diǎn)的路徑上沒(méi)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn),子樹(shù)u為二叉搜索樹(shù),子樹(shù)u所有節(jié)點(diǎn)非紅即黑。先設(shè)有執(zhí)行插入操作的紅黑樹(shù)的子樹(shù)u它滿足條件B,u的父節(jié)點(diǎn)為p,u為p的左子女或右子女。若u為p的左子女則有如下幾種情形p為黑色,此時(shí)由子樹(shù)u滿足條件B不難驗(yàn)證執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)平衡結(jié)束平衡化過(guò)程p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,若g的右子女r為紅色則交換g和p,r的顏色若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑此時(shí)由子樹(shù)u滿足條件B不難驗(yàn)證子樹(shù)g為紅黑樹(shù)于是結(jié)束平衡化過(guò)程 。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)子樹(shù)g滿足條件B但g的顏色由黑變紅意味著g和其父節(jié)點(diǎn)有可能組成一對(duì)連續(xù)紅節(jié)點(diǎn)所以此時(shí)應(yīng)令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理以消除可能出現(xiàn)的一對(duì)連續(xù)紅色節(jié)點(diǎn)這樣做是合理的因?yàn)榻粨Q顏色后的子樹(shù)g滿足條件B。p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,若g的左子女r為紅色則同樣交換g和p,r的顏色和上一情形類似若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn),則令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,g的右子女r為黑色此時(shí)g做右單旋轉(zhuǎn)并交換p,g顏色然后由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)紅黑樹(shù)特性結(jié)束平衡化過(guò)程。p為紅色,p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,g的左子女r為黑色此時(shí)對(duì)g先右后左雙旋轉(zhuǎn)并交換v,g顏色然后由子樹(shù)u滿足條件B不難驗(yàn)證此時(shí)執(zhí)行插入操作的紅黑樹(shù)已恢復(fù)紅黑樹(shù)特性結(jié)束平衡化過(guò)程。若u為p的右子女也有類似諸情形這些情形和以上對(duì)應(yīng)各情形保持對(duì)稱每一種情形和其對(duì)應(yīng)的以上情形相比顏色調(diào)整操作不便旋轉(zhuǎn)操作互為鏡像下面將這些情形及相應(yīng)的處理方式列出這些情形從上至下和上述情形從上至下保持對(duì)應(yīng)和對(duì)稱p為黑色已平衡結(jié)束p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,若g的左子女r為紅色則交換g和p,r顏色,若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束平衡化過(guò)程 。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,若g的右子女r為紅色則同樣交換g和p,r顏色然后若g已為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn)則將g染黑結(jié)束。若g不為執(zhí)行插入操作的紅黑樹(shù)的根節(jié)點(diǎn),則令ug pg的父節(jié)點(diǎn)回溯至上一層按所列各情形進(jìn)行相同的平衡化處理p為紅色,由原紅黑樹(shù)的特性知p有父節(jié)點(diǎn)g,p為g的右子女g為黑色,g的左子女r為黑色此時(shí)g做左單旋轉(zhuǎn)并交換p,g顏色然后已平衡結(jié)束平衡化過(guò)程。p為紅色,p有父節(jié)點(diǎn)g,p為g的左子女g為黑色,g的右子女r為黑色此時(shí)對(duì)g先左后右雙旋轉(zhuǎn)并交換v,g顏色然后結(jié)束平衡化過(guò)程。從以上討論就可以看出循環(huán)不變量就是u子樹(shù)滿足的條件B由此可總結(jié)出紅黑樹(shù)的插入算法這里省略可自行分析。紅黑樹(shù)插入算法的具體實(shí)現(xiàn)請(qǐng)參考下方代碼。下面是實(shí)現(xiàn)紅黑樹(shù)插入與刪除操作的具體代碼(c),代碼中加入了判斷節(jié)點(diǎn)顏色非紅即黑的二叉樹(shù)是否為紅黑樹(shù)的函數(shù)用其在每次插入刪除成功后檢驗(yàn)插入刪除后的二叉樹(shù)是否仍為紅黑樹(shù)以判斷插入刪除算法的正確性#include string #include vector #include iostream #include stack #include random #include ctime using namespace std; #define TYPE int enum ColorFlag { RED, BLACK }; template typename T struct RBTreeNode { T data; //節(jié)點(diǎn)數(shù)據(jù)域 ColorFlag color; //節(jié)點(diǎn)顏色 RBTreeNode* left; RBTreeNode* right; RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {} }; template typename T void RotateLR(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行先左后右雙旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-left; RBTreeNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; ptr q; } template typename T void RotateRL(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行先右后左雙旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-right; RBTreeNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; ptr q; } template typename T void RotateR(RBTreeNodeT* ptr) //對(duì)以ptr為根的子樹(shù)執(zhí)行右單旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-left; ptr-left p-right; p-right ptr; ptr p; } template typename T void RotateL(RBTreeNodeT* ptr) ////對(duì)以ptr為根的子樹(shù)執(zhí)行左單旋轉(zhuǎn),ptr成為旋轉(zhuǎn)后新樹(shù)根節(jié)點(diǎn)指針 { RBTreeNodeT* p ptr-right; ptr-right p-left; p-left ptr; ptr p; } bool examineBlackHeight(bool TF, int preroadblacknum, const int blacknum) { if (TF false) { TF true; preroadblacknum blacknum; } else { if (preroadblacknum ! blacknum) { cout 從根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上黑節(jié)點(diǎn)數(shù)目不等,非紅黑樹(shù) endl; return false; } } return true; } template typename T void addBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) blacknum; } template typename T void reduceBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) --blacknum; } template typename T bool isRB(RBTreeNodeT* root) //判斷以root為根的二叉樹(shù)是否為紅黑樹(shù)(已假定節(jié)點(diǎn)顏色不是為紅色就是為黑色) { if (root-color ColorFlag::RED) { cout 根節(jié)點(diǎn)不為黑色,非紅黑樹(shù) endl; return false; } struct memory { RBTreeNodeT* p; int direction; T lmin; memory(RBTreeNodeT* p, int d) :p(p), direction(d) {} }; T lmax; T rmin; T rmax; int d 0; RBTreeNodeT* ptr root; RBTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int blacknum 0; //統(tǒng)計(jì)路徑上黑節(jié)點(diǎn)個(gè)數(shù)的變量 int preroadblacknum 0; //當(dāng)前路徑的前一路徑上黑節(jié)點(diǎn)數(shù)目 while (true) { int result; if ((result Searchd(ptr, d)) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { addBlackNum(ptr, blacknum); if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax ptr-data; } else { rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax ptr-data; } else { rmin lmin; rmax ptr-data; } } else { if (rmin ptr-data) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; } else rmin ptr-data; } else { T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax rmax; } else rmin lmin; } } } reduceBlackNum(ptr, blacknum); ptr arrange.top().p; d arrange.top().direction; } else { RBTreeNodeT* interval nullptr; if (d 0) { if (ptr-color ColorFlag::RED) { if (result 2) { if (ptr-right-color ColorFlag::RED) { cout 在根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上存在兩個(gè)連續(xù)紅色節(jié)點(diǎn),非紅黑樹(shù) endl; return false; } } else { if (ptr-left-color ColorFlag::RED || ptr-right ! nullptr ptr-right-color ColorFlag::RED) { cout 在根節(jié)點(diǎn)到外節(jié)點(diǎn)的路徑上存在兩個(gè)連續(xù)紅色節(jié)點(diǎn),非紅黑樹(shù) endl; return false; } } } else blacknum; if (ptr-left nullptr || ptr-right nullptr) { if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; } arrange.push(memory(ptr, result)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 當(dāng)前樹(shù)非二叉搜索樹(shù),也非紅黑樹(shù) endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void linkWithUpper(RBTreeNodeT* parent, RBTreeNodeT* original, RBTreeNodeT* _new) { if (original parent-left) { parent-left _new; } else { parent-right _new; } } template typename T bool executeDelete(RBTreeNodeT* p, RBTreeNodeT* q) { p-data q-data; if (q-color ColorFlag::RED) //如果被刪節(jié)點(diǎn)為紅色,直接刪除即可 { delete q; return true; //已平衡返回根節(jié)點(diǎn) } if (q-right ! nullptr q-right-color ColorFlag::RED) //被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)為紅色 //右子樹(shù)根節(jié)點(diǎn)染黑,刪除被刪節(jié)點(diǎn),紅黑樹(shù)恢復(fù)平衡,結(jié)束 { q-right-color ColorFlag::BLACK; delete q; return true; } //或被刪節(jié)點(diǎn)及其右子女均為黑色,直接刪除被刪節(jié)點(diǎn)//被刪節(jié)點(diǎn)為葉子黑節(jié)點(diǎn),直接刪除,子樹(shù)q滿足循環(huán)不變條件,向下進(jìn)入do-while循環(huán) delete q; return false; } template typename T RBTreeNodeT* executeDelete(RBTreeNodeT*p, RBTreeNodeT* root, RBTreeNodeT* stackforflashback_top, RBTreeNodeT* p_left_or_right) { if (stackforflashback_top ! nullptr) //被刪節(jié)點(diǎn)有父節(jié)點(diǎn) { if (stackforflashback_top-left p) stackforflashback_top-left p_left_or_right; //將被刪節(jié)點(diǎn)左子樹(shù)或右子樹(shù)鏈接至被刪節(jié)點(diǎn)父節(jié)點(diǎn)相應(yīng)鏈指針 else stackforflashback_top-right p_left_or_right; //被刪節(jié)點(diǎn)一定為黑其左子女一定為紅,左子女染黑,刪除被刪節(jié)點(diǎn),已平衡返回根節(jié)點(diǎn) } else //被刪節(jié)點(diǎn)為根節(jié)點(diǎn)且只有左子樹(shù)或只有右子樹(shù) root p_left_or_right; //直接刪除被刪節(jié)點(diǎn),左子女直接染黑,這樣左子樹(shù)為紅黑樹(shù),結(jié)束 p_left_or_right-color ColorFlag::BLACK; delete p; return root; } template typename T RBTreeNodeT* DelRB(RBTreeNodeT* root, T key) { //紅黑樹(shù)刪除 RBTreeNodeT* p root; stackRBTreeNodeT* stackforflashback; while (p ! nullptr) //搜索被刪除節(jié)點(diǎn),同時(shí)將回溯路徑記錄在棧中 { if (p-data key) break; else { stackforflashback.push(p); if (key p-data) { p p-left; } else { p p-right; } } } if (p ! nullptr) //被刪除節(jié)點(diǎn)存在,被p指向 { RBTreeNodeT* parent nullptr; RBTreeNodeT* q nullptr; if (p-left ! nullptr p-right ! nullptr) //被刪節(jié)點(diǎn)左右子樹(shù)均存在 { q p-right; parent p; if (q-left ! nullptr) //被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)有左子樹(shù) { while (q-left ! nullptr) //在被刪節(jié)點(diǎn)右子樹(shù)根節(jié)點(diǎn)左子樹(shù)中搜索中序遍歷的第一個(gè)節(jié)點(diǎn),同時(shí)用棧記錄回溯路徑 { stackforflashback.push(parent); parent q; q q-left; } parent-left q-right; //用該節(jié)點(diǎn)數(shù)據(jù)域替換被刪節(jié)點(diǎn)數(shù)據(jù)域,將其右子樹(shù)鏈接至其父節(jié)點(diǎn)左鏈指針 if (executeDelete(p, q)) return root; q parent-left; //parent為需要做或不做平衡化旋轉(zhuǎn)及顏色調(diào)整的第一棵子樹(shù)根節(jié)點(diǎn)指針,q為該子樹(shù)左子樹(shù)根節(jié)點(diǎn)指針 } else { p-right q-right; //用被刪節(jié)點(diǎn)右子女?dāng)?shù)據(jù)域替換被刪節(jié)點(diǎn)指針域,將右子女右子樹(shù)鏈接至被刪節(jié)點(diǎn)右鏈指針 if (executeDelete(p, q)) return root; q p-right; //parent為需要做或不做平衡化旋轉(zhuǎn)的第一棵子樹(shù)根節(jié)點(diǎn)指針,q為該子樹(shù)左子樹(shù)根節(jié)點(diǎn)指針 } } else { if (p-left ! nullptr) //被刪節(jié)點(diǎn)左子樹(shù)不空,右子樹(shù)空 return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-left); if (p-right ! nullptr) //處理過(guò)程和以上情形完全對(duì)稱{ return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-right); //被刪節(jié)點(diǎn)為葉節(jié)點(diǎn) if (stackforflashback.empty()) { delete p; //被刪葉節(jié)點(diǎn)為根節(jié)點(diǎn),直接刪除,結(jié)束 return nullptr; } parent stackforflashback.top(); //被刪葉節(jié)點(diǎn)有父節(jié)點(diǎn) stackforflashback.pop(); if (parent-left p) parent-left nullptr; else //將葉節(jié)點(diǎn)的父節(jié)點(diǎn)對(duì)應(yīng)指針域置空 parent-right nullptr; q nullptr; if (p-color ColorFlag::RED) { delete p; return root; } delete p; //被刪葉節(jié)點(diǎn)為黑,直接刪除,此時(shí)q為需要做或不做平衡化旋轉(zhuǎn)和顏色調(diào)整的第一棵子樹(shù)根節(jié)點(diǎn)指針,q子樹(shù)滿足循環(huán)不變條件,向下進(jìn)入do-while循環(huán) } enum class condition_be_processed {C1, C2, C3, C4, C5, C6, C7, C8, C9, _C1, _C10, _C3, _C4, _C5, _C6, _C7, _C8, _C9} distinguish; bool TF false; do //do-while循環(huán)所做工作是,從滿足循環(huán)不變條件的第一棵子樹(shù)起,沿父節(jié)點(diǎn)到第一棵子樹(shù)根節(jié)點(diǎn)的路徑向上平衡化旋轉(zhuǎn)或調(diào)整顏色,直到原紅黑樹(shù)重新恢復(fù)平衡為止 { if (TF true) { linkWithUpper(stackforflashback.top(), q, parent); if (q-color ! ColorFlag::RED) return root; q parent; parent stackforflashback.top(); stackforflashback.pop(); } else TF true; if (parent-right q) { p parent-left; if (parent-color ColorFlag::RED) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C1; else if(p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C2; else distinguish condition_be_processed::C3; } else { if (p-color ColorFlag::BLACK) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C4; else if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C5; else distinguish condition_be_processed::C6; } else { q p-right; if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::C7; else if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::C8; else distinguish condition_be_processed::C9; } } } else { p parent-right; if (parent-color ColorFlag::RED) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C1; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C10; else distinguish condition_be_processed::_C3; } else { if (p-color ColorFlag::BLACK) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C4; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C5; else distinguish condition_be_processed::_C6; } else { q p-left; if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::_C7; else if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::_C8; else distinguish condition_be_processed::_C9; } } } if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1 || distinguish condition_be_processed::C2 || distinguish condition_be_processed::_C10) { q parent; parent-color ColorFlag::BLACK; if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1) { p-color ColorFlag::RED; if (distinguish condition_be_processed::C1) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else { if (distinguish condition_be_processed::C2) RotateLR(parent); else RotateRL(parent); } } else if (distinguish condition_be_processed::C3 || distinguish condition_be_processed::_C3) { parent-color ColorFlag::BLACK; p-color ColorFlag::RED; return root; } else if (distinguish condition_be_processed::C4 || distinguish condition_be_processed::_C4) { q parent; if (distinguish condition_be_processed::C4) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else if (distinguish condition_be_processed::C5 || distinguish condition_be_processed::_C5) { q parent; if (distinguish condition_be_processed::C5) { p-right-color ColorFlag::BLACK; RotateLR(parent); } else { p-left-color ColorFlag::BLACK; RotateRL(parent); } } else if (distinguish condition_be_processed::C6 || distinguish condition_be_processed::_C6) { q parent; parent-color ColorFlag::RED; if (distinguish condition_be_processed::C6) RotateR(parent); else RotateL(parent); } else if (distinguish condition_be_processed::C7 || distinguish condition_be_processed::_C8) { q-left-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::C7) RotateLR(parent); else { RotateR(p-left); RotateRL(parent); } } else if (distinguish condition_be_processed::_C7 || distinguish condition_be_processed::C8) { q-right-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::_C7) RotateRL(parent); else { RotateL(p-right); RotateLR(parent); } } else if (distinguish condition_be_processed::C9 || distinguish condition_be_processed::_C9) { p-color ColorFlag::BLACK; q-color ColorFlag::RED; q parent; if (distinguish condition_be_processed::C9) RotateR(parent); else RotateL(parent); } } while (stackforflashback.empty() false); parent-color ColorFlag::BLACK; return parent; } else { cout 紅黑樹(shù)中不存在要?jiǎng)h除的數(shù)據(jù)元素,刪除失敗 endl; return nullptr; } } template typename T RBTreeNodeT* InsertRB(RBTreeNodeT* root, T key) { //紅黑樹(shù)插入 if (root nullptr) return new RBTreeNodeT(key, ColorFlag::BLACK); else { stackRBTreeNodeT* stackforflashback; RBTreeNodeT* p root; while (p ! nullptr) //搜索插入位置 { stackforflashback.push(p); if (key p-data) p p-left; else if (key p-data) p p-right; else { cout 要插入的關(guān)鍵字在AVL樹(shù)中已存在,插入失敗 endl; return nullptr; } } if (key stackforflashback.top()-data) { p stackforflashback.top()-left new RBTreeNodeT(key, ColorFlag::RED); } else { p stackforflashback.top()-right new RBTreeNodeT(key, ColorFlag::RED); } enum class condition_be_processed {L1, L2, L3, _L1, _L2, _L3}distinguish; RBTreeNodeT* q nullptr; RBTreeNodeT* g nullptr; while (stackforflashback.empty() false) //從第一棵滿足循環(huán)不變條件的子樹(shù)(就是新插入的節(jié)點(diǎn))開(kāi)始逐步向上調(diào)整顏色或進(jìn)行平衡化旋轉(zhuǎn),直到原紅黑樹(shù)重新恢復(fù)平衡為止 { if (g ! nullptr) { if (g-color ColorFlag::BLACK) { linkWithUpper(stackforflashback.top(), p, g); return root; } else p g; } q stackforflashback.top(); //進(jìn)入新一輪循環(huán)后p為滿足循環(huán)不變條件的子樹(shù)的根節(jié)點(diǎn),stackforflashback棧頂指針為其父節(jié)點(diǎn)指針 stackforflashback.pop(); if (q-color ColorFlag::BLACK) return root; g stackforflashback.top(); stackforflashback.pop(); if (q g-left) { if (g-right ! nullptr g-right-color ColorFlag::RED) distinguish condition_be_processed::L1; else if (p q-left) distinguish condition_be_processed::L2; else distinguish condition_be_processed::L3; } else if (g-left ! nullptr g-left-color ColorFlag::RED) distinguish condition_be_processed::_L1; else if (p q-left) distinguish condition_be_processed::_L2; else distinguish condition_be_processed::_L3; g-color ColorFlag::RED; if (distinguish condition_be_processed::L1 || distinguish condition_be_processed::_L1) { q-color ColorFlag::BLACK; if (distinguish condition_be_processed::L1) g-right-color ColorFlag::BLACK; else g-left-color ColorFlag::BLACK; } else if (distinguish condition_be_processed::L2 || distinguish condition_be_processed::_L3) { q-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::L2) RotateR(g); else RotateL(g); } else if (distinguish condition_be_processed::_L2 || distinguish condition_be_processed::L3) { p-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::_L2) RotateRL(g); else RotateLR(g); } } g-color ColorFlag::BLACK; return g; } } template typename T int Searchd(RBTreeNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T void output(RBTreeNodeT* ptr) //輸出以ptr為根的紅黑樹(shù)對(duì)應(yīng)的廣義表形式 { struct memory { RBTreeNodeT* p; int direction; int last; memory(RBTreeNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; int d 0; RBTreeNodeT* const dest ptr; stackmemory arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data; arrange.top().last 1; } else { cout , ptr-data; arrange.top().last 2; } } else { cout ,; cout ptr-data; arrange.top().last 2; } } else { if (arrange.top().last 2) cout ); else { cout , ); } arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { RBTreeNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data (; arrange.top().last 1; } else { cout , ptr-data (; arrange.top().last 2; } } else { cout ,; cout ptr-data (; arrange.top().last 2; } } else { cout ptr-data (; } arrange.push(memory(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) interval ptr-left; else interval ptr-right; } else { arrange.top().direction 2; interval ptr-right; } d 0; ptr interval; } } } int main() { const int N 1000; //vectorTYPE insertvalue{ 13, 2}; vectorTYPE insertvalue; for (int i 1; i N; i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); RBTreeNodeTYPE* root nullptr; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { root InsertRB(root, *p); cout 插入 *p endl; //output(root); cout endl; if (isRB(root) true) { cout 當(dāng)前樹(shù)是紅黑樹(shù); cout endl; } else { cerr 錯(cuò)誤當(dāng)前樹(shù)不是紅黑樹(shù)! endl; exit(0); } } cout endl; //cout 插入完成后刪除前紅黑樹(shù)對(duì)應(yīng)的廣義表形式為: endl; //output(root); cout endl; cout endl; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 刪除節(jié)點(diǎn) *p endl; root DelRB(root, *p); if (root ! nullptr) { //output(root); cout endl; if (isRB(root) true) { cout 當(dāng)前樹(shù)是紅黑樹(shù); cout endl; } else { cerr 錯(cuò)誤當(dāng)前樹(shù)不是紅黑樹(shù)! endl; exit(0); } } else cout NULL; cout endl; } return 0; }