rb.java

红黑数算法及演示源代码

			   A.leftTreeOf().setColor(Color.black);
			   C.setColor(Color.black);
			} else if (A.colorOf() == Color.red) {
			   A.setColor(Color.black);
			   if (C.leftTreeOf().leftTreeOf() != null ||
			       C.leftTreeOf().rightTreeOf() != null)
			      C.setColor(Color.red);
			   else
			      C.leftTreeOf().setColor(Color.red);
			} else {
			   A.leftTreeOf().setColor(Color.black);
			}
                     } else if (A != null && 
				A.leftTreeOf() == null && 
				A.rightTreeOf() != null) {
                        Dot E = A.rightTreeOf();
                        if (P != null) {
                           if (P.leftTreeOf() == B) P.setLeftTree(E);
                           else P.setRightTree(E);
                        } else
			   head = E;
                        if (E != null) {
			   E.setLeftTree(A);
			   E.setRightTree(C);
			}
                        A.setRightTree(null);
                        A.setColor(Color.black);
                        C.setColor(Color.black);
                        if (E != null) E.setColor(panel.saveColorOf());
                     } else if (A != null && 
				A.leftTreeOf() != null && 
				A.rightTreeOf() == null) {
                        if (P != null) {
                           if (P.leftTreeOf() == B) P.setLeftTree(A);
                           else P.setRightTree(A);
                        } else
			   head = A;
                        A.setRightTree(C);
                        A.setColor(panel.saveColorOf());
                        C.setColor(Color.black);
                        A.leftTreeOf().setColor(Color.black);
                     } else if (A != null && 
				A.leftTreeOf() == null && 
				A.rightTreeOf() == null) {
                        if (P != null) {
                           if (P.leftTreeOf() == B) P.setLeftTree(A);
                           else P.setRightTree(A);
                        } else 
			   head = A;
                        
                        // one black & two reds or three blacks at top
                        if (panel.saveColorOf() == Color.red || P == null) {
                           A.setRightTree(C);
                           A.setColor(Color.black);
                           C.setColor(Color.red);
                        } else if (A.colorOf() == Color.red) {
			   // two reds on bottom
                           A.setRightTree(C);
                           A.setColor(Color.black);
                        } else {
			   // triangle of 3 blacks at bottom, not at root
                           A.setRightTree(C);
                           A.setColor(Color.black);
                           C.setColor(Color.red);
                           if (P != null) {
                              if (P.rightTreeOf() == panel.dotOf())
                                 P.setRightTree(A);
                              else
                              if (P.leftTreeOf() == panel.dotOf())
                                 P.setLeftTree(A);
                              pushupward = A;
                              deleteDot(B);
                              reLevel(head,0,0);
                              panel.setRemoving(true);
                              bgcolor = new Color(0,190,190);
                              step = 2;
                              return super.action(evt, arg);
                           } else 
			      head = A;
                        }
                     }

                     if (B != null) deleteDot(B);
                     reLevel(head,0,0);
                     panel.setRemoving(false);
                     bgcolor = new Color(190,190,190);           
                     step = 0;   
                  } else if (C != null && C.leftTreeOf() == null) {
                     if (P != null) {
                        if (P.leftTreeOf() == B) P.setLeftTree(C);
                        else P.setRightTree(C);
                     } else
			head = C;
                     C.setLeftTree(A);
                     C.setColor(panel.saveColorOf());
                     if (C.rightTreeOf() != null) 
			C.rightTreeOf().setColor(Color.black);
                     if (B != null) deleteDot(B);
                     reLevel(head,0,0);
                     panel.setRemoving(false);
                     bgcolor = new Color(190,190,190);           
                     step = 0;
                  } else {
                     if ((pushdownward = panel.dotOf().rightTreeOf()) != null){
			downSaveColor = pushdownward.colorOf();
			pushdownward.setColor(Color.yellow);
		     }
                     step = 1;
                  }
               } else if (panel.dotOf().leftTreeOf() != null) {
		  // only left child
                  t_dot = parentOf(panel.dotOf());
                  if (t_dot != null) {
                     if (t_dot.leftTreeOf() == panel.dotOf())
                        t_dot.setLeftTree(panel.dotOf().leftTreeOf());
                     else
                        t_dot.setRightTree(panel.dotOf().leftTreeOf());
                  } else
                     head = panel.dotOf().leftTreeOf();

		  panel.dotOf().leftTreeOf().setColor(Color.black);
                  deleteDot(panel.dotOf());
                  reLevel(head,0,0);
                  panel.setRemoving(false);
                  bgcolor = new Color(190,190,190);        
                  step = 0;
               } else if (panel.dotOf().rightTreeOf() != null) {
		  // only right child
                  t_dot = parentOf(panel.dotOf());
                  if (t_dot != null) {
                     if (t_dot.leftTreeOf() == panel.dotOf())
                        t_dot.setLeftTree(panel.dotOf().rightTreeOf());
                     else
                        t_dot.setRightTree(panel.dotOf().rightTreeOf());
                  } else
                     head = panel.dotOf().rightTreeOf();

		  if (t_dot != null && 
		      t_dot.colorOf() == Color.red &&
		      panel.dotOf().rightTreeOf().colorOf() == Color.red &&
		      panel.dotOf().rightTreeOf().rightTreeOf() == null &&
		      panel.dotOf().rightTreeOf().leftTreeOf() == null) {
		     t_dot.setColor(Color.black);
		     panel.dotOf().rightTreeOf().setColor(Color.red);
		  } else {
		     panel.dotOf().rightTreeOf().setColor(Color.black);
		  }
                  deleteDot(panel.dotOf());
                  reLevel(head,0,0);
                  panel.setRemoving(false);
                  bgcolor = new Color(190,190,190);        
                  step = 0;
               } else { 
		  // no children
                  if (panel.dotOf() == head) {
                     deleteDot(panel.dotOf());
                     head = null;
                  } else if (parentOf(panel.dotOf()) != null &&
			     parentOf(panel.dotOf()).colorOf() == Color.red) {
                     Dot A=null,B=null,C=null,D=null,P=null;
                     int z;
           
                     Dot parent = parentOf(panel.dotOf());
                     if (parent.leftTreeOf() == panel.dotOf()) z=0; else z=1;
           
                     if (z==0 && 
			 parent.rightTreeOf() != null && 
			 (parent.rightTreeOf().rightTreeOf() != null &&
			  parent.rightTreeOf().leftTreeOf() != null)) {
                        A = parent;
                        B = parent.rightTreeOf();
			if (B != null) {
			   C = B.leftTreeOf();
			   D = B.rightTreeOf();
			}
                        P = parentOf(parent);
                        A.setRightTree(C);
                        A.setLeftTree(null);
			if (B != null) {
			   B.setLeftTree(A);
			   B.setRightTree(D);
			}
			if (C != null) {
			   C.setLeftTree(null);
			   C.setRightTree(null);
			}
			if (D != null) {
			   D.setLeftTree(null);
			   D.setRightTree(null);
			}
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                        } else 
			   head = B;
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.red);
                        if (D != null) D.setColor(Color.black);
                        if (C != null) C.setColor(Color.red);
                     } else if (z==0 && 
				parent.rightTreeOf() != null && 
				(parent.rightTreeOf().rightTreeOf() == null &&
				 parent.rightTreeOf().leftTreeOf() != null)) {
                        A = parent;
                        B = parent.rightTreeOf();
                        if (B != null) C = B.leftTreeOf();
                        P = parentOf(parent);
                        A.setRightTree(null);
                        A.setLeftTree(null);
			if (B != null) {
			   B.setLeftTree(null);
			   B.setRightTree(null);
			}
			if (C != null) {
			   C.setLeftTree(A);
			   C.setRightTree(B);
			}
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(C);
                           else
                              P.setRightTree(C);
                        } else 
			   head = C;
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.black);
                        if (C != null) C.setColor(Color.red);
                     } else if (z==0 && parent.rightTreeOf() != null && 
			 (parent.rightTreeOf().rightTreeOf() != null &&
			  parent.rightTreeOf().leftTreeOf() == null)) {
                        A = parent;
                        B = parent.rightTreeOf();
                        if (B != null) D = B.rightTreeOf();
                        P = parentOf(parent);
                        A.setRightTree(null);
                        A.setLeftTree(null);
			if (B != null) {
			   B.setLeftTree(A);
			   B.setRightTree(D);
			}
			if (D != null) {
			   D.setLeftTree(null);
			   D.setRightTree(null);
			}
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                        } else 
			   head = B;
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.red);
                        if (D != null) D.setColor(Color.black);
                     } else if (z==0 && 
				parent.rightTreeOf() != null && 
				(parent.rightTreeOf().rightTreeOf() == null &&
				 parent.rightTreeOf().leftTreeOf() == null)) {
                        A = parent;
                        B = parent.rightTreeOf();
                        A.setLeftTree(null);
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.red);
                     } else if (z==0 && 
				parent.rightTreeOf() == null) {
			parent.setColor(Color.black);
		     } else if (z==1 && 
				parent.leftTreeOf() != null &&
				(parent.leftTreeOf().leftTreeOf() != null &&
				 parent.leftTreeOf().rightTreeOf() != null)) {
                        A = parent;
                        B = parent.leftTreeOf();
			if (B != null) {
			   C = B.rightTreeOf();
			   D = B.leftTreeOf();
			}
                        P = parentOf(parent);
                        A.setLeftTree(C);
                        A.setRightTree(null);
			if (B != null) {
			   B.setRightTree(A);
			   B.setLeftTree(D);
			}
			if (C != null) {
			   C.setRightTree(null);
			   C.setLeftTree(null);
			}
			if (D != null) {
			   D.setRightTree(null);
			   D.setLeftTree(null);
			}
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                        } else 
			   head = B;
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.red);
                        if (C != null) C.setColor(Color.red);
                        if (D != null) D.setColor(Color.black);
                     } else if (z==1 && 
				parent.leftTreeOf() != null &&
				(parent.leftTreeOf().leftTreeOf() == null &&
				 parent.leftTreeOf().rightTreeOf() != null)) {
                        A = parent;
                        B = parent.leftTreeOf();
                        if (B != null) C = B.rightTreeOf();
                        P = parentOf(parent);
                        A.setLeftTree(null);
                        A.setRightTree(null);
			if (B != null) {
			   B.setRightTree(null);
			   B.setLeftTree(null);
			}
			if (C != null) {
			   C.setRightTree(A);
			   C.setLeftTree(B);
			}
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(C);
                           else
                              P.setRightTree(C);
                        } else 
			   head = C;
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.black);
                        if (C != null) C.setColor(Color.red);
                     } else if (z==1 && 
				parent.leftTreeOf() != null &&
				(parent.leftTreeOf().leftTreeOf() != null &&
				 parent.leftTreeOf().rightTreeOf() == null)) {
                        A = parent;
                        B = parent.leftTreeOf();