)
云深麋鹿專欄C | 用C語言學數(shù)據(jù)結構 | Java回顧上一篇我們結束了 AVLTree 的相關介紹接下來這篇文章讓我們進入到 紅黑樹 的學習體會新的設計思路吧~放個目錄前言一 紅黑樹的概念1.1 紅黑樹的規(guī)則1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍1.3 紅黑樹的效率二 紅黑樹的實現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類Colour2.1.2 定義結點結構體2.2 紅黑樹的插入2.2.1 特別處理1變色1簡單舉例2推廣到所有情況①來個抽象圖②情況1hb 01.介紹所處情況2.采取操作③情況2hb 11.介紹所處情況2.采取措施④情況3hb 21.介紹所處情況2.采取措施3代碼實現(xiàn)2.2.2 特別處理2單旋變色1 u不存在①介紹所處情況②采取操作2u存在且為黑①介紹所處情況②采取措施3代碼實現(xiàn)2.2.3 特別處理3雙旋變色1u不存在①介紹所處情況②采取措施2u存在且為黑①介紹所處情況②采取措施3代碼實現(xiàn)2.2.4 整體代碼2.3 紅黑樹的驗證2.4 紅黑樹的查找2.5 紅黑樹的刪除2.5.1 刪除指定節(jié)點2.5.2 析構2.6 測試前言摘要紅黑樹是一種自平衡的二叉搜索樹通過為每個結點增加顏色屬性并施加約束確保樹的高度始終保持在 O(logN) 級別。本文首先介紹紅黑樹的基本概念與四條核心規(guī)則分析其如何保證最長路徑不超過最短路徑的 2 倍并推導其增刪查改的時間復雜度為 O(logN)隨后以 C 為例從定義結點結構開始逐步實現(xiàn)紅黑樹的插入變色、單旋變色、雙旋變色三種特別處理、驗證、查找、刪除與析構并附上測試用例驗證正確性。最后總結紅黑樹的核心要點為后續(xù)封裝紅黑樹實現(xiàn) mymap 與 myset 容器打下基礎。一 紅黑樹的概念每個結點增加一個存儲位來表示結點的顏色可以是紅色或者黑色。通過對任何一條從根到葉子的路徑上各個結點的顏色進行約束紅黑樹確保沒有一條路徑會比其他路徑長出2倍因而是接近平衡的。1.1 紅黑樹的規(guī)則每個結點不是紅色就是黑色。根結點是黑色的。如果?個結點是紅色的則它的兩個孩子結點必須是黑色的也就是說任意一條路徑不會有連續(xù)的紅色結點。但可以有連續(xù)的黑色節(jié)點對于任意一個結點從該結點到其所有NULL結點的簡單路徑上均包含相同數(shù)量的黑色結點。下面來個動圖演示一顆紅黑樹的形成上圖網址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍從根到NULL結點的每條路徑都有相同數(shù)量的黑色結點。極端場景下最短路徑就就是全是黑色結點的路徑長度設為bh(black height)。最長的路徑就是?黑?紅間隔組成長度設為2*bh。理論上的最短路徑和最長路徑并不是在每棵紅黑樹都存在的。假設任意?條從根到NULL結點路徑的長度為h那么bh h 2*bh。1.3 紅黑樹的效率假設N是紅黑樹樹中結點數(shù)量h最短路徑的長度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN。關于N 2^(2*h) - 1為什么取不到等號存在最短路徑最長路徑的同時二叉樹不可能是滿二叉樹。假設h 1最短路徑為1最長路徑為2。N 取不到2^(2*h) - 1即3。最多只能取到如圖所示2個結點。也就是意味著紅黑樹增刪查改最壞也就是走最長路徑2*logN那么時間復雜度還是O(logN)。二 紅黑樹的實現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類ColourenumColour{RED,BLACK};沒啥好說的紅黑樹就紅色或者黑色兩種結點。2.1.2 定義結點結構體templateclassK,classVstructRBTreeNode{pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};跟AVL樹類似只是多了個_col記錄顏色。這里和AVL樹一樣記錄了_parent方便后續(xù)旋轉。2.2 紅黑樹的插入為了保證每條路徑上的黑色結點數(shù)量相等沒有特殊情況的話新插入結點都為紅。紅黑樹為空插入結點為黑。插入結點的parent為黑插入結點為紅。插入結點的parent為紅插入結點為紅不符合規(guī)則特別處理。假設插入結點為cur插入結點的父母為parentparent的父母為grandparentparent的兄弟為uncle后面都以首字母簡稱。部分代碼boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;// change colour ...}}這部分邏輯跟AVLTree是一樣的除了處理_col的部分處理紅黑樹_root為空的情況。用cur找到新結點應當插入位置parent記錄cur的_parent.最后構造新結點把新結點賦值給cur讓其根據(jù)情況成為parent的左孩子或右孩子。其次若parent為紅需要特殊處理進入循環(huán)。先定義gparent和uncle。注由于parent為紅而_root一定為黑所以gparent一定存在。極端情況為gparent恰好就是_root。2.2.1 特別處理1變色u存在且為紅只變色。1簡單舉例畫個栗圖插入cur后存在連續(xù)的紅色結點。則要實現(xiàn)的效果變色后cur更新為g向上檢查變色。2推廣到所有情況①來個抽象圖上圖的c可能不是新增結點而是從g變到c的設a、b是每條路徑擁有hb-1個黑色結點的根為紅色結點的子樹。設d、e、f是每條路徑擁有hb個黑色結點的子樹。②情況1hb 01.介紹所處情況a、b、d、e、f都是空子樹。如圖c還可以是下面白色結點位置之一c就是新插入結點上面的1簡單舉例就屬于這種情況。2.采取操作直接變色到③情況2hb 11.介紹所處情況c是由g變上來的Ⅰ則a、b是根結點為紅色的hb 0的子樹這樣。Ⅱ新增結點新增結點可能出現(xiàn)在4個位置即4個白色結點之一Ⅲd、e、f是根結點為黑色的hb 1的子樹四種情況。Ⅳ總結一共444*4 256種情況都是只需要變色就行。2.采取措施取其中一種情況分析明顯有連續(xù)的紅色結點不符合規(guī)則3需變色。最終效果再往上檢查④情況3hb 21.介紹所處情況Ⅰ則a、b是根結點為紅色的hb 1的子樹如圖4個位置的紅色結點可能存在或不存在。C(4,4) C(3,4) … C(0,4) 16所以子樹共有16種可能形態(tài)。Ⅱ新增結點16種形態(tài)一種形態(tài)下可新增結點的位置也很多是否會觸發(fā)變色也不一定。拿一個極端例子分析直接新增不觸發(fā)變色Ⅲd、e、f是根結點為黑色的hb 2的子樹子樹可以是3層或4層。3層C(4,4) C(3,4) … C(0,4) 164層C(8,8) C(7,8) … C(0,8) 256所以一共16256 272 種可能形態(tài)。Ⅲ總結總共可能的情況數(shù)有百億往上。2.采取措施取其中一種情況分析變色c向上更新g變到c再繼續(xù)向上更新。3代碼實現(xiàn)//省略給uncle賦值部分代碼if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{//特別處理2}2.2.2 特別處理2單旋變色有兩種情況u不存在 或 存在且為黑。采取操作單旋下面舉例為需要右單旋的情況左單旋本質上也是一樣的變色。1 u不存在①介紹所處情況u不存在則c一定是新增結點。因為如果c更新上來的c原來就得是黑的。c是黑的下圖中g的左子樹和右子樹黑色結點數(shù)量就不相同了。不符合規(guī)則4因此c不可能是更新上來的。②采取操作先以g為旋轉點右單旋再變色2u存在且為黑①介紹所處情況u存在且為黑則c一定是更新上來的。同樣反推如果c是新增節(jié)點a b子樹肯定為空。我們看新增前的樹p的右子樹為空d子樹也肯定為空子樹。先不論 e f 子樹是什么形態(tài)g的右子樹已經比左子樹多了u這個黑色結點不符合規(guī)則4。因此c不可能是新增節(jié)點。在此基礎上我們先來看新增前的情況為保證規(guī)則4a b e f 四棵子樹黑色結點為hb-1個d子樹為hb個。a b是兩棵根結點為紅色的子樹。再來看新增后從新增結點更新上去a b子樹的根結點就變成了黑色上圖 a b d 子樹黑色結點為hb個e f子樹為hb-1個。②采取措施同樣先以g為旋轉點右單旋再變色3代碼實現(xiàn)//同樣省略給uncle賦值部分代碼if(uncleuncle-_colRED){//特別處理1}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}else{//特別處理3}}2.2.3 特別處理3雙旋變色也是兩種情況u不存在 或 存在且為黑。采取操作雙旋這里同樣只舉例先左單旋再右單旋另一種情況本質上一樣變色。1u不存在①介紹所處情況c一定是新增結點這個推論跟單旋的情況一樣。②采取措施先以p為旋轉點左單旋變色再以g為旋轉點右單旋2u存在且為黑①介紹所處情況c同樣一定是更新上來的。新增結點前的樹為保證規(guī)則4d子樹黑色結點數(shù)量為hb a b e f 子樹為hb-1a b 子樹根結點為紅色。新增后假設新增結點在a子樹。更新上去到c變?yōu)榧t色a b子樹變?yōu)楦?jié)點為黑色的子樹。則現(xiàn)在 a b d 子樹黑色結點為hb個e f不變還是hb-1個。②采取措施先以p為旋轉點左單旋變色再以g為旋轉點右單旋最后的樹顯然符合規(guī)則4搞定。3代碼實現(xiàn)if(uncleuncle-_colRED){//特別處理1}else{if(gparent-_leftparentparent-_leftcur){//特別處理2}elseif(gparent-_rightparentparent-_rightcur){//特別處理2}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}2.2.4 整體代碼boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// change colourwhile(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;//給uncle賦值if(gparent-_leftparent){unclegparent-_right;}else{unclegparent-_left;}//分情況特殊處理if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}//循環(huán)繼續(xù)的要點cur跟parent需要更新curgparent;parentcur-_parent;}_root-_colBLACK;returntrue;}為了保證_root是黑的最后可以直接不管三七二十一給它賦值一下。2.3 紅黑樹的驗證分別檢查4條規(guī)則。boolIsRBTree(){if(_rootnullptr){returntrue;}if(_root-_col!BLACK){returnfalse;}intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}return_check(_root,refNum,0);}先處理樹為空_root為空的情況。規(guī)則①檢查_root是否為黑。用refNum記錄一條路徑從_root到空結點的黑色結點備用。進入_check函數(shù)。bool_check(Node*root,constintrefNum,intblackNum){if(rootnullptr){if(blackNum!refNum){coutrefNum:refNum; blackNum:blackNumendl;returnfalse;}returntrue;}if(root-_colBLACK){blackNum;}elseif(root-_colRED){if(root-_parent-_colRED){coutred node has red parentendl;returnfalse;}}else{coutillegal colourendl;returnfalse;}return_check(root-_left,refNum,blackNum)_check(root-_right,refNum,blackNum);}進入函數(shù)先檢查root是否為空。規(guī)則④若為空則結束一條路徑需要檢查這條路徑的黑色結點數(shù)量blackNum是否與參考數(shù)量refNum相等。若不相等則違反規(guī)則④返回false相等則返回true。root不為空則判斷當前root是否為黑。root為黑則blackNum。規(guī)則③root為紅則判斷其parent是否為紅為紅違反規(guī)則③返回false。規(guī)則②若root既不為黑也不為紅違反規(guī)則②返回false。再遞歸檢查root-_left跟root-_right。2.4 紅黑樹的查找跟AVL樹一樣。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}直接照搬過來。2.5 紅黑樹的刪除2.5.1 刪除指定節(jié)點不細究比較復雜可以放一份思路步驟操作說明找真正刪除節(jié)點 y若 z 有兩個孩子用中序后繼替換也可用前驅最終 y 一定只有 0 或 1 個孩子。替換用 y 的孩子x可能為空頂替 y 的位置并記錄 y 在父節(jié)點中的左右方向isLeft。關鍵判斷只有刪除的節(jié)點y是黑色時才需要調用deleteFixup因為刪除紅節(jié)點不影響黑色路徑。修復循環(huán)核心是處理“雙黑”節(jié)點即替代上來的節(jié)點 x。1.兄弟為紅→ 旋轉父節(jié)點轉為兄弟為黑的情況。2.兄弟為黑且其兩個子節(jié)點均為黑→ 兄弟變紅將雙黑往上移。3.兄弟為黑且遠端侄子為黑近端為紅→ 旋轉兄弟轉為情況4。4.兄弟為黑且遠端侄子為紅→ 旋轉父節(jié)點并著色直接結束。收尾循環(huán)結束后將當前節(jié)點x涂黑若 x 為空則忽略徹底消去雙黑。2.5.2 析構加一個析構函數(shù)防止內存泄漏public://...~RBTree(){_Destroy(_root);_rootnullptr;}private:void_Destroy(Node*root){if(rootnullptr){return;}_Destroy(root-_left);_Destroy(root-_right);deleteroot;}//...輔助函數(shù)_Destroy寫在private區(qū)域以便遞歸銷毀。2.6 測試voidTestRBTree01(void){wyzy::RBTreeint,intt;//1測試用例不涉及雙旋//int a[] { 18, 10, 6, 15, 30, 25, 40 };//2測試用例涉及雙旋inta[]{18,10,6,15,30,25,40,27};for(autoe:a){t.Insert({e,e});}t.inOrder();t.preOrder();coutt.IsRBTree()endl;}測試代碼僅供參考。這里我寫了inOrder跟preOrder方便打印觀察。顏色打印出來0代表紅1代表黑。最終測試結果符合預期。紅黑樹的學習就到這里下一篇我們要 封裝紅黑樹 實現(xiàn)容器mymap跟myset 很快會更出來~ C++ | 紅黑樹實現(xiàn)
云深麋鹿專欄C | 用C語言學數(shù)據(jù)結構 | Java回顧上一篇我們結束了 AVLTree 的相關介紹接下來這篇文章讓我們進入到 紅黑樹 的學習體會新的設計思路吧~放個目錄前言一 紅黑樹的概念1.1 紅黑樹的規(guī)則1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍1.3 紅黑樹的效率二 紅黑樹的實現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類Colour2.1.2 定義結點結構體2.2 紅黑樹的插入2.2.1 特別處理1變色1簡單舉例2推廣到所有情況①來個抽象圖②情況1hb 01.介紹所處情況2.采取操作③情況2hb 11.介紹所處情況2.采取措施④情況3hb 21.介紹所處情況2.采取措施3代碼實現(xiàn)2.2.2 特別處理2單旋變色1 u不存在①介紹所處情況②采取操作2u存在且為黑①介紹所處情況②采取措施3代碼實現(xiàn)2.2.3 特別處理3雙旋變色1u不存在①介紹所處情況②采取措施2u存在且為黑①介紹所處情況②采取措施3代碼實現(xiàn)2.2.4 整體代碼2.3 紅黑樹的驗證2.4 紅黑樹的查找2.5 紅黑樹的刪除2.5.1 刪除指定節(jié)點2.5.2 析構2.6 測試前言摘要紅黑樹是一種自平衡的二叉搜索樹通過為每個結點增加顏色屬性并施加約束確保樹的高度始終保持在 O(logN) 級別。本文首先介紹紅黑樹的基本概念與四條核心規(guī)則分析其如何保證最長路徑不超過最短路徑的 2 倍并推導其增刪查改的時間復雜度為 O(logN)隨后以 C 為例從定義結點結構開始逐步實現(xiàn)紅黑樹的插入變色、單旋變色、雙旋變色三種特別處理、驗證、查找、刪除與析構并附上測試用例驗證正確性。最后總結紅黑樹的核心要點為后續(xù)封裝紅黑樹實現(xiàn) mymap 與 myset 容器打下基礎。一 紅黑樹的概念每個結點增加一個存儲位來表示結點的顏色可以是紅色或者黑色。通過對任何一條從根到葉子的路徑上各個結點的顏色進行約束紅黑樹確保沒有一條路徑會比其他路徑長出2倍因而是接近平衡的。1.1 紅黑樹的規(guī)則每個結點不是紅色就是黑色。根結點是黑色的。如果?個結點是紅色的則它的兩個孩子結點必須是黑色的也就是說任意一條路徑不會有連續(xù)的紅色結點。但可以有連續(xù)的黑色節(jié)點對于任意一個結點從該結點到其所有NULL結點的簡單路徑上均包含相同數(shù)量的黑色結點。下面來個動圖演示一顆紅黑樹的形成上圖網址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍從根到NULL結點的每條路徑都有相同數(shù)量的黑色結點。極端場景下最短路徑就就是全是黑色結點的路徑長度設為bh(black height)。最長的路徑就是?黑?紅間隔組成長度設為2*bh。理論上的最短路徑和最長路徑并不是在每棵紅黑樹都存在的。假設任意?條從根到NULL結點路徑的長度為h那么bh h 2*bh。1.3 紅黑樹的效率假設N是紅黑樹樹中結點數(shù)量h最短路徑的長度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN。關于N 2^(2*h) - 1為什么取不到等號存在最短路徑最長路徑的同時二叉樹不可能是滿二叉樹。假設h 1最短路徑為1最長路徑為2。N 取不到2^(2*h) - 1即3。最多只能取到如圖所示2個結點。也就是意味著紅黑樹增刪查改最壞也就是走最長路徑2*logN那么時間復雜度還是O(logN)。二 紅黑樹的實現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類ColourenumColour{RED,BLACK};沒啥好說的紅黑樹就紅色或者黑色兩種結點。2.1.2 定義結點結構體templateclassK,classVstructRBTreeNode{pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};跟AVL樹類似只是多了個_col記錄顏色。這里和AVL樹一樣記錄了_parent方便后續(xù)旋轉。2.2 紅黑樹的插入為了保證每條路徑上的黑色結點數(shù)量相等沒有特殊情況的話新插入結點都為紅。紅黑樹為空插入結點為黑。插入結點的parent為黑插入結點為紅。插入結點的parent為紅插入結點為紅不符合規(guī)則特別處理。假設插入結點為cur插入結點的父母為parentparent的父母為grandparentparent的兄弟為uncle后面都以首字母簡稱。部分代碼boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;// change colour ...}}這部分邏輯跟AVLTree是一樣的除了處理_col的部分處理紅黑樹_root為空的情況。用cur找到新結點應當插入位置parent記錄cur的_parent.最后構造新結點把新結點賦值給cur讓其根據(jù)情況成為parent的左孩子或右孩子。其次若parent為紅需要特殊處理進入循環(huán)。先定義gparent和uncle。注由于parent為紅而_root一定為黑所以gparent一定存在。極端情況為gparent恰好就是_root。2.2.1 特別處理1變色u存在且為紅只變色。1簡單舉例畫個栗圖插入cur后存在連續(xù)的紅色結點。則要實現(xiàn)的效果變色后cur更新為g向上檢查變色。2推廣到所有情況①來個抽象圖上圖的c可能不是新增結點而是從g變到c的設a、b是每條路徑擁有hb-1個黑色結點的根為紅色結點的子樹。設d、e、f是每條路徑擁有hb個黑色結點的子樹。②情況1hb 01.介紹所處情況a、b、d、e、f都是空子樹。如圖c還可以是下面白色結點位置之一c就是新插入結點上面的1簡單舉例就屬于這種情況。2.采取操作直接變色到③情況2hb 11.介紹所處情況c是由g變上來的Ⅰ則a、b是根結點為紅色的hb 0的子樹這樣。Ⅱ新增結點新增結點可能出現(xiàn)在4個位置即4個白色結點之一Ⅲd、e、f是根結點為黑色的hb 1的子樹四種情況。Ⅳ總結一共444*4 256種情況都是只需要變色就行。2.采取措施取其中一種情況分析明顯有連續(xù)的紅色結點不符合規(guī)則3需變色。最終效果再往上檢查④情況3hb 21.介紹所處情況Ⅰ則a、b是根結點為紅色的hb 1的子樹如圖4個位置的紅色結點可能存在或不存在。C(4,4) C(3,4) … C(0,4) 16所以子樹共有16種可能形態(tài)。Ⅱ新增結點16種形態(tài)一種形態(tài)下可新增結點的位置也很多是否會觸發(fā)變色也不一定。拿一個極端例子分析直接新增不觸發(fā)變色Ⅲd、e、f是根結點為黑色的hb 2的子樹子樹可以是3層或4層。3層C(4,4) C(3,4) … C(0,4) 164層C(8,8) C(7,8) … C(0,8) 256所以一共16256 272 種可能形態(tài)。Ⅲ總結總共可能的情況數(shù)有百億往上。2.采取措施取其中一種情況分析變色c向上更新g變到c再繼續(xù)向上更新。3代碼實現(xiàn)//省略給uncle賦值部分代碼if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{//特別處理2}2.2.2 特別處理2單旋變色有兩種情況u不存在 或 存在且為黑。采取操作單旋下面舉例為需要右單旋的情況左單旋本質上也是一樣的變色。1 u不存在①介紹所處情況u不存在則c一定是新增結點。因為如果c更新上來的c原來就得是黑的。c是黑的下圖中g的左子樹和右子樹黑色結點數(shù)量就不相同了。不符合規(guī)則4因此c不可能是更新上來的。②采取操作先以g為旋轉點右單旋再變色2u存在且為黑①介紹所處情況u存在且為黑則c一定是更新上來的。同樣反推如果c是新增節(jié)點a b子樹肯定為空。我們看新增前的樹p的右子樹為空d子樹也肯定為空子樹。先不論 e f 子樹是什么形態(tài)g的右子樹已經比左子樹多了u這個黑色結點不符合規(guī)則4。因此c不可能是新增節(jié)點。在此基礎上我們先來看新增前的情況為保證規(guī)則4a b e f 四棵子樹黑色結點為hb-1個d子樹為hb個。a b是兩棵根結點為紅色的子樹。再來看新增后從新增結點更新上去a b子樹的根結點就變成了黑色上圖 a b d 子樹黑色結點為hb個e f子樹為hb-1個。②采取措施同樣先以g為旋轉點右單旋再變色3代碼實現(xiàn)//同樣省略給uncle賦值部分代碼if(uncleuncle-_colRED){//特別處理1}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}else{//特別處理3}}2.2.3 特別處理3雙旋變色也是兩種情況u不存在 或 存在且為黑。采取操作雙旋這里同樣只舉例先左單旋再右單旋另一種情況本質上一樣變色。1u不存在①介紹所處情況c一定是新增結點這個推論跟單旋的情況一樣。②采取措施先以p為旋轉點左單旋變色再以g為旋轉點右單旋2u存在且為黑①介紹所處情況c同樣一定是更新上來的。新增結點前的樹為保證規(guī)則4d子樹黑色結點數(shù)量為hb a b e f 子樹為hb-1a b 子樹根結點為紅色。新增后假設新增結點在a子樹。更新上去到c變?yōu)榧t色a b子樹變?yōu)楦?jié)點為黑色的子樹。則現(xiàn)在 a b d 子樹黑色結點為hb個e f不變還是hb-1個。②采取措施先以p為旋轉點左單旋變色再以g為旋轉點右單旋最后的樹顯然符合規(guī)則4搞定。3代碼實現(xiàn)if(uncleuncle-_colRED){//特別處理1}else{if(gparent-_leftparentparent-_leftcur){//特別處理2}elseif(gparent-_rightparentparent-_rightcur){//特別處理2}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}2.2.4 整體代碼boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// change colourwhile(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;//給uncle賦值if(gparent-_leftparent){unclegparent-_right;}else{unclegparent-_left;}//分情況特殊處理if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}//循環(huán)繼續(xù)的要點cur跟parent需要更新curgparent;parentcur-_parent;}_root-_colBLACK;returntrue;}為了保證_root是黑的最后可以直接不管三七二十一給它賦值一下。2.3 紅黑樹的驗證分別檢查4條規(guī)則。boolIsRBTree(){if(_rootnullptr){returntrue;}if(_root-_col!BLACK){returnfalse;}intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}return_check(_root,refNum,0);}先處理樹為空_root為空的情況。規(guī)則①檢查_root是否為黑。用refNum記錄一條路徑從_root到空結點的黑色結點備用。進入_check函數(shù)。bool_check(Node*root,constintrefNum,intblackNum){if(rootnullptr){if(blackNum!refNum){coutrefNum:refNum; blackNum:blackNumendl;returnfalse;}returntrue;}if(root-_colBLACK){blackNum;}elseif(root-_colRED){if(root-_parent-_colRED){coutred node has red parentendl;returnfalse;}}else{coutillegal colourendl;returnfalse;}return_check(root-_left,refNum,blackNum)_check(root-_right,refNum,blackNum);}進入函數(shù)先檢查root是否為空。規(guī)則④若為空則結束一條路徑需要檢查這條路徑的黑色結點數(shù)量blackNum是否與參考數(shù)量refNum相等。若不相等則違反規(guī)則④返回false相等則返回true。root不為空則判斷當前root是否為黑。root為黑則blackNum。規(guī)則③root為紅則判斷其parent是否為紅為紅違反規(guī)則③返回false。規(guī)則②若root既不為黑也不為紅違反規(guī)則②返回false。再遞歸檢查root-_left跟root-_right。2.4 紅黑樹的查找跟AVL樹一樣。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}直接照搬過來。2.5 紅黑樹的刪除2.5.1 刪除指定節(jié)點不細究比較復雜可以放一份思路步驟操作說明找真正刪除節(jié)點 y若 z 有兩個孩子用中序后繼替換也可用前驅最終 y 一定只有 0 或 1 個孩子。替換用 y 的孩子x可能為空頂替 y 的位置并記錄 y 在父節(jié)點中的左右方向isLeft。關鍵判斷只有刪除的節(jié)點y是黑色時才需要調用deleteFixup因為刪除紅節(jié)點不影響黑色路徑。修復循環(huán)核心是處理“雙黑”節(jié)點即替代上來的節(jié)點 x。1.兄弟為紅→ 旋轉父節(jié)點轉為兄弟為黑的情況。2.兄弟為黑且其兩個子節(jié)點均為黑→ 兄弟變紅將雙黑往上移。3.兄弟為黑且遠端侄子為黑近端為紅→ 旋轉兄弟轉為情況4。4.兄弟為黑且遠端侄子為紅→ 旋轉父節(jié)點并著色直接結束。收尾循環(huán)結束后將當前節(jié)點x涂黑若 x 為空則忽略徹底消去雙黑。2.5.2 析構加一個析構函數(shù)防止內存泄漏public://...~RBTree(){_Destroy(_root);_rootnullptr;}private:void_Destroy(Node*root){if(rootnullptr){return;}_Destroy(root-_left);_Destroy(root-_right);deleteroot;}//...輔助函數(shù)_Destroy寫在private區(qū)域以便遞歸銷毀。2.6 測試voidTestRBTree01(void){wyzy::RBTreeint,intt;//1測試用例不涉及雙旋//int a[] { 18, 10, 6, 15, 30, 25, 40 };//2測試用例涉及雙旋inta[]{18,10,6,15,30,25,40,27};for(autoe:a){t.Insert({e,e});}t.inOrder();t.preOrder();coutt.IsRBTree()endl;}測試代碼僅供參考。這里我寫了inOrder跟preOrder方便打印觀察。顏色打印出來0代表紅1代表黑。最終測試結果符合預期。紅黑樹的學習就到這里下一篇我們要 封裝紅黑樹 實現(xiàn)容器mymap跟myset 很快會更出來~