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、代码
代码示例：完整的红黑树插入及删除
1publicclass RBTree<Textends Comparable<T>> { 2// 根结点 3private RBNode<T> root; 4 5public RBTree() { 6 } 7 8public RBTree(T[] arr) { 9if (arr ==null || arr.length == 0) { 10return; 11 } 12 13for (T i : arr) { 14this.add(i); 15 } 16 } 17 18// 查找结点 t 19public RBNode<T> findRbNode(T t) { 20returnthis.findRbNode(t, root); 21 } 22 23private RBNode<T> findRbNode(T t, RBNode<T> node) { 24if (t ==null || node ==null) { 25returnnull; 26 } 27 28if (t.compareTo(node.value) == 0) { 29return node; 30 } 31if (t.compareTo(node.value) < 0) { 32returnthis.findRbNode(t, node.left); 33 }else { 34returnthis.findRbNode(t, node.right); 35 } 36 } 37 38// 查找结点 t 的前驱 39private RBNode<T> precursor(T t) { 40final RBNode<T> node =this.findRbNode(t); 41if (node ==null) { 42returnnull; 43 } 44returnthis.precursor(node); 45 } 46 47private RBNode<T> precursor(RBNode<T> node) { 48// 左子树的最大值 49if (node.left !=null) { 50 RBNode<T> t = node.left; 51while (t.right !=null) { 52 t = t.right; 53 } 54return t; 55 }else { 56// 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的. 57 RBNode<T> temp = node.parent; 58 RBNode<T> ch = node; 59while (temp !=null && ch == temp.left) { 60 ch = temp; 61 temp = temp.parent; 62 } 63 64return temp; 65 } 66 } 67 68// 查找结点 t 的后继 69private RBNode<T> successor(T t) { 70final RBNode<T> node =this.findRbNode(t); 71if (node ==null) { 72returnnull; 73 } 74returnthis.successor(node); 75 } 76 77private RBNode<T> successor(RBNode<T> node) { 78// 右子树的最小值 79if (node.right !=null) { 80 RBNode<T> t = node.right; 81while (t.left !=null) { 82 t = t.left; 83 } 84return t; 85 }else { 86// 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的. 87 RBNode<T> temp = node.parent; 88 RBNode<T> ch = node; 89while (temp !=null && ch == temp.right) { 90 ch = temp; 91 temp = temp.parent; 92 } 93 94return temp; 95 } 96 } 97 98publicvoid delete(T value) { 99final RBNode<T> node =this.findRbNode(value);100if (node ==null) {101 System.out.println("待删除的结点:" + value + " 不存在~");102return;103 }104105this.delNode(node);106 }107108privatevoid delNode(RBNode<T> node) {109finalint degree = node.getDegree();110// 度为 0111if (degree == 0) {112// 1.红色.直接删113if (node.red) {114this.freeDegree0(node);115 }else {116// 2.黑色117if (node == root) {118this.freeDegree0(node);119 }else {120this.delBlackNode(node);121 }122 }123 }elseif (degree == 1) {124// 度为 1.一定是 "黑-红"125if (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// 度为 2134final RBNode<T> precursor =this.precursor(node);135 node.value = precursor.value;136this.delNode(precursor);137 }138 }139140/* 删除度为 1 的黑色结点*/141privatevoid delBlackNode(RBNode<T> node) {142 RBNode<T> temp = node;143144// 递归调整145while (temp != root) {146final RBNode<T> p = temp.parent;147final RBNode<T> brother = temp.getBrother();148149// 兄弟 B是红150if (brother.red) {151this.adjustCase1(temp);// 经过adjustCase1后,兄弟是黑色152 }else {153// 兄弟 B是黑 .有孩子154if (brother.left !=null || brother.right !=null) {155if (temp == p.left) {156if (brother.right !=null) {157this.adjustCase2(temp);158 }else {159this.adjustCase3(temp);160 }161 }else {162if (brother.left !=null) {163this.adjustCase2(temp);164 }else {165this.adjustCase3(temp);166 }167 }168169break;170 }else {171// C-黑.兄弟 B是黑. 且没有孩子172// p-红173if (p.red) {174 brother.red =true;175 p.red =false;176this.freeDegree0(temp);177break;178 }else {179// p-黑180 brother.red =true;181this.freeDegree0(temp);182 temp = p;183 }184 }185 }186 }187 }188189// C-黑. B-红190privatevoid adjustCase1(RBNode<T> node) {191final RBNode<T> p = node.parent;192// 左孩子.(左右对称的)193if (node == p.left) {194this.leftRotate(p);195 }else {196this.rightRotate(p);197 }198199 node.parent.red =true;200 node.parent.parent.red =false;201 }202203// C-黑. B-黑. BR-红 (远侄子)204privatevoid adjustCase2(RBNode<T> node) {205final RBNode<T> p = node.parent;206if (node == p.left) {207this.leftRotate(p);208209// 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 {215this.rightRotate(p);216217// B、P颜色互换218 node.parent.parent.red = node.parent.red;219 node.parent.red =false;220// 涂黑远侄子221 node.parent.parent.left.red =false;222 }223this.freeDegree0(node);224 }225226// C-黑. B-黑. BR-不存在. BL-红 (近侄子)227privatevoid adjustCase3(RBNode<T> node) {228final RBNode<T> p = node.parent;229final RBNode<T> brother = node.getBrother();230// C 是左孩子.BL-红 (近侄子)231if (brother.left !=null) {232 rightRotate(brother);233 }else {234// C 是右孩子.BR-红 (近侄子)235 leftRotate(brother);236 }237238// BL 和 B 互换颜色239 brother.red =true;240 brother.parent.red =false;241242// 跳转到adjustCase2243this.adjustCase2(p);244 }245246// 直接删除度为 0 的结点 node247privatevoid freeDegree0(RBNode<T> node) {248final RBNode<T> p = node.parent;249// 待删除结点 node 就是root250if (p ==null) {251 root =null;252return;253 }254255if (node == p.left) {256 p.left =null;257 }else {258 p.right =null;259 }260 }261262// 添加结点263publicvoid add(T value) {264 RBNode<T> newNode =new RBNode<>(value);265if (root ==null) {266 root = newNode;267 newNode.red =false;268return;269 }270271// 1.添加272this.add(root, newNode);273274// 2.调整275this.fixUp(newNode);276 }277278privatevoid fixUp(RBNode<T> newNode) {279if (newNode == root) {280 newNode.red =false;281return;282 }283284// newNode 的父结点为黑色285if (!newNode.parent.red) {286return;287 }288289/* 1.newNode 的叔叔结点存在且为红色。*/290final RBNode<T> uncle = newNode.getUncle();291if (uncle !=null && uncle.red) {292 newNode.parent.red =false;293 uncle.red =false;294295 newNode.parent.parent.red =true;296this.fixUp(newNode.parent.parent);297 }else {298/* 2.newNode 的叔叔结点不存在，或者为黑色。*/299final RBNode<T> grandFather = newNode.getGrandFather();300// 2.1左左301if (newNode == grandFather.left.left) {302this.rightRotate(grandFather);303 newNode.parent.red =false;304 grandFather.red =true;305 }306// 2.2左右307elseif (newNode == grandFather.left.right) {308this.leftRotate(newNode.parent);309this.rightRotate(grandFather);310 newNode.red =false;311 grandFather.red =true;312 }313// 2.3右右314elseif (newNode == grandFather.right.right) {315this.leftRotate(grandFather);316 newNode.parent.red =false;317 grandFather.red =true;318 }319// 2.4右左320elseif (newNode == grandFather.right.left) {321this.rightRotate(newNode.parent);322this.leftRotate(grandFather);323 newNode.red =false;324 grandFather.red =true;325 }326 }327 }328329// 按 排序二叉树 的规则插入结点330privatevoid add(RBNode<T> root, RBNode<T> newNode) {331if (newNode.value.compareTo(root.value) <= 0) {332if (root.left ==null) {333 root.left = newNode;334 newNode.parent = root;335 }else {336this.add(root.left, newNode);337 }338 }else {339if (root.right ==null) {340 root.right = newNode;341 newNode.parent = root;342 }else {343this.add(root.right, newNode);344 }345 }346 }347348// 左旋349privatevoid leftRotate(RBNode<T> node) {350if (node ==null) {351return;352 }353final RBNode<T> p = node.parent;354355// 左旋. 应该认为 temp 不为null356final RBNode<T> temp = node.right;357 node.right = temp.left;358if (temp.left !=null) {359// 该结点可能不存在360 temp.left.parent = node;361 }362363 temp.left = node;364 node.parent = temp;365366// 旋转完成.修正根结点与父结点367// 1.node为根结点368if (node == root) {369 root = temp;370 temp.parent =null;371return;372 }373374// 2.node不为根结点375// node 为父结点的右孩子376if (node == p.right) {377 p.right = temp;378 }else {379 p.left = temp;380 }381 temp.parent = p;382 }383384// 右旋385privatevoid rightRotate(RBNode<T> node) {386if (node ==null) {387return;388 }389390final RBNode<T> p = node.parent;391392// 右旋. 应该认为 temp 不为null393final RBNode<T> temp = node.left;394 node.left = temp.right;395if (temp.right !=null) {396// 该结点可能不存在397 temp.right.parent = node;398 }399400 temp.right = node;401 node.parent = temp;402403// 旋转完成.修正根结点与父结点404// 1.node为根结点405if (node == root) {406 root = temp;407 temp.parent =null;408return;409 }410411// 2.node不为根结点412// node 为父结点的右孩子413if (node == p.right) {414 p.right = temp;415 }else {416 p.left = temp;417 }418 temp.parent = p;419 }420421// 中序遍历422publicvoid infixOrder() {423this.infixOrder(root);424 }425426privatevoid infixOrder(RBNode<T> root) {427if (root !=null) {428this.infixOrder(root.left);429 System.out.print("-->" + root.value + ":" + (root.red ? "红" : "黑"));430this.infixOrder(root.right);431 }432 }433434/**435 * 红黑树 树结点结构436*/437protectedstaticclass RBNode<Textends Comparable<T>> {438private T value;439// 默认为 红色 结点440privateboolean red =true;441442private RBNode<T> left;443private RBNode<T> right;444private RBNode<T> parent;445446public RBNode() {447 }448449public RBNode(T value) {450this.value = value;451 }452453// 返回结点的度454publicint getDegree() {455if (this.left ==null &&this.right ==null) {456return 0;457 }458459if ((this.left !=null &&this.right ==null) || (this.left ==null &&this.right !=null)) {460return 1;461 }462463return 2;464 }465466public RBNode<T> getUncle() {467final RBNode<T> grandFather =this.parent.parent;468final RBNode<T> parent =this.parent;469470if (parent == grandFather.left) {471return grandFather.right;472 }473474if (parent == grandFather.right) {475return grandFather.left;476 }477478returnnull;479 }480481public RBNode<T> getGrandFather() {482returnthis.parent.parent;483 }484485public RBNode<T> getBrother() {486final RBNode<T> p =this.parent;487488returnthis == p.left ? p.right : p.left;489 }490491 @Override492public String toString() {493return "RBNode{" +494 "value=" + value +495 ", red=" + red +496 '}';497 }498 }499 }
完整的红黑树插入及删除
代码示例：测试
1publicclass Main { 2publicstaticvoid 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 用于读者验证上述代码的结果。上述测试案例构建的红黑树为：
