数据结构之红黑树

朴灿烈づ我的快乐病毒、 2022-01-27 08:05 274阅读 0赞

2-3树和红黑树相关学习：

红黑树和2-3树本身是等价的,在学习红黑树之前我们不妨去了解一下2-3树的特性。当我们理解了2-3树之后，对于红黑树和通常用于磁盘存储，文件系统，数据库相应的B类树也是有帮助的。

## 2-3树 ##

2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树(满足二分搜索树的基本性质)，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。

![20190523223433.png][]

![20190523220039.png][]

b的左孩子点小于b的值，bc中间的值再bc之间，c的右孩子的值大于c。

![20190523220622.png][]

2-3树是一颗绝对平衡的树：从根节点到任意一个节点所经过的节点数量一定是相同的

### 插入 ###

如果插入2-节点那么

![20190523222021.png][]

如果插入3-节点

![20190523222055.png][]

如果插入3-节点，父亲节点为2-节点的话

![20190523222740.png][]

如果插入3-节点，父亲节点也为3-节点

![20190523222843.png][]

## 红黑树 ##

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为`对称二叉B树`，它现代的名字源于LeoJ. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 $\\mathrm\{O\}(\\log n)$时间内完成查找，插入和删除，这里的$n$是树中元素的数目。

### 性质 ###

1.  节点是红色或黑色。
2.  根是黑色。
3.  所有叶子都是黑色（叶子是NIL节点）。
4.  每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5.  从任一节点到其每个叶子的所有`简单路径`都包含相同数目的黑色节点。

![20190523224136.png][]

### Java实现 ###

红黑树的基本操作是**添加**、**删除**和**旋转**。在对红黑树进行添加或删除后，会用到旋转方法。添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树，旋转的目的是让树保持红黑树的特性。  
旋转包括两种：**左旋** 和 **右旋**。

#### 基本定义 ####

#### 左旋 ####

![20190524115121.png][]

对x进行左旋，意味着”将x变成一个左节点”。

#### 右旋 ####

![20190524115243.png][]

对y进行左旋，意味着”将y变成一个右节点”。

#### 添加 ####

将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过”旋转和重新着色”等一系列操作来修正该树，使之重新成为一颗红黑树。详细描述如下：  
**第一步: 将红黑树当作一颗二叉查找树，将节点插入。**  
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。  
好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！

**第二步：将插入的节点着色为”红色”。**  
为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：  
(1) 每个节点或者是黑色，或者是红色。  
(2) 根节点是黑色。  
(3) 每个叶子节点是黑色。 \[注意：这里叶子节点，是指为空的叶子节点！\]  
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。  
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。  
将插入的节点着色为红色，不会违背”特性(5)”！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o…哈哈

**第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。**  
第二步中，将插入节点着色为”红色”之后，不会违背”特性(5)”。那它到底会违背哪些特性呢？  
对于”特性(1)”，显然不会违背了。因为我们已经将它涂成红色了。  
对于”特性(2)”，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。  
对于”特性(3)”，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。  
对于”特性(4)”，是有可能违背的！  
那接下来，想办法使之”满足特性(4)”，就可以将树重新构造成红黑树了。

**内部接口** — insert(node)的作用是将”node”节点插入到红黑树中。  
**外部接口** — insert(key)的作用是将”key”添加到红黑树中。

#### 平衡 ####

#### 删除 ####

将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：  
**第一步：将红黑树当作一颗二叉查找树，将节点删除。**  
这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：  
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。  
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。  
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况① “进行处理；若只有一个儿子，则按”情况② “进行处理。

**第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。**  
因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树

**内部接口** — remove(node)的作用是将”node”节点插入到红黑树中。  
**外部接口** — remove(key)删除红黑树中键值为key的节点。

#### 平衡 ####

removeFixup(node, parent)是对应”上面所讲的第三步”。它是一个内部接口。

### 完整代码 ###

<table> 
 <tbody> 
 <tr> 
 <td><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 </pre></td> 
 <td><pre>/** * Java 语言: 红黑树 * * @author skywang * @date 2013/11/07 */ public class RBTree&lt;T extends Comparable&lt;T&gt;&gt; {
 private RBTNode&lt;T&gt; mRoot; // 根结点 private static final boolean RED = false; private static final boolean BLACK = true; public class RBTNode&lt;T extends Comparable&lt;T&gt;&gt; {
 boolean color; // 颜色 T key; // 关键字(键值) RBTNode&lt;T&gt; left; // 左孩子 RBTNode&lt;T&gt; right; // 右孩子 RBTNode&lt;T&gt; parent; // 父结点 public RBTNode(T key, boolean color, RBTNode&lt;T&gt; parent, RBTNode&lt;T&gt; left, RBTNode&lt;T&gt; right) {
 this.key = key; this.color = color; this.parent = parent; this.left = left; this.right = right; } public T getKey() {
 return key; } public String toString() {
 return ""+key+(this.color==RED?"(R)":"B"); } } public RBTree() {
 mRoot=null; } private RBTNode&lt;T&gt; parentOf(RBTNode&lt;T&gt; node) {
 return node!=null ? node.parent : null; } private boolean colorOf(RBTNode&lt;T&gt; node) {
 return node!=null ? node.color : BLACK; } private boolean isRed(RBTNode&lt;T&gt; node) {
 return ((node!=null)&amp;&amp;(node.color==RED)) ? true : false; } private boolean isBlack(RBTNode&lt;T&gt; node) {
 return !isRed(node); } private void setBlack(RBTNode&lt;T&gt; node) {
 if (node!=null) node.color = BLACK; } private void setRed(RBTNode&lt;T&gt; node) {
 if (node!=null) node.color = RED; } private void setParent(RBTNode&lt;T&gt; node, RBTNode&lt;T&gt; parent) {
 if (node!=null) node.parent = parent; } private void setColor(RBTNode&lt;T&gt; node, boolean color) {
 if (node!=null) node.color = color; } /* * 前序遍历"红黑树" */ private void preOrder(RBTNode&lt;T&gt; tree) {
 if(tree != null) {
 System.out.print(tree.key+" "); preOrder(tree.left); preOrder(tree.right); } } public void preOrder() {
 preOrder(mRoot); } /* * 中序遍历"红黑树" */ private void inOrder(RBTNode&lt;T&gt; tree) {
 if(tree != null) {
 inOrder(tree.left); System.out.print(tree.key+" "); inOrder(tree.right); } } public void inOrder() {
 inOrder(mRoot); } /* * 后序遍历"红黑树" */ private void postOrder(RBTNode&lt;T&gt; tree) {
 if(tree != null) {
 postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+" "); } } public void postOrder() {
 postOrder(mRoot); } /* * (递归实现)查找"红黑树x"中键值为key的节点 */ private RBTNode&lt;T&gt; search(RBTNode&lt;T&gt; x, T key) {
 if (x==null) return x; int cmp = key.compareTo(x.key); if (cmp &lt; 0) return search(x.left, key); else if (cmp &gt; 0) return search(x.right, key); else return x; } public RBTNode&lt;T&gt; search(T key) {
 return search(mRoot, key); } /* * (非递归实现)查找"红黑树x"中键值为key的节点 */ private RBTNode&lt;T&gt; iterativeSearch(RBTNode&lt;T&gt; x, T key) {
 while (x!=null) {
 int cmp = key.compareTo(x.key); if (cmp &lt; 0) x = x.left; else if (cmp &gt; 0) x = x.right; else return x; } return x; } public RBTNode&lt;T&gt; iterativeSearch(T key) {
 return iterativeSearch(mRoot, key); } /* * 查找最小结点：返回tree为根结点的红黑树的最小结点。 */ private RBTNode&lt;T&gt; minimum(RBTNode&lt;T&gt; tree) {
 if (tree == null) return null; while(tree.left != null) tree = tree.left; return tree; } public T minimum() {
 RBTNode&lt;T&gt; p = minimum(mRoot); if (p != null) return p.key; return null; } /* * 查找最大结点：返回tree为根结点的红黑树的最大结点。 */ private RBTNode&lt;T&gt; maximum(RBTNode&lt;T&gt; tree) {
 if (tree == null) return null; while(tree.right != null) tree = tree.right; return tree; } public T maximum() {
 RBTNode&lt;T&gt; p = maximum(mRoot); if (p != null) return p.key; return null; } /* * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。 */ public RBTNode&lt;T&gt; successor(RBTNode&lt;T&gt; x) {
 // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。 if (x.right != null) return minimum(x.right); // 如果x没有右孩子。则x有以下两种可能： // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 RBTNode&lt;T&gt; y = x.parent; while ((y!=null) &amp;&amp; (x==y.right)) {
 x = y; y = y.parent; } return y; } /* * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。 */ public RBTNode&lt;T&gt; predecessor(RBTNode&lt;T&gt; x) {
 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x.left != null) return maximum(x.left); // 如果x没有左孩子。则x有以下两种可能： // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 RBTNode&lt;T&gt; y = x.parent; while ((y!=null) &amp;&amp; (x==y.left)) {
 x = y; y = y.parent; } return y; } /* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-. / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ private void leftRotate(RBTNode&lt;T&gt; x) {
 // 设置x的右孩子为y RBTNode&lt;T&gt; y = x.right; // 将 “y的左孩子” 设为 “x的右孩子”； // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲” x.right = y.left; if (y.left != null) y.left.parent = x; // 将 “x的父亲” 设为 “y的父亲” y.parent = x.parent; if (x.parent == null) {
 this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点 } else {
 if (x.parent.left == x) x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” else x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” } // 将 “x” 设为 “y的左孩子” y.left = x; // 将 “x的父节点” 设为 “y” x.parent = y; } /* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)-. / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */ private void rightRotate(RBTNode&lt;T&gt; y) {
 // 设置x是当前节点的左孩子。 RBTNode&lt;T&gt; x = y.left; // 将 “x的右孩子” 设为 “y的左孩子”； // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲” y.left = x.right; if (x.right != null) x.right.parent = y; // 将 “y的父亲” 设为 “x的父亲” x.parent = y.parent; if (y.parent == null) {
 this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 } else {
 if (y == y.parent.right) y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” else y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x.right = y; // 将 “y的父节点” 设为 “x” y.parent = x; } /* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的z */ private void insertFixUp(RBTNode&lt;T&gt; node) {
 RBTNode&lt;T&gt; parent, gparent; // 若“父节点存在，并且父节点的颜色是红色” while (((parent = parentOf(node))!=null) &amp;&amp; isRed(parent)) {
 gparent = parentOf(parent); //若“父节点”是“祖父节点的左孩子” if (parent == gparent.left) {
 // Case 1条件：叔叔节点是红色 RBTNode&lt;T&gt; uncle = gparent.right; if ((uncle!=null) &amp;&amp; isRed(uncle)) {
 setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是右孩子 if (parent.right == node) {
 RBTNode&lt;T&gt; tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是左孩子。 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若“z的父节点”是“z的祖父节点的右孩子” // Case 1条件：叔叔节点是红色 RBTNode&lt;T&gt; uncle = gparent.left; if ((uncle!=null) &amp;&amp; isRed(uncle)) {
 setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是左孩子 if (parent.left == node) {
 RBTNode&lt;T&gt; tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是右孩子。 setBlack(parent); setRed(gparent); leftRotate(gparent); } } // 将根节点设为黑色 setBlack(this.mRoot); } /* * 将结点插入到红黑树中 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的node */ private void insert(RBTNode&lt;T&gt; node) {
 int cmp; RBTNode&lt;T&gt; y = null; RBTNode&lt;T&gt; x = this.mRoot; // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。 while (x != null) {
 y = x; cmp = node.key.compareTo(x.key); if (cmp &lt; 0) x = x.left; else x = x.right; } node.parent = y; if (y!=null) {
 cmp = node.key.compareTo(y.key); if (cmp &lt; 0) y.left = node; else y.right = node; } else {
 this.mRoot = node; } // 2. 设置节点的颜色为红色 node.color = RED; // 3. 将它重新修正为一颗二叉查找树 insertFixUp(node); } /* * 新建结点(key)，并将其插入到红黑树中 * * 参数说明： * key 插入结点的键值 */ public void insert(T key) {
 RBTNode&lt;T&gt; node=new RBTNode&lt;T&gt;(key,BLACK,null,null,null); // 如果新建结点失败，则返回。 if (node != null) insert(node); } /* * 红黑树删除修正函数 * * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 待修正的节点 */ private void removeFixUp(RBTNode&lt;T&gt; node, RBTNode&lt;T&gt; parent) {
 RBTNode&lt;T&gt; other; while ((node==null || isBlack(node)) &amp;&amp; (node != this.mRoot)) {
 if (parent.left == node) {
 other = parent.right; if (isRed(other)) {
 // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); leftRotate(parent); other = parent.right; } if ((other.left==null || isBlack(other.left)) &amp;&amp; (other.right==null || isBlack(other.right))) {
 // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else {
 if (other.right==null || isBlack(other.right)) {
 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.left); setRed(other); rightRotate(other); other = parent.right; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.right); leftRotate(parent); node = this.mRoot; break; } } else {
 other = parent.left; if (isRed(other)) {
 // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); rightRotate(parent); other = parent.left; } if ((other.left==null || isBlack(other.left)) &amp;&amp; (other.right==null || isBlack(other.right))) {
 // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else {
 if (other.left==null || isBlack(other.left)) {
 // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.right); setRed(other); leftRotate(other); other = parent.left; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.left); rightRotate(parent); node = this.mRoot; break; } } } if (node!=null) setBlack(node); } /* * 删除结点(node)，并返回被删除的结点 * * 参数说明： * node 删除的结点 */ private void remove(RBTNode&lt;T&gt; node) {
 RBTNode&lt;T&gt; child, parent; boolean color; // 被删除节点的"左右孩子都不为空"的情况。 if ( (node.left!=null) &amp;&amp; (node.right!=null) ) {
 // 被删节点的后继节点。(称为"取代节点") // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 RBTNode&lt;T&gt; replace = node; // 获取后继节点 replace = replace.right; while (replace.left != null) replace = replace.left; // "node节点"不是根节点(只有根节点不存在父节点) if (parentOf(node)!=null) {
 if (parentOf(node).left == node) parentOf(node).left = replace; else parentOf(node).right = replace; } else {
 // "node节点"是根节点，更新根节点。 this.mRoot = replace; } // child是"取代节点"的右孩子，也是需要"调整的节点"。 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 child = replace.right; parent = parentOf(replace); // 保存"取代节点"的颜色 color = colorOf(replace); // "被删除节点"是"它的后继节点的父节点" if (parent == node) {
 parent = replace; } else {
 // child不为空 if (child!=null) setParent(child, parent); parent.left = child; replace.right = node.right; setParent(node.right, replace); } replace.parent = node.parent; replace.color = node.color; replace.left = node.left; node.left.parent = replace; if (color == BLACK) removeFixUp(child, parent); node = null; return ; } if (node.left !=null) {
 child = node.left; } else {
 child = node.right; } parent = node.parent; // 保存"取代节点"的颜色 color = node.color; if (child!=null) child.parent = parent; // "node节点"不是根节点 if (parent!=null) {
 if (parent.left == node) parent.left = child; else parent.right = child; } else {
 this.mRoot = child; } if (color == BLACK) removeFixUp(child, parent); node = null; } /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * tree 红黑树的根结点 * z 删除的结点 */ public void remove(T key) {
 RBTNode&lt;T&gt; node; if ((node = search(mRoot, key)) != null) remove(node); } /* * 销毁红黑树 */ private void destroy(RBTNode&lt;T&gt; tree) {
 if (tree==null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; } public void clear() {
 destroy(mRoot); mRoot = null; } /* * 打印"红黑树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(RBTNode&lt;T&gt; tree, T key, int direction) {
 if(tree != null) {
 if(direction==0) // tree是根节点 System.out.printf("%2d(B) is root\n", tree.key); else // tree是分支节点 System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left"); print(tree.left, tree.key, -1); print(tree.right,tree.key, 1); } } public void print() {
 if (mRoot != null) print(mRoot, mRoot.key, 0); } } </pre></td> 
 </tr> 
 </tbody> 
</table>

### 测试 ###

![20190524205857.png][]

![E7_BA_A2_E9_BB_91_E6_A0_91_E6_8F_92_E5_85_A5.gif][]

## 参考资料 ##

《玩转数据结构》

[https://www.cnblogs.com/skywang12345/p/3624343.html][https_www.cnblogs.com_skywang12345_p_3624343.html]

[20190523223433.png]: /images/20220127/a25beb99fc3747b0970f77908bac42f2.png
[20190523220039.png]: https://hphimages-1253879422.cos.ap-beijing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%A0%91/%E7%BA%A2%E9%BB%91%E6%A0%91/20190523220039.png
[20190523220622.png]: /images/20220127/420f73e42c1944f3a7b6e69f98f0b8dc.png
[20190523222021.png]: /images/20220127/edab9fcbb6c54794a4bf3df78b624586.png
[20190523222055.png]: /images/20220127/d0923423da9940b99ed3548d2ed880f7.png
[20190523222740.png]: /images/20220127/6818a44cacaf4504b3fa38bff25f3aca.png
[20190523222843.png]: /images/20220127/e2108305e6434b9b921531ccc6f74183.png
[20190523224136.png]: /images/20220127/f965c827a351496ab9a777fc5274bbb4.png
[20190524115121.png]: /images/20220127/48c0817d46ea48f4bfa5d1edff68753d.png
[20190524115243.png]: /images/20220127/5845501cb7e54aa28b45ab9718b44241.png
[20190524205857.png]: /images/20220127/c12e2a856ede494497618f1ecb97cc5d.png
[E7_BA_A2_E9_BB_91_E6_A0_91_E6_8F_92_E5_85_A5.gif]: /images/20220127/d6943dc86050496e86d1418d41b72cfc.png
[https_www.cnblogs.com_skywang12345_p_3624343.html]: https://www.cnblogs.com/skywang12345/p/3624343.html