java实现红黑树

  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<a.length;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 }