云深麋鹿專欄C | 用C語言學(xué)數(shù)據(jù)結(jié)構(gòu) | Java回顧上一篇我們結(jié)束了 AVLTree 的相關(guān)介紹接下來這篇文章讓我們進(jìn)入到 紅黑樹 的學(xué)習(xí)體會(huì)新的設(shè)計(jì)思路吧~放個(gè)目錄前言一 紅黑樹的概念1.1 紅黑樹的規(guī)則1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍1.3 紅黑樹的效率二 紅黑樹的實(shí)現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類Colour2.1.2 定義結(jié)點(diǎn)結(jié)構(gòu)體2.2 紅黑樹的插入2.2.1 特別處理1變色1簡單舉例2推廣到所有情況①來個(gè)抽象圖②情況1hb 01.介紹所處情況2.采取操作③情況2hb 11.介紹所處情況2.采取措施④情況3hb 21.介紹所處情況2.采取措施3代碼實(shí)現(xiàn)2.2.2 特別處理2單旋變色1 u不存在①介紹所處情況②采取操作2u存在且為黑①介紹所處情況②采取措施3代碼實(shí)現(xiàn)2.2.3 特別處理3雙旋變色1u不存在①介紹所處情況②采取措施2u存在且為黑①介紹所處情況②采取措施3代碼實(shí)現(xiàn)2.2.4 整體代碼2.3 紅黑樹的驗(yàn)證2.4 紅黑樹的查找2.5 紅黑樹的刪除2.5.1 刪除指定節(jié)點(diǎn)2.5.2 析構(gòu)2.6 測試前言摘要紅黑樹是一種自平衡的二叉搜索樹通過為每個(gè)結(jié)點(diǎn)增加顏色屬性并施加約束確保樹的高度始終保持在 O(logN) 級(jí)別。本文首先介紹紅黑樹的基本概念與四條核心規(guī)則分析其如何保證最長路徑不超過最短路徑的 2 倍并推導(dǎo)其增刪查改的時(shí)間復(fù)雜度為 O(logN)隨后以 C 為例從定義結(jié)點(diǎn)結(jié)構(gòu)開始逐步實(shí)現(xiàn)紅黑樹的插入變色、單旋變色、雙旋變色三種特別處理、驗(yàn)證、查找、刪除與析構(gòu)并附上測試用例驗(yàn)證正確性。最后總結(jié)紅黑樹的核心要點(diǎn)為后續(xù)封裝紅黑樹實(shí)現(xiàn) mymap 與 myset 容器打下基礎(chǔ)。一 紅黑樹的概念每個(gè)結(jié)點(diǎn)增加一個(gè)存儲(chǔ)位來表示結(jié)點(diǎn)的顏色可以是紅色或者黑色。通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)的顏色進(jìn)行約束紅黑樹確保沒有一條路徑會(huì)比其他路徑長出2倍因而是接近平衡的。1.1 紅黑樹的規(guī)則每個(gè)結(jié)點(diǎn)不是紅色就是黑色。根結(jié)點(diǎn)是黑色的。如果?個(gè)結(jié)點(diǎn)是紅色的則它的兩個(gè)孩子結(jié)點(diǎn)必須是黑色的也就是說任意一條路徑不會(huì)有連續(xù)的紅色結(jié)點(diǎn)。但可以有連續(xù)的黑色節(jié)點(diǎn)對(duì)于任意一個(gè)結(jié)點(diǎn)從該結(jié)點(diǎn)到其所有NULL結(jié)點(diǎn)的簡單路徑上均包含相同數(shù)量的黑色結(jié)點(diǎn)。下面來個(gè)動(dòng)圖演示一顆紅黑樹的形成上圖網(wǎng)址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html1.2 紅黑樹如何確保最長路徑不超過最短路徑的2倍從根到NULL結(jié)點(diǎn)的每條路徑都有相同數(shù)量的黑色結(jié)點(diǎn)。極端場景下最短路徑就就是全是黑色結(jié)點(diǎn)的路徑長度設(shè)為bh(black height)。最長的路徑就是?黑?紅間隔組成長度設(shè)為2*bh。理論上的最短路徑和最長路徑并不是在每棵紅黑樹都存在的。假設(shè)任意?條從根到NULL結(jié)點(diǎn)路徑的長度為h那么bh h 2*bh。1.3 紅黑樹的效率假設(shè)N是紅黑樹樹中結(jié)點(diǎn)數(shù)量h最短路徑的長度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN。關(guān)于N 2^(2*h) - 1為什么取不到等號(hào)存在最短路徑最長路徑的同時(shí)二叉樹不可能是滿二叉樹。假設(shè)h 1最短路徑為1最長路徑為2。N 取不到2^(2*h) - 1即3。最多只能取到如圖所示2個(gè)結(jié)點(diǎn)。也就是意味著紅黑樹增刪查改最壞也就是走最長路徑2*logN那么時(shí)間復(fù)雜度還是O(logN)。二 紅黑樹的實(shí)現(xiàn)2.1 定義紅黑樹2.1.1 枚舉類ColourenumColour{RED,BLACK};沒啥好說的紅黑樹就紅色或者黑色兩種結(jié)點(diǎn)。2.1.2 定義結(jié)點(diǎn)結(jié)構(gòu)體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樹類似只是多了個(gè)_col記錄顏色。這里和AVL樹一樣記錄了_parent方便后續(xù)旋轉(zhuǎn)。2.2 紅黑樹的插入為了保證每條路徑上的黑色結(jié)點(diǎn)數(shù)量相等沒有特殊情況的話新插入結(jié)點(diǎn)都為紅。紅黑樹為空插入結(jié)點(diǎn)為黑。插入結(jié)點(diǎn)的parent為黑插入結(jié)點(diǎn)為紅。插入結(jié)點(diǎn)的parent為紅插入結(jié)點(diǎn)為紅不符合規(guī)則特別處理。假設(shè)插入結(jié)點(diǎn)為cur插入結(jié)點(diǎn)的父母為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找到新結(jié)點(diǎn)應(yīng)當(dāng)插入位置parent記錄cur的_parent.最后構(gòu)造新結(jié)點(diǎn)把新結(jié)點(diǎn)賦值給cur讓其根據(jù)情況成為parent的左孩子或右孩子。其次若parent為紅需要特殊處理進(jìn)入循環(huán)。先定義gparent和uncle。注由于parent為紅而_root一定為黑所以gparent一定存在。極端情況為gparent恰好就是_root。2.2.1 特別處理1變色u存在且為紅只變色。1簡單舉例畫個(gè)栗圖插入cur后存在連續(xù)的紅色結(jié)點(diǎn)。則要實(shí)現(xiàn)的效果變色后cur更新為g向上檢查變色。2推廣到所有情況①來個(gè)抽象圖上圖的c可能不是新增結(jié)點(diǎn)而是從g變到c的設(shè)a、b是每條路徑擁有hb-1個(gè)黑色結(jié)點(diǎn)的根為紅色結(jié)點(diǎn)的子樹。設(shè)d、e、f是每條路徑擁有hb個(gè)黑色結(jié)點(diǎn)的子樹。②情況1hb 01.介紹所處情況a、b、d、e、f都是空子樹。如圖c還可以是下面白色結(jié)點(diǎn)位置之一c就是新插入結(jié)點(diǎn)上面的1簡單舉例就屬于這種情況。2.采取操作直接變色到③情況2hb 11.介紹所處情況c是由g變上來的Ⅰ則a、b是根結(jié)點(diǎn)為紅色的hb 0的子樹這樣。Ⅱ新增結(jié)點(diǎn)新增結(jié)點(diǎn)可能出現(xiàn)在4個(gè)位置即4個(gè)白色結(jié)點(diǎn)之一Ⅲd、e、f是根結(jié)點(diǎn)為黑色的hb 1的子樹四種情況。Ⅳ總結(jié)一共444*4 256種情況都是只需要變色就行。2.采取措施取其中一種情況分析明顯有連續(xù)的紅色結(jié)點(diǎn)不符合規(guī)則3需變色。最終效果再往上檢查④情況3hb 21.介紹所處情況Ⅰ則a、b是根結(jié)點(diǎn)為紅色的hb 1的子樹如圖4個(gè)位置的紅色結(jié)點(diǎn)可能存在或不存在。C(4,4) C(3,4) … C(0,4) 16所以子樹共有16種可能形態(tài)。Ⅱ新增結(jié)點(diǎn)16種形態(tài)一種形態(tài)下可新增結(jié)點(diǎn)的位置也很多是否會(huì)觸發(fā)變色也不一定。拿一個(gè)極端例子分析直接新增不觸發(fā)變色Ⅲd、e、f是根結(jié)點(diǎn)為黑色的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)。Ⅲ總結(jié)總共可能的情況數(shù)有百億往上。2.采取措施取其中一種情況分析變色c向上更新g變到c再繼續(xù)向上更新。3代碼實(shí)現(xiàn)//省略給uncle賦值部分代碼if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{//特別處理2}2.2.2 特別處理2單旋變色有兩種情況u不存在 或 存在且為黑。采取操作單旋下面舉例為需要右單旋的情況左單旋本質(zhì)上也是一樣的變色。1 u不存在①介紹所處情況u不存在則c一定是新增結(jié)點(diǎn)。因?yàn)槿绻鹀更新上來的c原來就得是黑的。c是黑的下圖中g(shù)的左子樹和右子樹黑色結(jié)點(diǎn)數(shù)量就不相同了。不符合規(guī)則4因此c不可能是更新上來的。②采取操作先以g為旋轉(zhuǎn)點(diǎn)右單旋再變色2u存在且為黑①介紹所處情況u存在且為黑則c一定是更新上來的。同樣反推如果c是新增節(jié)點(diǎn)a b子樹肯定為空。我們看新增前的樹p的右子樹為空d子樹也肯定為空子樹。先不論 e f 子樹是什么形態(tài)g的右子樹已經(jīng)比左子樹多了u這個(gè)黑色結(jié)點(diǎn)不符合規(guī)則4。因此c不可能是新增節(jié)點(diǎn)。在此基礎(chǔ)上我們先來看新增前的情況為保證規(guī)則4a b e f 四棵子樹黑色結(jié)點(diǎn)為hb-1個(gè)d子樹為hb個(gè)。a b是兩棵根結(jié)點(diǎn)為紅色的子樹。再來看新增后從新增結(jié)點(diǎn)更新上去a b子樹的根結(jié)點(diǎn)就變成了黑色上圖 a b d 子樹黑色結(jié)點(diǎn)為hb個(gè)e f子樹為hb-1個(gè)。②采取措施同樣先以g為旋轉(zhuǎn)點(diǎn)右單旋再變色3代碼實(shí)現(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不存在 或 存在且為黑。采取操作雙旋這里同樣只舉例先左單旋再右單旋另一種情況本質(zhì)上一樣變色。1u不存在①介紹所處情況c一定是新增結(jié)點(diǎn)這個(gè)推論跟單旋的情況一樣。②采取措施先以p為旋轉(zhuǎn)點(diǎn)左單旋變色再以g為旋轉(zhuǎn)點(diǎn)右單旋2u存在且為黑①介紹所處情況c同樣一定是更新上來的。新增結(jié)點(diǎn)前的樹為保證規(guī)則4d子樹黑色結(jié)點(diǎn)數(shù)量為hb a b e f 子樹為hb-1a b 子樹根結(jié)點(diǎn)為紅色。新增后假設(shè)新增結(jié)點(diǎn)在a子樹。更新上去到c變?yōu)榧t色a b子樹變?yōu)楦?jié)點(diǎn)為黑色的子樹。則現(xiàn)在 a b d 子樹黑色結(jié)點(diǎn)為hb個(gè)e f不變還是hb-1個(gè)。②采取措施先以p為旋轉(zhuǎn)點(diǎn)左單旋變色再以g為旋轉(zhuǎn)點(diǎn)右單旋最后的樹顯然符合規(guī)則4搞定。3代碼實(shí)現(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ù)的要點(diǎn)cur跟parent需要更新curgparent;parentcur-_parent;}_root-_colBLACK;returntrue;}為了保證_root是黑的最后可以直接不管三七二十一給它賦值一下。2.3 紅黑樹的驗(yàn)證分別檢查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到空結(jié)點(diǎn)的黑色結(jié)點(diǎn)備用。進(jìn)入_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);}進(jìn)入函數(shù)先檢查root是否為空。規(guī)則④若為空則結(jié)束一條路徑需要檢查這條路徑的黑色結(jié)點(diǎn)數(shù)量blackNum是否與參考數(shù)量refNum相等。若不相等則違反規(guī)則④返回false相等則返回true。root不為空則判斷當(dāng)前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é)點(diǎn)不細(xì)究比較復(fù)雜可以放一份思路步驟操作說明找真正刪除節(jié)點(diǎn) y若 z 有兩個(gè)孩子用中序后繼替換也可用前驅(qū)最終 y 一定只有 0 或 1 個(gè)孩子。替換用 y 的孩子x可能為空頂替 y 的位置并記錄 y 在父節(jié)點(diǎn)中的左右方向isLeft。關(guān)鍵判斷只有刪除的節(jié)點(diǎn)y是黑色時(shí)才需要調(diào)用deleteFixup因?yàn)閯h除紅節(jié)點(diǎn)不影響黑色路徑。修復(fù)循環(huán)核心是處理“雙黑”節(jié)點(diǎn)即替代上來的節(jié)點(diǎn) x。1.兄弟為紅→ 旋轉(zhuǎn)父節(jié)點(diǎn)轉(zhuǎn)為兄弟為黑的情況。2.兄弟為黑且其兩個(gè)子節(jié)點(diǎn)均為黑→ 兄弟變紅將雙黑往上移。3.兄弟為黑且遠(yuǎn)端侄子為黑近端為紅→ 旋轉(zhuǎn)兄弟轉(zhuǎn)為情況4。4.兄弟為黑且遠(yuǎn)端侄子為紅→ 旋轉(zhuǎn)父節(jié)點(diǎn)并著色直接結(jié)束。收尾循環(huán)結(jié)束后將當(dāng)前節(jié)點(diǎn)x涂黑若 x 為空則忽略徹底消去雙黑。2.5.2 析構(gòu)加一個(gè)析構(gòu)函數(shù)防止內(nèi)存泄漏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代表黑。最終測試結(jié)果符合預(yù)期。紅黑樹的學(xué)習(xí)就到這里下一篇我們要 封裝紅黑樹 實(shí)現(xiàn)容器mymap跟myset 很快會(huì)更出來~