好久没更新了 今天发个有点技术含量的
java实现红黑树代码
下面是代码
由于我才疏学浅 和自己对于特别复杂的问题的讲解能力问题 可能不能特别清晰明了的为大家讲解清晰 后面会抽时间整理思路 单独出一篇来讲这个原理
在这之前 为大家推荐 自己在学习过程中找到的比较好的讲解文章
这是链接
这要求我们对树 平衡树 有一定的了解 不会的可以自己在网上找些教程 这很简单
下面我们上代码
此代码为本人原创
不想网上有些地方的直接复制
对大家应该有不错的参考意义
我想说的是 要理解原理 参透原理 在纸上完全规划好实现的各个方面 然后在进行编码调试
OK 下面看代码
1 package good;
2
3 public class RedBlackTree {
4
5 node Head;
6
7
8 public RedBlackTree() {//A constructor
9 Head = new node();
10 Head.isNil = true;
11 }
12
13 private static node getNIL(){//Get a NIL node
14 node a = new node();
15 a.isNil = true;
16 a.color = 2;
17 return a;
18 }
19
20
21 public static void main(String[] args) {
22 RedBlackTree c = new RedBlackTree();
23 int[] a;
24 a= new int[]{50,20,60,10,30,70,40};
25 for (int i=0;i){
26 c.addNode(a[i]);
27 }
28 c.Put();
29 }
30
31
32 public void chageNode(int Old, int New){// Modification method
33 deletNode(Old);
34 addNode(New);
35
36 }
37
38
39 public int checkNode(int n){//Query method, with this number, returns 0, otherwise returns-1
40 if (getNode(n)!=null){
41 return 0;
42 }else{
43 return -1;
44 }
45 }
46
47
48 public void Put() {//Output method
49 PUT(Head);
50 System.out.println();
51 }
52
53 private void PUT(node head) {//Specific output method
54 if (head == null) {//In the sequence traversal
55 return;
56 }
57 if (head.isNil == false) {
58 PUT(head.nextLeft);
59 System.out.print(head.getValue()+" ");//A few Spaces in between
60 PUT(head.nextRight);
61 } else {
62 return;
63 }
64 }
65
66
67 public int addNode(int n) {//Add methods
68 return addTwo(n);
69 //Failure returns -1
70 }
71
72 private int addTwo(int n) {//Add a concrete implementation of the method
73 //Find the insert node
74 node to;
75 to = Head;
76 node parent = null;//Initialize the parent node to be null
77 while (to.isNil != true) {
78 parent = to;//You need to bind the parent node
79
80 if (n > to.value) {
81 to = to.nextRight;
82 } else {
83
84 if (n == to.value) {
85 return -1;//Returns -1 if this number exists
86 } else {
87 to = to.nextLeft;
88 }
89 }
90 }
91 //The parent node has been found
92 //Insert and bind the parent node
93 to.clone(new node(n));
94 to.setParent(parent);//Binding parent node
95 //The node is now found and the insert is complete
96 addFixup(parent, to);//Check balance to maintain balance
97 return -1;
98 }
99
100
101 private int addFixup(node parent, node n) {//Added method to maintain balance
102 //Judge each situation
103 if (n.getValue() == Head.getValue()) {//Add nodes as head nodes
104 Head.setColor(2);
105 Head.setParent(null);//Head node condition
106 return 0;
107 }
108
109 if (parent.getColor() == node.BLACK) {//The parent node is black and ends directly without adjustment
110 return 0;
111 }
112
113 if (parent.getColor() == node.RED) {
114 //When the father is red, we need the uncle node.
115 //Get the uncle node and grandfather node first
116 node gp = parent.getParent();//Get grandfather node
117 node uncle;//Uncle node
118
119 if (parent == gp.getNextLeft()) {//Get Uncle Node
120 uncle = gp.getNextRight();
121 } else {
122 uncle = gp.getNextLeft();
123 }
124 //The node has been acquired to judge the situation.
125 //Determined that the father is red
126 if (uncle.getColor() == node.RED) {
127 //Paternal red uncle red condition
128 //Father Hong, uncle Hong, father and uncle are both black, and their grandfather is black for the new N.
129 uncle.setBlack();
130 parent.setBlack();
131 gp.setRed();
132 return addFixup(gp.getParent(), gp);//Leveling up
133 } else {
134 //Paternal red uncle black condition
135 //Judge the direction
136 if (gp.getNextLeft() == parent && n == parent.getNextLeft()) {
137 // PN Same as left
138 parent.setBlack();
139 gp.setRed();//Change color first and then rotate to prevent the relationship from getting wrong after rotation.
140 node i = new node();
141 i.clone(parent.getNextRight());//Why do you do this temporarily? please refer to the clone method in node.
142 parent.getNextRight().clone(gp);
143 parent.getNextRight().setNextLeft(i);
144 i.setParent(parent.getNextRight());
145 gp.clone(parent);
146 return 0;//balance
147 }
148
149 if (parent.getNextRight() == n && gp.getNextRight() == parent) {
150 //PN Same as right
151 parent.setBlack();
152 gp.setRed();
153 node i = new node();
154 i.clone(parent.getNextLeft());//Save the node
155 parent.getNextLeft().clone(gp);
156 parent.getNextLeft().setNextRight(i);
157 i.setParent(parent.getNextLeft());
158 gp.clone(parent);
159 return 0;//Rotation completed and leveled successfully.
160 }
161
162 if (gp.getNextLeft() == parent && parent.getNextRight() == n) {
163 //P left N right
164 //First, turn p to the left.
165 n.getNextLeft().clone(parent);
166 n.getNextLeft().setNextRight(getNIL());
167 parent.clone(n);
168 //Complete the left turn and now PN is the same as the left.
169 parent.setBlack();
170 gp.setRed();//Change color first and then rotate to prevent the relationship from getting wrong after rotation.
171 node i = new node();
172 i.clone(parent.getNextRight());//Keep it for the time being, brother.
173 parent.getNextRight().clone(gp);
174 parent.getNextRight().setNextLeft(i);
175 i.setParent(parent.getNextRight());
176 gp.clone(parent);
177 return 0;
178 //Right-hand rotation complete. Leveling complete.
179 }
180
181 if (gp.getNextRight() == parent && parent.getNextLeft() == n) {
182 //P right N left
183 n.getNextRight().clone(parent);
184 n.getNextRight().setNextLeft(getNIL());
185 parent.clone(n);
186 //Complete the right-hand rotation and now PN is the same as the right.
187 parent.setBlack();
188 gp.setRed();
189 node i = new node();
190 i.clone(parent.getNextLeft());//Temporary preservation
191 parent.getNextLeft().clone(gp);
192 parent.getNextLeft().setNextRight(i);
193 i.setParent(parent.getNextLeft());
194 gp.clone(parent);
195 //Complete left-handed rotation
196 return 0;
197 }
198 //The addition situation has been considered.
199 }
200 }
201 return -1;
202 }
203
204
205 public node getNode(int n) {//Get node
206 //Find Node
207 if (Head.getValue() == n) {
208 return Head;
209 }
210
211 node to = Head;
212 while (to.isNil == false && to.getValue() != n) {
213 if (to.getValue() > n) {
214 to = to.nextLeft;
215 } else {
216 to = to.nextRight;
217 }
218 }
219 if (to.getValue()==n) {//Whether the search was successful or not
220 return to;
221 } else {
222 return null;
223 }
224 }
225
226
227 public int deletNode(int x) {
228 //Delete nod
229 // Get the node first, that is, the node to be deleted
230 node n = getNode(x);
231 return deletNodeTwo(n);//Delete nod
232
233 }
234
235
236 private int deletNodeTwo(node n) {
237 //It is not necessary to delete a node to determine whether it exists or not.
238 if (n == null) {
239 //It doesn't exist.
240 return -1;
241 }
242 if (n.getNextRight()==null){//Prevent null pointers from appearing
243 n.nextRight=getNIL();
244 }
245
246 if (n.nextLeft==null){
247 n.nextLeft=getNIL();
248 }
249 //It is not empty now and it is a normal node.
250 //Deal with the case without child nodes first
251 if (n.getNextLeft().isNil && n.getNextRight().isNil) {
252 //No child node
253 //To delete as red
254 if (n.getColor() == node.RED) {
255 n.setValue(-1);
256 n.isNil = true;//Red no child node is deleted directly.
257 n.setBlack();
258 return 0;//There is no need to maintain balance if the deletion is successful.
259 } else {
260 //Black no child node
261 //Directly delete the dimension level of the successor NIl node
262 n.isNil = true;
263 n.setValue(-1);
264 //Maintain balance with n nodes as unbalanced points
265 return deletFixup(n);
266 }
267 }
268
269
270 //Now there is a child node.
271 if ( (n.getNextRight().isNil && n.getNextLeft().isNil == false) ||
272 (n.getNextRight().isNil==false && n.getNextLeft().isNil) ){
273 //Get child nodes
274 node c;
275 if (n.getNextLeft().isNil==false){
276 c=n.getNextLeft();
277 }else {
278 c=n.getNextRight();
279 }
280 //Child nodes have been obtained
281 //Judge in the light of each situation
282 if (n.getColor()==node.RED){
283 n.clone(c);
284 return 0;
285 //N is red c must be black direct replacement
286 }else {
287 //N is black
288 if (c.getColor()==node.RED){
289 //If n is black, it is red.
290 n.clone(c);
291 n.setBlack();
292 return 0;
293 //Replace discoloration
294 }else {
295 //N is sunspot and black is black.
296 n.clone(c);//Replacement leveling
297 return deletFixup(n);
298 }
299
300 }
301 }
302 //The deletion of two child nodes is now handled.
303 if (n.getNextLeft().isNil==false && n.getNextRight().isNil==false){
304 //Find the successor node and then delete the successor node
305 node max=getMax(n);
306 //Get successor node
307 n.setValue(max.value);//Replace
308 //Delete
309 return deletNodeTwo(max);
310 //Balance
311 }
312 return -1;
313 }
314
315 private int deletFixup(node n){
316 //The parameter is the node to be balanced.
317 if (n==Head){
318 //There is no need to operate when the balance node is the root node.
319 return 0;
320 }
321
322 //Non-root node
323 //The subsequent operation is to get the relevant nodes.
324 node S,SL,SR,U,GP,Parent;
325 Parent=n.getParent();
326 if (n==Parent.getNextLeft()){
327 S=Parent.getNextRight();
328 }else {
329 S=Parent.getNextLeft();
330 }
331 SL=S.getNextLeft();
332 SR=S.getNextRight();
333 GP=Parent.getParent();
334 if (GP!=null) {
335 if (Parent == GP.getNextLeft()) {
336 U = GP.getNextRight();
337 } else {
338 U = GP.getNextLeft();
339 }
340 }
341 //Related nodes have been obtained
342 //Related situation analysis
343
344 if (S.getColor()==node.BLACK){
345 return SisBlack(Parent,S,SL,SR);
346 }else {
347 //Brother node is red
348 //The brothers are on the left and on the right.
349 if (S ==Parent.getNextLeft()) {
350 //The brother node is on the left.
351 S.setBlack();
352 Parent.setRed();
353 node i=new node();
354 i.clone(S.getNextRight());
355 S.getNextRight().clone(Parent);
356 S.getNextRight().setNextLeft(i);
357 i.setParent(S.getNextRight());
358 Parent.clone(S);
359 //Complete rotation
360 Parent=Parent.getNextRight();
361 S=Parent.getNextLeft();
362 return SisBlack(Parent,S,S.getNextLeft(),S.getNextRight());
363 }else {
364 S.setBlack();
365 Parent.setRed();
366 node i=new node();
367 i.clone(S.getNextLeft());
368 S.getNextLeft().clone(Parent);
369 S.getNextLeft().setNextRight(i);
370 i.setParent(S.getNextLeft());
371 Parent.clone(S);
372 Parent=Parent.getNextLeft();
373 S=Parent.getNextRight();
374 return SisBlack(Parent,S,S.getNextLeft(),S.getNextRight());
375 }
376
377 }
378
379 }
380
381
382 private int SisBlack(node Parent,node S,node SL,node SR){
383 //The sibling nodes are black
384 if (SL==null){
385 SL=getNIL();
386 }
387
388 if (SR==null){
389 SR=getNIL();
390 }
391 if (SL.getColor()==node.BLACK && SR.getColor()==node.BLACK){
392 //All sibling nodes are black
393 if (Parent.getColor()==node.BLACK){
394 //The parent node is black
395 S.setRed();
396 return deletFixup(Parent);
397
398 }else {
399 //The father of red
400 Parent.setBlack();
401 S.setRed();
402 //The father is black and the brother is red
403 return 0;
404 }
405 }else {
406 //Not all sibling nodes are black
407 //There are four cases
408
409 if (S==Parent.getNextLeft() && SL.getColor()==node.RED){
410 return SisLAndSLisR(Parent,S,SL);
411 }
412
413 if (S==Parent.getNextRight() && SR.getColor()==node.RED){
414 //S is the right and the right is red
415 return SisRAndSRisR(Parent,S,SR);
416 }
417
418 if (S==Parent.getNextLeft() && SL.getColor()==node.BLACK){
419 //S is the left subson S is the left subson black and the right subson red
420 SR.setBlack();
421 S.setRed();
422 //First left-handed
423 node i=new node();
424 i.clone(SR.getNextLeft());
425 SR.getNextLeft().clone(S);
426 SR.getNextLeft().setNextRight(i);
427 i.setParent(SR.getNextLeft());
428 S.clone(SR);
429 SL=S.getNextLeft();
430 //The new left child
431 //Left child and left is red
432 return SisLAndSLisR(Parent,S,SL);
433 }
434
435 if (S==Parent.getNextRight() && SR.getColor()==node.BLACK){
436 //S is the right and the right is black and the left is red
437 if (SL.getNextRight()==null){
438 SL.nextRight=getNIL();
439 }
440
441 if (SL.getNextLeft()==null){
442 SL.nextLeft=getNIL();
443 }
444 SL.setBlack();
445 S.setRed();
446 node i=new node();
447 i.clone(SL.getNextRight());
448 SL.getNextRight().clone(S);
449 SL.getNextRight().setNextLeft(i);
450 i.setParent(SL.getNextRight());
451 S.clone(SL);
452 SR=S.getNextRight();
453 //The new right is red
454 return SisRAndSRisR(Parent,S,SR);
455 }
456
457 }
458 return -1;
459 }
460
461
462 private int SisLAndSLisR(node Parent,node S,node SL){
463 S.setColor( Parent.getColor());
464 Parent.setBlack();
465 SL.setBlack();
466 node i=new node();
467 i.clone(S.getNextRight());
468 S.getNextRight().clone(Parent);
469 S.getNextRight().setNextLeft(i);
470 i.setParent(S.getNextRight());
471 Parent.clone(S);
472 //P and S discoloration, the left hand turns black, and the right hand turns black
473 return 0;
474 }
475
476
477 private int SisRAndSRisR(node Parent,node S,node SR){
478 //S is the right and the right is red
479 SR.setBlack();
480 S.setColor(Parent.getColor());
481 Parent.setBlack();
482 node i=new node();
483 i.clone(S.getNextLeft());
484 S.getNextLeft().clone(Parent);
485 S.getNextLeft().setNextRight(i);
486 i.setParent(S.getNextLeft());
487 Parent.clone(S);
488 return 0;
489 }
490
491
492 //Find the successor node method
493 private static node getMax(node a){
494 //Parameter is the node to be deleted with two child nodes
495 a=a.getNextLeft();
496 while (a.getNextRight().isNil==false){
497 a=a.getNextRight();
498 }
499
500 return a;
501 //Return successor node
502 }
503
504 }
505
506
507 class node {
508
509 static final int RED = 1;
510 static final int BLACK = 2;
511 static node NIL;
512 int value;
513 node nextLeft;//left
514 node nextRight;//right
515 node parent;//parent node
516 boolean isNil;
517 int color;//1 is red// 2 is black
518
519 public node() {//The default color is red
520 color = 2;
521 isNil = false;
522 }
523
524 public node(int n) {
525 value = n;
526 color = 1;
527 this.toNIL();
528 }
529
530 public static node getNIL() {
531 node a = new node();
532 a.isNil = true;
533 a.color = 2;
534 return a;
535 }
536
537 public void setRed() {
538 this.color = RED;
539 }
540
541 public void setBlack() {
542 this.color = BLACK;
543 }
544
545 public void clone(node a) {// Cloning methods all clones except the parent node
546 if (a==null){
547 this.isNil=true;
548 return;
549 }
550 if (a.isNil)
551 this.isNil=true;
552 else {
553 this.value = a.value;
554 this.color = a.color;
555 if (a.getNextLeft() == null) {
556 a.nextLeft = getNIL();
557 }
558 if (a.getNextRight() == null) {
559 a.nextRight = getNIL();
560 }
561
562 this.nextLeft = a.nextLeft;
563 this.nextRight = a.nextRight;//Don't forget to modify the parent node after cloning
564 a.getNextLeft().setParent(this);
565 a.getNextRight().setParent(this);
566 this.isNil = a.isNil;
567 }
568 }
569
570 public void setNil(boolean nil) {
571 isNil = nil;
572 }
573
574 public int getValue() {
575 return value;
576 }
577
578 public void setValue(int value) {
579 this.value = value;
580 }
581
582 public int getColor() {
583 return color;
584 }
585
586 public void setColor(int color) {
587 this.color = color;
588 }
589
590 public node getNextRight() {
591 return nextRight;
592 }
593
594 public void setNextRight(node nextRight) {
595 this.nextRight = nextRight;
596 }
597
598 public node getNextLeft() {
599 return nextLeft;
600 }
601
602 public void setNextLeft(node nextLeft) {
603 this.nextLeft = nextLeft;
604 }
605
606 public node getParent() {
607 return parent;
608 }
609
610 public void setParent(node parent) {
611 this.parent = parent;
612 }
613
614 private void toNIL() {
615 if (this.getNextRight() == null) {
616 this.nextRight = new node();
617 this.nextRight.setBlack();
618 this.getNextRight().isNil = true;
619 }
620
621 if (this.getNextLeft() == null) {
622 this.nextLeft = new node();
623 this.nextRight.setBlack();
624 this.getNextLeft().isNil = true;
625
626 }
627 }
628 }
再次声明 原创 原创 原创 引用请注明出处
有瑕疵的地方请大家予以指正
后面会更新原理讲解 可能会有点慢 感谢
Original: https://www.cnblogs.com/cndccm/p/13166784.html
Author: Mr小明同学
Title: java实现红黑树
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/712405/
转载文章受原作者版权保护。转载请注明原作者出处!