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

2022 年 3 月 28 日
筆記
数据结构与算法

三、删除

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         // 度为 0
111         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             // 度为 2
134             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         // 跳转到adjustCase2
243         this.adjustCase2(p);
244     }
245 
246     // 直接删除度为 0 的结点 node
247     private void freeDegree0(RBNode<T> node) {
248         final RBNode<T> p = node.parent;
249         // 待删除结点 node 就是root
250         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 不为null
356         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 不为null
393         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         @Override
492         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 }

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

Tags: 数据结构与算法