【算法】手撕红黑树（下）—— 一张流程图梳理删除操作（含实现代码）
标签：展示 als todo 导出 颜色 位置 ring return alt
本文承接上篇，重点讲解上篇中没有提到的红黑树中最复杂的删除操作。
这里还是用流程图来展示，先规定一下图中代号节点的基本含义：
C节点（Curent,当前要操作节点的指针）
D节点（Delete,最终要删除的节点的指针）
P节点（Parent,当前C节点的父节点）
S节点（Sibling,当前C节点的兄弟节点）
此外：
白圈节点指代黑节点（毕竟CAD背景色是黑的嘛QAQ）；
红圈节点就是红节点；
黄圈节点则表示不做限制，可以是红色或黑色；
【注意P、S节点应当随着C的更新而更新，D节点不会；element则指代节点中的内容】
最后是删除功能的实现代码（插入功能的实现代码也写在了一起）：
1 /**
2 * 手撕红黑树
3 * By 469の瘸子 （意义不明的口胡：现在应该是420の的瘸子233）
4 * **/
5 public class RedBlackTreeextends Comparable & PrintToDOS> {
6
7 public static final boolean black = true;
8 public static final boolean red = false;
9 public Node root;
10
11 class Node {//节点类
12 public Node parent;
13 public Node left;
14 public Node right;
15 public E element;
16 public boolean color;
17
18 public Node (E element){//构造方法，默认新节点为红色
19 this.element = element;
20 this.color =red;
21 }
22
23 //打印的红黑树的时候，会调用每个节点的打印方法
24 public void print(){
25 //先打印颜色
26 if (this.color) {
27 System.out.print(" black:");
28 }else {
29 System.out.print(" red:");
30 }
31 //再打印值
32 element.print();
33 //最后打印父节并换行
34 if(parent==null){
35 System.out.println(" this is root");
36 }else {
37 System.out.print(" parent is:");
38 parent.element.println();
39 }
40 }
41
42 }
43
44 //插入方法，会调用insert方法和fixAfterInsertion方法
45 public void insert(E element){
46 //case1:树中无元素，直接将elemnt插进去涂黑
47 if (root==null){
48 root = new Node(element);
49 root.color = black;
50 }else{//case2:树非空，先按二叉搜索树的方式确定元素位置，再视父元素颜色分类处理
51 //先把节点插进去，如果插的元素已经存在会返回null
52 Node node = insertBST(element);
53 //再对树进行维护
54 fixAfterInsertion(node);
55 }
56
57 }
58
59 //该方法只负责将新的节点插进树里，不负责维护红黑树性质
60 private Node insertBST(E element){
61 Node pointer = root;
62 Node pointer_parent = null;
63
64 do{
65 switch (element.compareTo(pointer.element)){
66 case 0:
67 System.out.println("已有当前元素！");
68 return null;
69 case 1:
70 pointer_parent = pointer;
71 pointer = pointer.right;
72 break;
73 case -1:
74 pointer_parent = pointer;
75 pointer = pointer.left;
76 break;
77 default:
78 break;
79 }
80 }while (pointer!=null);
81
82 Node child = new Node(element);
83 child.parent = pointer_parent;
84
85 //compareTo的结果只会是1或-1。不会出现0，是0的话，在上方的switch语句里就return了
86 if(pointer_parent.element.compareTo(element)>0){
87 pointer_parent.left = child;
88 }else {
89 pointer_parent.right = child;
90 }
91 return child;
92 }
93
94 //该方法负责插入后的维护工作
95 private void fixAfterInsertion(Node node){
96 Node cur,parent,grandparent,uncle;
97 cur = node;
98 //检查是否需要维护树,cur是null的话说明插的元素已存在，就不用维护了
99 if(cur !=null){
100 parent = cur.parent;
101 //cur.print();
102 //case2.1:父节点为黑色或为空，不用维护
103 if(parent==null||parent.color == black){
104 return;
105 }else{//case2.2:父节点为红色，视叔叔节点颜色分类处理
106
107 //region 先获取U、G节点的引用（这里G必然非空，因为G空必然P为根且黑，那就不会执行到这里）
108 grandparent = parent.parent;
109 if(grandparent.left == parent){
110 uncle = grandparent.right;
111 }else {
112 uncle = grandparent.left;
113 }
114 //endregion
115
116 //case2.2.1:U节点为黑色（NIL节点也是黑色的）。视C、P、G节点的形态处理
117 if (uncle==null||uncle.color==black){
118 //case2.2.1.1:C、P、G形态为“/”、“\”。以G为支点右旋或左旋，P变黑、G变红
119 if(grandparent.element.compareTo(parent.element)==parent.element.compareTo(cur.element)){
120 parent.color=black;
121 grandparent.color=red;
122 if(grandparent.element.compareTo(parent.element)>0){//“/”形态，右旋
123 rightRotate(grandparent);
124 }else {//“\”形态，左旋
125 leftRotate(grandparent);
126 }
127 }else {//case2.2.1.2:C、P、G形态为“”。先以P为支点左旋或右旋，在以P为支点右旋或左旋
128 cur.color = black;
129 grandparent.color =red;
130 if(grandparent.element.compareTo(parent.element)>0){//“
131 leftRotate(parent);
132 rightRotate(grandparent);
133 }else {//“>”形态，P右旋后、G左旋
134 rightRotate(parent);
135 leftRotate(grandparent);
136 }
137 }
138 }else {//case2.2.2:U节点为红色。将P、G、U节点换色，然后cur指向G节点调用维护函数
139 grandparent.color=red;
140 parent.color=black;
141 uncle.color=black;
142 fixAfterInsertion(grandparent);
143 }
144
145 }
146
147 }
148 root.color=black;
149 }
150
151 //左旋方法
152 private void leftRotate(Node node){
153 Node parent = node.parent;
154 Node child = node.right;
155 Node childLeft = child==null?null:child.left;
156 //子节点上位
157 if(parent==null){//支点为根节点，parent会是空
158 child.parent = null;
159 root = child;
160 }else {
161 if (parent.left == node){
162 parent.left = child;
163 child.parent = parent;
164 }else {
165 parent.right = child;
166 child.parent = parent;
167 }
168 }
169 //父节点下位
170 child.left = node;
171 node.parent = child;
172 //子树调整
173 node.right = childLeft;
174 if(childLeft!=null){
175 childLeft.parent = node;
176 }
177 }
178 //右旋方法
179 private void rightRotate(Node node){
180 Node parent = node.parent;
181 Node child = node.left;
182 Node childRight = child==null?null:child.right;
183 //子节点上位
184 if(parent==null){//支点为根节点，parent会是空
185 child.parent = null;
186 root = child;
187 }else {//支点不是根节点
188 if (parent.left == node){
189 parent.left = child;
190 child.parent = parent;
191 }else {
192 parent.right = child;
193 child.parent = parent;
194 }
195 }
196
197 //父节点下位
198 child.right = node;
199 node.parent = child;
200 //子树调整
201 node.left = childRight;
202 if(childRight!=null){
203 childRight.parent = node;
204 }
205 }
206
207 //打印红黑树
208 public void printRBT(Node node){
209
210 if(node!=null){
211 printRBT(node.left);
212 node.print();
213 printRBT(node.right);
214 }else {
215 return;
216 }
217 }
218
219 public static void main(String[] args) {
220
221 //13,8,5,11,6,22,27,25,14,17 另外一组调试数据
222 int[] nums = {1,2,3,4,5,6,7,8,9,10};
223 RedBlackTree redBlackTree = new RedBlackTree ();
224
225 for (int i: nums){
226 Element element = new Element(i);
227 redBlackTree.insert(element);
228 }
229 //打印红黑树
230 redBlackTree.printRBT(redBlackTree.root);
231
232 //删除操作
233 int value = 3;
234 redBlackTree.remove(new Element(value));
235 System.out.println("删除节点"+value+"后，打印：");
236
237 //打印红黑树
238 redBlackTree.printRBT(redBlackTree.root);
239 }
240
241 /**—————————— —— 分割线：以下是删除代码 —————————————**/
242 //从树中删除一个元素的代码
243 public void remove(E element){
244 Node pointer = getNodeByElement(element);
245 if(pointer==null){
246 System.out.print("树中并没有要删除的元素");
247 return;
248 }
249 do {
250 //case1:要删除的节点仅有一个子树，红黑树性质决定该情况下删除的必然是黑节点，且子节点为红色叶子节点
251 if ((pointer.left==null)!=(pointer.right==null)) {
252 //要删除的节点的子树（仅为一个红色叶子节点）顶上来并变色
253 removeOneBranchNode(pointer);
254 return;
255 } else {//case2:删除节点为叶子节点
256 if ((pointer.left == null)&&(pointer.right == null)) {
257 removeLeafNode(pointer);
258 return;
259 } else {//case3:要删除的节点有两个子树
260 //指针指向后继节点，后继节点element顶替要删除的element。再do一次以判定新指针的case(此时只会是case2、3)
261 pointer = changePointer(pointer);
262 }
263 }
264
265 }while (true);
266 }
267
268 //获取要删除的元素的Node，若返回为null代表树中没有要删除的元素
269 public Node getNodeByElement(E element){
270 if(root==null){//树为空，返回null
271 return null;
272 }
273
274 Node pointer = root;
275 do{
276 if(element.compareTo(pointer.element)>0){//大于，指针指向右孩子
277 pointer = pointer.right;
278 }else {
279 if(element.compareTo(pointer.element)//小于，指针指向左孩子
280 pointer = pointer.left;
281 }else {//等于，返回当前的节点
282 return pointer;
283 }
284 }
285 }while (pointer!=null);
286 return null;
287 }
288
289 //指针指向后继节点，并用后继节点的element顶替要删除的element,没有后继节点就返回null
290 public Node changePointer(Node pointer){
291 //指针备份方便替换时找到引用
292 Node pointer_old = pointer;
293 //寻找后继节点
294 pointer = pointer.right;
295 while (pointer.left!=null){ pointer = pointer.left; }
296 pointer_old.element=pointer.element;
297 return pointer;
298 }
299
300 //删除叶子节点，红色的就直接删，黑色的分情况处理
301 public void removeLeafNode(Node pointer){
302 Node parent = pointer.parent;
303 Node pointer_old = pointer;
304 //case:2.1叶子节点是根节点
305 if(parent==null){
306 root=null;
307 return;
308 }
309 //case:2.2叶子节点是红色的的话直接删除，黑色的要分类处理
310 if(pointer.color==red){
311 if(pointer.parent.left==pointer){
312 pointer.parent.left=null;
313 }else {
314 pointer.parent.right=null;
315 }
316 }else {
317 //case2.3:叶子节点是黑色的,视兄弟点分类处理
318 while (pointer.parent!=null&&pointer.color==black){
319 parent = pointer.parent;//在case2.3.2.2下循环，要更新parent
320 Node brother;
321 if(pointer.parent.left==pointer){//左叶子节点处理方式
322 brother = pointer.parent.right;
323 //case2.3.1:兄弟节点为红色。那么将其转换为黑色
324 if(brother.color==red){
325 brother.color = black;
326 parent.color = red;
327 leftRotate(parent);
328 brother = parent.right;
329 }
330 //case2.3.2:兄弟节点为黑色，侄子节点都是黑色（NIL）
331 if((brother.left == null)&&(brother.right == null)){
332 //case2.3.2.1:父节点为红色
333 if(parent.color==red){
334 parent.color = black;
335 brother.color = red;
336 break;
337 }else {//case2.3.2.2:父节点为黑色
338 brother.color = red;
339 pointer = parent;
340 //继续循环
341 }
342 }else {
343 //case2.3.3:兄弟节点为黑色,左侄子为红色
344 if((brother.color==black)&&brother.left!=null&&brother.left.color==red){
345 brother.left.color = parent.color;
346 parent.color = black;
347 rightRotate(brother);
348 leftRotate(parent);
349 //case2.3.4:兄弟节点为黑色,右侄子为红色
350 }else if((brother.color==black)&&brother.right!=null&&brother.right.color==red){
351 brother.color = parent.color;
352 parent.color = black;
353 brother.right.color = black;
354 leftRotate(parent);
355 }
356 break;
357 }
358 }else {//右叶子节点处理方式
359 brother = pointer.parent.left;
360 //case2.3.1:兄弟节点为红色。那么将其转换为黑色
361 if(brother.color==red){
362 brother.color = black;
363 parent.color = red;
364 rightRotate(parent);
365 brother = parent.left;
366 }
367 //case2.3.2:兄弟节点为黑色，侄子节点都是黑色（NIL）
368 if((brother.left == null)&&(brother.right == null)){
369 //case2.3.2.1:父节点为红色
370 if(parent.color==red){
371 parent.color = black;
372 brother.color = red;
373 break;
374 }else {//case2.3.2.2:父节点为黑色
375 brother.color = red;
376 pointer = parent;
377 //继续循环
378 }
379
380 }else {
381 //case2.3.3:兄弟节点为黑色,右侄子为红色
382 if((brother.color==black)&&brother.right!=null&&brother.right.color==red){
383 brother.right.color = parent.color;
384 parent.color = black;
385 leftRotate(brother);
386 rightRotate(parent);
387 //case2.3.4:兄弟节点为黑色,左侄子为红色
388 }else if((brother.color==black)&&brother.left!=null&&brother.left.color==red){
389 brother.color = parent.color;
390 parent.color = black;
391 brother.left.color = black;
392 rightRotate(parent);
393 }
394 break;
395 }
396 }
397 }
398 //最后别忘了删掉这个节点
399 if(pointer_old.parent.left == pointer_old){
400 pointer_old.parent.left = null;
401 }else if((pointer_old.parent.right == pointer_old)){
402 pointer_old.parent.right = null;
403 }
404 pointer_old.parent = null;
405
406 }
407 }
408
409 //删除单分支节点（此时删除节点必为红色，子树仅为一个叶子节点）。子树（就是一个叶子节点）顶上来涂黑即可。
410 public void removeOneBranchNode(Node pointer){
411 Node child = pointer.left!=null?pointer.left:pointer.right;
412 if(pointer.parent.left==pointer){
413 pointer.parent.left = child;
414 }else {
415 pointer.parent.right = child;
416 }
417 child.parent = pointer.parent;
418 child.color=black;
419 }
420
421
422
423 }
上文中泛型E的测试用类及其打印接口：
1 public class Element implements Comparable ,PrintToDOS{
2
3 public Element(int value){
4 this.value = value;
5 }
6
7 public int value;
8
9 @Override
10 public void println() {
11 System.out.println(value);
12 }
13
14 @Override
15 public void print() { System.out.print(value); }
16
17 //this大于element返回1，小于返回-1，相等返回0
18 @Override
19 public int compareTo(Element element) {
20 if (this.value>element.value){
21 return 1;
22 }else {
23 if(this.valueelement.value){
24 return -1;
25 }else {
26 return 0;
27 }
28 }
29 }
30 }
打印接口：
1 public interface PrintToDOS {
2 public void print(); //打印值但不换行
3 public void println();//打印值后换行
4 }
测试结果：
【一个经验：从小到大顺序插入，如1到10，则会出现C、P、S皆黑的这种最复杂的删除情况，这里删除节点3就是这样，大家可以多试几组数据】
最后的最后，本文如有纰漏还请dalao们指正。
【PS：终于整完了这个变态的红黑树了2333，删除的情况有够复杂呢，CAD也导出不了图片，流程图我还要一张张截图再拼在一起QAQ】
【算法】手撕红黑树（下）—— 一张流程图梳理删除操作（含实现代码）
标签：展示 als todo 导出 颜色 位置 ring return alt
原文地址：https://www.cnblogs.com/469Accelerator/p/13369437.html
评论