在閱讀其他博主關于紅黑樹增刪實作的時候，博主們大多直接使用文字圖片描述，對整個增刪整體的流程突出的不太明顯（當然dalao們寫得還是很棒得，不然我也寫不出這篇文章），所以我特意花了2天時間用CAD制作了 一張插入操作的流程圖和一張洗掉操作的流程圖（洗掉見下篇）并手撕代碼（好吧，其實大部分時間在除錯代碼，畢竟talk is easy,show me the code.），
廢話不多說了，進入正題吧，
紅黑樹是一種常見而又有點復雜的資料結構，它的應用場景有很多，比如經典的JAVA的HashMap，當slot中元素大于8時就會樹化為紅黑樹，
和AVL樹一樣，紅黑樹也是一種二叉搜索樹（BST），但與AVL樹不同的是，紅黑樹通過稍微犧牲其平衡性（即榷訓了查找效率），并配合其特殊的規則（下面會說）以實作在增刪上的效率提升，即相比AVL樹，增刪一個節點最多只用旋轉三次，【紅黑樹：沒有什么是兩次旋轉不能解決的，如果有就三次
】
下面介紹以下紅黑樹的五個規則：
0、樹中節點不是紅色就是黑色；
1、根節點必為黑色；
2、紅色節點的父子不能也是紅色（或者說，由根至葉子的每一條路徑上不能有連續的紅節點）；
3、每個葉子節點（NIL節點）是黑色的
4、任意節點到其下方的NIL節點的每一條路徑上經過的黑色節點相同（或者說，除去紅色節點，黑色節點就是是一個AVL樹）；
5、在維護紅黑樹性質之前，對于新插入的節點，我們把它涂紅，【這其實只是一個經驗，另外，五條規則有六個不是常識么？】
接下來我們就用流程圖來梳理一下紅黑樹的插入操作：
但在此之前我們先規定下圖中一些代號節點的含義以及旋轉的操作：
C節點（Curent,當前要操作節點的指標）
P節點（Parent,當前C節點的父節點）
G節點（Grandparent,當前C節點的爺爺節點）
U節點（Uncle,當前C節點的叔叔節點，即P節點的兄弟節點）
【注意P、G、U節點應當隨著C的更新而更新】
旋轉： 以P為支點進行右旋為例——C頂替P的位置，P變為C的有右孩子，C原來的右孩子變為P的左孩子，左旋反向即可，
另外圖中白圈節點指代黑節點（畢竟CAD背景色是黑的嘛QAQ），紅圈節點就是紅節點，
最后附上代碼（由于增刪方法我是一起寫的，所以代碼中寫了洗掉方法的實作，洗掉方法的具體流程請參閱下篇）：
1 /** 2 * 手撕紅黑樹 3 * By 469の瘸子 （意義不明的口胡：現在應該是420の的瘸子233） 4 * **/ 5 public class RedBlackTree<E extends Comparable<E> & PrintToDOS> { 6 7 public static final boolean black = true; 8 public static final boolean red = false; 9 public Node root; 10 11 class Node {//節點類 12 public Node parent; 13 public Node left; 14 public Node right; 15 public E element; 16 public boolean color; 17 18 public Node (E element){//構造方法，默認新節點為紅色 19 this.element = element; 20 this.color =red; 21 } 22 23 //列印的紅黑樹的時候，會呼叫每個節點的列印方法 24 public void print(){ 25 //先列印顏色 26 if (this.color) { 27 System.out.print(" black:"); 28 }else { 29 System.out.print(" red:"); 30 } 31 //再列印值 32 element.print(); 33 //最后列印父節并換行 34 if(parent==null){ 35 System.out.println(" this is root"); 36 }else { 37 System.out.print(" parent is:"); 38 parent.element.println(); 39 } 40 } 41 42 } 43 44 //插入方法，會呼叫insert方法和fixAfterInsertion方法 45 public void insert(E element){ 46 //case1:樹中無元素，直接將elemnt插進去涂黑 47 if (root==null){ 48 root = new Node(element); 49 root.color = black; 50 }else{//case2:樹非空，先按二叉搜索樹的方式確定元素位置，再視父元素顏色分類處理 51 //先把節點插進去，如果插的元素已經存在會回傳null 52 Node node = insertBST(element); 53 //再對樹進行維護 54 fixAfterInsertion(node); 55 } 56 57 } 58 59 //該方法只負責將新的節點插進樹里，不負責維護紅黑樹性質 60 private Node insertBST(E element){ 61 Node pointer = root; 62 Node pointer_parent = null; 63 64 do{ 65 switch (element.compareTo(pointer.element)){ 66 case 0: 67 System.out.println("已有當前元素！"); 68 return null; 69 case 1: 70 pointer_parent = pointer; 71 pointer = pointer.right; 72 break; 73 case -1: 74 pointer_parent = pointer; 75 pointer = pointer.left; 76 break; 77 default: 78 break; 79 } 80 }while (pointer!=null); 81 82 Node child = new Node(element); 83 child.parent = pointer_parent; 84 85 //compareTo的結果只會是1或-1，不會出現0，是0的話，在上方的switch陳述句里就return了 86 if(pointer_parent.element.compareTo(element)>0){ 87 pointer_parent.left = child; 88 }else { 89 pointer_parent.right = child; 90 } 91 return child; 92 } 93 94 //該方法負責插入后的維護作業 95 private void fixAfterInsertion(Node node){ 96 Node cur,parent,grandparent,uncle; 97 cur = node; 98 //檢查是否需要維護樹,cur是null的話說明插的元素已存在，就不用維護了 99 if(cur !=null){ 100 parent = cur.parent; 101 //cur.print(); 102 //case2.1:父節點為黑色或為空，不用維護 103 if(parent==null||parent.color == black){ 104 return; 105 }else{//case2.2:父節點為紅色，視叔叔節點顏色分類處理 106 107 //region 先獲取U、G節點的參考（這里G必然非空，因為G空必然P為根且黑，那就不會執行到這里） 108 grandparent = parent.parent; 109 if(grandparent.left == parent){ 110 uncle = grandparent.right; 111 }else { 112 uncle = grandparent.left; 113 } 114 //endregion 115 116 //case2.2.1:U節點為黑色（NIL節點也是黑色的），視C、P、G節點的形態處理 117 if (uncle==null||uncle.color==black){ 118 //case2.2.1.1:C、P、G形態為“/”、“\”，以G為支點右旋或左旋，P變黑、G變紅 119 if(grandparent.element.compareTo(parent.element)==parent.element.compareTo(cur.element)){ 120 parent.color=black; 121 grandparent.color=red; 122 if(grandparent.element.compareTo(parent.element)>0){//“/”形態，右旋 123 rightRotate(grandparent); 124 }else {//“\”形態，左旋 125 leftRotate(grandparent); 126 } 127 }else {//case2.2.1.2:C、P、G形態為“<”、“>”，先以P為支點左旋或右旋，在以P為支點右旋或左旋 128 cur.color = black; 129 grandparent.color =red; 130 if(grandparent.element.compareTo(parent.element)>0){//“<”形態，P左旋后、G右旋 131 leftRotate(parent); 132 rightRotate(grandparent); 133 }else {//“>”形態，P右旋后、G左旋 134 rightRotate(parent); 135 leftRotate(grandparent); 136 } 137 } 138 }else {//case2.2.2:U節點為紅色，將P、G、U節點換色，然后cur指向G節點呼叫維護函式 139 grandparent.color=red; 140 parent.color=black; 141 uncle.color=black; 142 fixAfterInsertion(grandparent); 143 } 144 145 } 146 147 } 148 root.color=black; 149 } 150 151 //左旋方法 152 private void leftRotate(Node node){ 153 Node parent = node.parent; 154 Node child = node.right; 155 Node childLeft = child==null?null:child.left; 156 //子節點上位 157 if(parent==null){//支點為根節點，parent會是空 158 child.parent = null; 159 root = child; 160 }else { 161 if (parent.left == node){ 162 parent.left = child; 163 child.parent = parent; 164 }else { 165 parent.right = child; 166 child.parent = parent; 167 } 168 } 169 //父節點下位 170 child.left = node; 171 node.parent = child; 172 //子樹調整 173 node.right = childLeft; 174 if(childLeft!=null){ 175 childLeft.parent = node; 176 } 177 } 178 //右旋方法 179 private void rightRotate(Node node){ 180 Node parent = node.parent; 181 Node child = node.left; 182 Node childRight = child==null?null:child.right; 183 //子節點上位 184 if(parent==null){//支點為根節點，parent會是空 185 child.parent = null; 186 root = child; 187 }else {//支點不是根節點 188 if (parent.left == node){ 189 parent.left = child; 190 child.parent = parent; 191 }else { 192 parent.right = child; 193 child.parent = parent; 194 } 195 } 196 197 //父節點下位 198 child.right = node; 199 node.parent = child; 200 //子樹調整 201 node.left = childRight; 202 if(childRight!=null){ 203 childRight.parent = node; 204 } 205 } 206 207 //列印紅黑樹 208 public void printRBT(Node node){ 209 210 if(node!=null){ 211 printRBT(node.left); 212 node.print(); 213 printRBT(node.right); 214 }else { 215 return; 216 } 217 } 218 219 public static void main(String[] args) { 220 221 //13,8,5,11,6,22,27,25,14,17 另外一組除錯資料 222 int[] nums = {1,2,3,4,5,6,7,8,9,10}; 223 RedBlackTree<Element> redBlackTree = new RedBlackTree<Element> (); 224 225 for (int i: nums){ 226 Element element = new Element(i); 227 redBlackTree.insert(element); 228 } 229 //列印紅黑樹 230 redBlackTree.printRBT(redBlackTree.root); 231 232 //洗掉操作 233 int value = https://www.cnblogs.com/469Accelerator/p/3; 234 redBlackTree.remove(new Element(value)); 235 System.out.println("洗掉節點"+value+"后，列印："); 236 237 //列印紅黑樹 238 redBlackTree.printRBT(redBlackTree.root); 239 } 240 241 /**—————————— —— 分割線：以下是洗掉代碼 —————————————**/ 242 //從樹中洗掉一個元素的代碼 243 public void remove(E element){ 244 Node pointer = getNodeByElement(element); 245 if(pointer==null){ 246 System.out.print("樹中并沒有要洗掉的元素"); 247 return; 248 } 249 do { 250 //case1:要洗掉的節點僅有一個子樹，紅黑樹性質決定該情況下洗掉的必然是黑節點，且子節點為紅色葉子節點 251 if ((pointer.left==null)!=(pointer.right==null)) { 252 //要洗掉的節點的子樹（僅為一個紅色葉子節點）頂上來并變色 253 removeOneBranchNode(pointer); 254 return; 255 } else {//case2:洗掉節點為葉子節點 256 if ((pointer.left == null)&&(pointer.right == null)) { 257 removeLeafNode(pointer); 258 return; 259 } else {//case3:要洗掉的節點有兩個子樹 260 //指標指向后繼節點，后繼節點element頂替要洗掉的element，再do一次以判定新指標的case(此時只會是case2、3) 261 pointer = changePointer(pointer); 262 } 263 } 264 265 }while (true); 266 } 267 268 //獲取要洗掉的元素的Node，若回傳為null代表樹中沒有要洗掉的元素 269 public Node getNodeByElement(E element){ 270 if(root==null){//樹為空，回傳null 271 return null; 272 } 273 274 Node pointer = root; 275 do{ 276 if(element.compareTo(pointer.element)>0){//大于，指標指向右孩子 277 pointer = pointer.right; 278 }else { 279 if(element.compareTo(pointer.element)<0){//小于，指標指向左孩子 280 pointer = pointer.left; 281 }else {//等于，回傳當前的節點 282 return pointer; 283 } 284 } 285 }while (pointer!=null); 286 return null; 287 } 288 289 //指標指向后繼節點，并用后繼節點的element頂替要洗掉的element,沒有后繼節點就回傳null 290 public Node changePointer(Node pointer){ 291 //指標備份方便替換時找到參考 292 Node pointer_old = pointer; 293 //尋找后繼節點 294 pointer = pointer.right; 295 while (pointer.left!=null){ pointer = pointer.left; } 296 pointer_old.element=pointer.element; 297 return pointer; 298 } 299 300 //洗掉葉子節點，紅色的就直接刪，黑色的分情況處理 301 public void removeLeafNode(Node pointer){ 302 Node parent = pointer.parent; 303 Node pointer_old = pointer; 304 //case:2.1葉子節點是根節點 305 if(parent==null){ 306 root=null; 307 return; 308 } 309 //case:2.2葉子節點是紅色的的話直接洗掉，黑色的要分類處理 310 if(pointer.color==red){ 311 if(pointer.parent.left==pointer){ 312 pointer.parent.left=null; 313 }else { 314 pointer.parent.right=null; 315 } 316 }else { 317 //case2.3:葉子節點是黑色的,視兄弟點分類處理 318 while (pointer.parent!=null&&pointer.color==black){ 319 parent = pointer.parent;//在case2.3.2.2下回圈，要更新parent 320 Node brother; 321 if(pointer.parent.left==pointer){//左葉子節點處理方式 322 brother = pointer.parent.right; 323 //case2.3.1:兄弟節點為紅色，那么將其轉換為黑色 324 if(brother.color==red){ 325 brother.color = black; 326 parent.color = red; 327 leftRotate(parent); 328 brother = parent.right; 329 } 330 //case2.3.2:兄弟節點為黑色，侄子節點都是黑色（NIL） 331 if((brother.left == null)&&(brother.right == null)){ 332 //case2.3.2.1:父節點為紅色 333 if(parent.color==red){ 334 parent.color = black; 335 brother.color = red; 336 break; 337 }else {//case2.3.2.2:父節點為黑色 338 brother.color = red; 339 pointer = parent; 340 //繼續回圈 341 } 342 }else { 343 //case2.3.3:兄弟節點為黑色,左侄子為紅色 344 if((brother.color==black)&&brother.left!=null&&brother.left.color==red){ 345 brother.left.color = parent.color; 346 parent.color = black; 347 rightRotate(brother); 348 leftRotate(parent); 349 //case2.3.4:兄弟節點為黑色,右侄子為紅色 350 }else if((brother.color==black)&&brother.right!=null&&brother.right.color==red){ 351 brother.color = parent.color; 352 parent.color = black; 353 brother.right.color = black; 354 leftRotate(parent); 355 } 356 break; 357 } 358 }else {//右葉子節點處理方式 359 brother = pointer.parent.left; 360 //case2.3.1:兄弟節點為紅色，那么將其轉換為黑色 361 if(brother.color==red){ 362 brother.color = black; 363 parent.color = red; 364 rightRotate(parent); 365 brother = parent.left; 366 } 367 //case2.3.2:兄弟節點為黑色，侄子節點都是黑色（NIL） 368 if((brother.left == null)&&(brother.right == null)){ 369 //case2.3.2.1:父節點為紅色 370 if(parent.color==red){ 371 parent.color = black; 372 brother.color = red; 373 break; 374 }else {//case2.3.2.2:父節點為黑色 375 brother.color = red; 376 pointer = parent; 377 //繼續回圈 378 } 379 380 }else { 381 //case2.3.3:兄弟節點為黑色,右侄子為紅色 382 if((brother.color==black)&&brother.right!=null&&brother.right.color==red){ 383 brother.right.color = parent.color; 384 parent.color = black; 385 leftRotate(brother); 386 rightRotate(parent); 387 //case2.3.4:兄弟節點為黑色,左侄子為紅色 388 }else if((brother.color==black)&&brother.left!=null&&brother.left.color==red){ 389 brother.color = parent.color; 390 parent.color = black; 391 brother.left.color = black; 392 rightRotate(parent); 393 } 394 break; 395 } 396 } 397 } 398 //最后別忘了刪掉這個節點 399 if(pointer_old.parent.left == pointer_old){ 400 pointer_old.parent.left = null; 401 }else if((pointer_old.parent.right == pointer_old)){ 402 pointer_old.parent.right = null; 403 } 404 pointer_old.parent = null; 405 406 } 407 } 408 409 //洗掉單分支節點（此時洗掉節點必為紅色，子樹僅為一個葉子節點），子樹（就是一個葉子節點）頂上來涂黑即可， 410 public void removeOneBranchNode(Node pointer){ 411 Node child = pointer.left!=null?pointer.left:pointer.right; 412 if(pointer.parent.left==pointer){ 413 pointer.parent.left = child; 414 }else { 415 pointer.parent.right = child; 416 } 417 child.parent = pointer.parent; 418 child.color=black; 419 } 420 421 422 423 }
上文中泛型E的測驗用類及其列印介面：
1 public class Element implements Comparable<Element> ,PrintToDOS{ 2 3 public Element(int value){ 4 this.value =https://www.cnblogs.com/469Accelerator/p/ value; 5 } 6 7 public int value; 8 9 @Override 10 public void println() { 11 System.out.println(value); 12 } 13 14 @Override 15 public void print() { System.out.print(value); } 16 17 //this大于element回傳1，小于回傳-1，相等回傳0 18 @Override 19 public int compareTo(Element element) { 20 if (this.value>element.value){ 21 return 1; 22 }else { 23 if(this.value<element.value){ 24 return -1; 25 }else { 26 return 0; 27 } 28 } 29 } 30 }
列印介面：
1 public interface PrintToDOS { 2 public void print(); //列印值但不換行 3 public void println();//列印值后換行 4 }
初次發布的時候忘了加測驗結果了QAQ，補上：
最后，本文如有紕漏還請dalao們指正，（點擊這里閱讀下篇）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14506.html
標籤：其他