数据结构与算法（十三）——红黑树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
3 private RBNode
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
21 }
22
23 private RBNode
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
41 if (node == null) {
42 return null;
43 }
44 return this.precursor(node);
45 }
46
47 private RBNode
49 if (node.left != null) {
50 RBNode
52 t = t.right; 53 }
54 return t; 55 } else { 56 // 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的.
57 RBNode
63
64 return temp; 65 }
66 }
67
68 // 查找结点 t 的后继
69 private RBNode
71 if (node == null) {
72 return null;
73 }
74 return this.successor(node);
75 }
76
77 private RBNode
79 if (node.right != null) {
80 RBNode
82 t = t.left; 83 }
84 return t; 85 } else { 86 // 这里在删除的情况下是不存在的.但是,就找前驱后继来说是存在的.
87 RBNode
93
94 return temp; 95 }
96 }
97
98 public void delete(T value) { 99 final RBNode
100 if (node == null) {
101 System.out.println(“待删除的结点:” + value + “ 不存在~”);
102 return;
103 }
104
105 this.delNode(node);
106 }
107
108 private void delNode(RBNode
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
135 node.value = precursor.value;
136 this.delNode(precursor);
137 }
138 }
139
140 /* 删除度为 1 的黑色结点 */
141 private void delBlackNode(RBNode
142 RBNode
143
144 // 递归调整
145 while (temp != root) {
146 final RBNode
147 final RBNode
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
191 final RBNode
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
205 final RBNode
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
228 final RBNode
229 final RBNode
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
248 final RBNode
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
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
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
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
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
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
350 if (node == null) {
351 return;
352 }
353 final RBNode
354
355 // 左旋. 应该认为 temp 不为null
356 final RBNode
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
386 if (node == null) {
387 return;
388 }
389
390 final RBNode
391
392 // 右旋. 应该认为 temp 不为null
393 final RBNode
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
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
438 private T value;
439 // 默认为 红色 结点
440 private boolean red = true;
441
442 private RBNode
443 private RBNode
444 private RBNode
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
467 final RBNode
468 final RBNode
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
482 return this.parent.parent;
483 }
484
485 public RBNode
486 final RBNode
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
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 用于读者验证上述代码的结果。上述测试案例构建的红黑树为：
作者：Craftsman-L
出处：https://www.cnblogs.com/originator
本博客所有文章仅用于学习、研究和交流目的，版权归作者所有，欢迎非商业性质转载。
如果本篇博客给您带来帮助，请作者喝杯咖啡吧！点击下面打赏，您的支持是我最大的动力！