数据结构与算法（十三）——红黑树2

三、删除

1、介绍

　　红黑树的删除类似于排序二叉树，排序二叉树主要分为三种情况：
　　（1）删除没有左孩子且没有右孩子的结点。即：度为0。
　　（2）删除只有左（右）孩子的结点。即：度为1。
　　（3）删除有左孩子且有右孩子的结点。即：度为2。
　　由于红黑树还有颜色的区分，所以在上述三种情况的基础上加上颜色，就是六种情况。以 {15, 7, 45, 3, 10, 25, 55, 1, 5, 75} 为例：

　　 红黑树有六种情况：
　　（1）删除度为 0 的黑色结点。比如：10、25。
　　（2）删除度为 0 的红色结点。比如：1、5、75。
　　（3）删除度为 1 的黑色结点。比如：55。
　　（4）删除度为 1 的红色结点。这种情况不存在。
　　（5）删除度为 2 的黑色结点。比如：3、15。
　　（6）删除度为 2 的红色结点。比如：7、45。

2、说明

　　论证：度为 1 的红色结点，在红黑树中，是不存在的！
　　所有度为 1 的情况只有以下 4 种，这里都画的右孩子，左孩子也是同理。

　　其中：
　　"黑-黑"和"红-黑"，这两种情况，都不符合红黑树的性质（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
　　"红-红"，不符合红黑树的性质（5）所有红色结点的两个孩子结点必须是黑色（即，红色结点不能连续）。
　　只有"黑-红"这种情况存在。所以，度为 1 的结点，也必然是"黑-红"这种情况。

3、分析

　　情况（1）删除度为 0 的黑色结点：比较复杂，后面专门讨论。
　　情况（2）删除度为 0 的红色结点：直接删除即可。
　　情况（3）删除度为 1 的黑色结点：必然是"黑-红"的结构，则，删除当前结点（A），让孩子结点（B）代替A，并将B改为黑色。
　　情况（4）删除度为 1 的红色结点：这种情况不存在。
　　情况（5）删除度为 2 的黑色结点：
　　比如：删除 15，用其前驱10（后继也可以）的值代替15，再删除10（跳到情况1）即可。

　　比如：删除 15，用其前驱10（后继也可以）的值代替15，再删除10（跳到情况3）即可。

　　比如：删除 15，用其前驱12（后继也可以）的值代替15，再删除12（跳到情况2）即可。

　　情况（6）删除度为 2 的红色结点：同情况（5），不再赘述。
　　下面，专门讨论情况（1）删除度为 0 的黑色结点。为了方便描述，先约定一下结点名称。

 

　　由于树的左子树和右子树是对称的，所以只讨论一边的情况即可。不妨令待删除结点 C 为左孩子，右孩子的对称情况同理即可。

4、兄弟结点B是红

　　B是红：则 P 一定是黑色。BL、BR一定存在且是黑色。
　　调整方案：先对 P 左旋；然后B 和 P 互换颜色。（需注意旋转后，这里的 B 就不是 C 的兄弟结点。后面的描述不赘述）。此时跳转到下面 B（此时的B是BL，BL才是C的兄弟结点） 是黑的情况。

5、兄弟结点B是黑

　　B是黑：则孩子结点BL和BR要么不存在，要么存在且为红色。不可能是黑色的结点，这会违背性质（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
　　情况一：BR存在且为红，B的度为1。这里包含了度为2的情况。
　　调整方案：先对 P 左旋；然后B 和 P 互换颜色，将BR涂黑；最后直接删除C。

　　情况二：BR不存在，BL存在且为红，B的度为1。
　　调整方案：先对 B 右旋；然后BL 和 B 互换颜色；跳转到上面的情况一；

　　情况三：BL、BR都不存在，B的度为0。
　　调整方案：这里，又要分两种情况讨论，P是红色还是黑色？
　　（1）P是红色
　　调整方案：P 和 B 互换颜色；直接删除C。

　　（2）P是黑色
　　调整方案：将 B 涂红；直接删除C；将node指向 P，递归进行平衡调整（不再删除结点），直到 node 指向根 root 结点。
　　说明：最后一步有点不好理解。删除C后，P的左右子树黑色结点数相等了。但是经过P的路径，即：G（P的父结点）的左（右）子树黑色结点数会减 1。所以，需要递归调整 P。

6、代码

　　代码示例：完整的红黑树插入及删除

  1 public class RBTree<T extends Comparable<T>> {  2     // 根结点  3     private RBNode<T> root;  4   5     public RBTree() {  6     }  7   8     public RBTree(T[] arr) {  9         if (arr == null || arr.length == 0) { 10             return; 11         } 12  13         for (T i : arr) { 14             this.add(i); 15         } 16     } 17  18     // 查找结点 t 19     public RBNode<T> findRbNode(T t) { 20         return this.findRbNode(t, root); 21     } 22  23     private RBNode<T> findRbNode(T t, RBNode<T> node) { 24         if (t == null || node == null) { 25             return null; 26         } 27  28         if (t.compareTo(node.value) == 0) { 29             return node; 30         } 31         if (t.compareTo(node.value) < 0) { 32             return this.findRbNode(t, node.left); 33         } else { 34             return this.findRbNode(t, node.right); 35         } 36     } 37  38     // 查找结点 t 的前驱 39     private RBNode<T> precursor(T t) { 40         final RBNode<T> node = this.findRbNode(t); 41         if (node == null) { 42             return null; 43         } 44         return this.precursor(node); 45     } 46  47     private RBNode<T> precursor(RBNode<T> node) { 48         // 左子树的最大值 49         if (node.left != null) { 50             RBNode<T> t = node.left; 51             while (t.right != null) { 52                 t = t.right; 53             } 54             return t; 55         } else { 56             // 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的. 57             RBNode<T> temp = node.parent; 58             RBNode<T> ch = node; 59             while (temp != null && ch == temp.left) { 60                 ch = temp; 61                 temp = temp.parent; 62             } 63  64             return temp; 65         } 66     } 67  68     // 查找结点 t 的后继 69     private RBNode<T> successor(T t) { 70         final RBNode<T> node = this.findRbNode(t); 71         if (node == null) { 72             return null; 73         } 74         return this.successor(node); 75     } 76  77     private RBNode<T> successor(RBNode<T> node) { 78         // 右子树的最小值 79         if (node.right != null) { 80             RBNode<T> t = node.right; 81             while (t.left != null) { 82                 t = t.left; 83             } 84             return t; 85         } else { 86             // 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的. 87             RBNode<T> temp = node.parent; 88             RBNode<T> ch = node; 89             while (temp != null && ch == temp.right) { 90                 ch = temp; 91                 temp = temp.parent; 92             } 93  94             return temp; 95         } 96     } 97  98     public void delete(T value) { 99         final RBNode<T> node = this.findRbNode(value);100         if (node == null) {101             System.out.println("待删除的结点:" + value + " 不存在~");102             return;103         }104 105         this.delNode(node);106     }107 108     private void delNode(RBNode<T> node) {109         final int degree = node.getDegree();110         // 度为 0111         if (degree == 0) {112             // 1.红色.直接删113             if (node.red) {114                 this.freeDegree0(node);115             } else {116                 // 2.黑色117                 if (node == root) {118                     this.freeDegree0(node);119                 } else {120                     this.delBlackNode(node);121                 }122             }123         } else if (degree == 1) {124             // 度为 1.一定是 "黑-红"125             if (node.left != null) {126                 node.value = node.left.value;127                 node.left = null;128             } else {129                 node.value = node.right.value;130                 node.right = null;131             }132         } else {133             // 度为 2134             final RBNode<T> precursor = this.precursor(node);135             node.value = precursor.value;136             this.delNode(precursor);137         }138     }139 140     /* 删除度为 1 的黑色结点 */141     private void delBlackNode(RBNode<T> node) {142         RBNode<T> temp = node;143 144         // 递归调整145         while (temp != root) {146             final RBNode<T> p = temp.parent;147             final RBNode<T> brother = temp.getBrother();148 149             // 兄弟 B是红150             if (brother.red) {151                 this.adjustCase1(temp); // 经过adjustCase1后,兄弟是黑色152             } else {153                 // 兄弟 B是黑 .有孩子154                 if (brother.left != null || brother.right != null) {155                     if (temp == p.left) {156                         if (brother.right != null) {157                             this.adjustCase2(temp);158                         } else {159                             this.adjustCase3(temp);160                         }161                     } else {162                         if (brother.left != null) {163                             this.adjustCase2(temp);164                         } else {165                             this.adjustCase3(temp);166                         }167                     }168 169                     break;170                 } else {171                     // C-黑.兄弟 B是黑. 且没有孩子172                     // p-红173                     if (p.red) {174                         brother.red = true;175                         p.red = false;176                         this.freeDegree0(temp);177                         break;178                     } else {179                         // p-黑180                         brother.red = true;181                         this.freeDegree0(temp);182                         temp = p;183                     }184                 }185             }186         }187     }188 189     // C-黑. B-红190     private void adjustCase1(RBNode<T> node) {191         final RBNode<T> p = node.parent;192         // 左孩子.(左右对称的)193         if (node == p.left) {194             this.leftRotate(p);195         } else {196             this.rightRotate(p);197         }198 199         node.parent.red = true;200         node.parent.parent.red = false;201     }202 203     // C-黑. B-黑. BR-红 (远侄子)204     private void adjustCase2(RBNode<T> node) {205         final RBNode<T> p = node.parent;206         if (node == p.left) {207             this.leftRotate(p);208 209             // B、P颜色互换210             node.parent.parent.red = node.parent.red;211             node.parent.red = false;212             // 涂黑远侄子213             node.parent.parent.right.red = false;214         } else {215             this.rightRotate(p);216 217             // B、P颜色互换218             node.parent.parent.red = node.parent.red;219             node.parent.red = false;220             // 涂黑远侄子221             node.parent.parent.left.red = false;222         }223         this.freeDegree0(node);224     }225 226     // C-黑. B-黑. BR-不存在. BL-红 (近侄子)227     private void adjustCase3(RBNode<T> node) {228         final RBNode<T> p = node.parent;229         final RBNode<T> brother = node.getBrother();230         // C 是左孩子.BL-红 (近侄子)231         if (brother.left != null) {232             rightRotate(brother);233         } else {234             // C 是右孩子.BR-红 (近侄子)235             leftRotate(brother);236         }237 238         // BL 和 B 互换颜色239         brother.red = true;240         brother.parent.red = false;241 242         // 跳转到adjustCase2243         this.adjustCase2(p);244     }245 246     // 直接删除度为 0 的结点 node247     private void freeDegree0(RBNode<T> node) {248         final RBNode<T> p = node.parent;249         // 待删除结点 node 就是root250         if (p == null) {251             root = null;252             return;253         }254 255         if (node == p.left) {256             p.left = null;257         } else {258             p.right = null;259         }260     }261 262     // 添加结点263     public void add(T value) {264         RBNode<T> newNode = new RBNode<>(value);265         if (root == null) {266             root = newNode;267             newNode.red = false;268             return;269         }270 271         // 1.添加272         this.add(root, newNode);273 274         // 2.调整275         this.fixUp(newNode);276     }277 278     private void fixUp(RBNode<T> newNode) {279         if (newNode == root) {280             newNode.red = false;281             return;282         }283 284         // newNode 的父结点为黑色285         if (!newNode.parent.red) {286             return;287         }288 289         /* 1.newNode 的叔叔结点存在且为红色。*/290         final RBNode<T> uncle = newNode.getUncle();291         if (uncle != null && uncle.red) {292             newNode.parent.red = false;293             uncle.red = false;294 295             newNode.parent.parent.red = true;296             this.fixUp(newNode.parent.parent);297         } else {298             /* 2.newNode 的叔叔结点不存在，或者为黑色。*/299             final RBNode<T> grandFather = newNode.getGrandFather();300             // 2.1左左301             if (newNode == grandFather.left.left) {302                 this.rightRotate(grandFather);303                 newNode.parent.red = false;304                 grandFather.red = true;305             }306             // 2.2左右307             else if (newNode == grandFather.left.right) {308                 this.leftRotate(newNode.parent);309                 this.rightRotate(grandFather);310                 newNode.red = false;311                 grandFather.red = true;312             }313             // 2.3右右314             else if (newNode == grandFather.right.right) {315                 this.leftRotate(grandFather);316                 newNode.parent.red = false;317                 grandFather.red = true;318             }319             // 2.4右左320             else if (newNode == grandFather.right.left) {321                 this.rightRotate(newNode.parent);322                 this.leftRotate(grandFather);323                 newNode.red = false;324                 grandFather.red = true;325             }326         }327     }328 329     // 按 排序二叉树 的规则插入结点330     private void add(RBNode<T> root, RBNode<T> newNode) {331         if (newNode.value.compareTo(root.value) <= 0) {332             if (root.left == null) {333                 root.left = newNode;334                 newNode.parent = root;335             } else {336                 this.add(root.left, newNode);337             }338         } else {339             if (root.right == null) {340                 root.right = newNode;341                 newNode.parent = root;342             } else {343                 this.add(root.right, newNode);344             }345         }346     }347 348     // 左旋349     private void leftRotate(RBNode<T> node) {350         if (node == null) {351             return;352         }353         final RBNode<T> p = node.parent;354 355         // 左旋. 应该认为 temp 不为null356         final RBNode<T> temp = node.right;357         node.right = temp.left;358         if (temp.left != null) {359             // 该结点可能不存在360             temp.left.parent = node;361         }362 363         temp.left = node;364         node.parent = temp;365 366         // 旋转完成.修正根结点与父结点367         // 1.node为根结点368         if (node == root) {369             root = temp;370             temp.parent = null;371             return;372         }373 374         // 2.node不为根结点375         // node 为父结点的右孩子376         if (node == p.right) {377             p.right = temp;378         } else {379             p.left = temp;380         }381         temp.parent = p;382     }383 384     // 右旋385     private void rightRotate(RBNode<T> node) {386         if (node == null) {387             return;388         }389 390         final RBNode<T> p = node.parent;391 392         // 右旋. 应该认为 temp 不为null393         final RBNode<T> temp = node.left;394         node.left = temp.right;395         if (temp.right != null) {396             // 该结点可能不存在397             temp.right.parent = node;398         }399 400         temp.right = node;401         node.parent = temp;402 403         // 旋转完成.修正根结点与父结点404         // 1.node为根结点405         if (node == root) {406             root = temp;407             temp.parent = null;408             return;409         }410 411         // 2.node不为根结点412         // node 为父结点的右孩子413         if (node == p.right) {414             p.right = temp;415         } else {416             p.left = temp;417         }418         temp.parent = p;419     }420 421     // 中序遍历422     public void infixOrder() {423         this.infixOrder(root);424     }425 426     private void infixOrder(RBNode<T> root) {427         if (root != null) {428             this.infixOrder(root.left);429             System.out.print("-->" + root.value + ":" + (root.red ? "红" : "黑"));430             this.infixOrder(root.right);431         }432     }433 434     /**435      * 红黑树 树结点结构436      */437     protected static class RBNode<T extends Comparable<T>> {438         private T value;439         // 默认为 红色 结点440         private boolean red = true;441 442         private RBNode<T> left;443         private RBNode<T> right;444         private RBNode<T> parent;445 446         public RBNode() {447         }448 449         public RBNode(T value) {450             this.value = value;451         }452 453         // 返回结点的度454         public int getDegree() {455             if (this.left == null && this.right == null) {456                 return 0;457             }458 459             if ((this.left != null && this.right == null) || (this.left == null && this.right != null)) {460                 return 1;461             }462 463             return 2;464         }465 466         public RBNode<T> getUncle() {467             final RBNode<T> grandFather = this.parent.parent;468             final RBNode<T> parent = this.parent;469 470             if (parent == grandFather.left) {471                 return grandFather.right;472             }473 474             if (parent == grandFather.right) {475                 return grandFather.left;476             }477 478             return null;479         }480 481         public RBNode<T> getGrandFather() {482             return this.parent.parent;483         }484 485         public RBNode<T> getBrother() {486             final RBNode<T> p = this.parent;487 488             return this == p.left ? p.right : p.left;489         }490 491         @Override492         public String toString() {493             return "RBNode{" +494                     "value=" + value +495                     ", red=" + red +496                     '}';497         }498     }499 }

完整的红黑树插入及删除

　　代码示例：测试

 1 public class Main { 2     public static void main(String[] args) { 3         // Integer[] integers = {15, 7, 45, 3, 10, 25, 55, 1, 5, 75}; 4         Integer[] integers = {500, 100, 750, 25, 300, 550, 800, 15, 50, 520, 600, 510}; 5         RBTree<Integer> tree = new RBTree<>(integers); 6         tree.infixOrder(); 7  8         tree.delete(300); 9         System.out.println("");10         tree.infixOrder();11     }12 }

　　最后，推荐一个在线构建红黑树的地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html  用于读者验证上述代码的结果。上述测试案例构建的红黑树为：