rb.java

红黑数算法及演示源代码

                        if (B != null) D = B.leftTreeOf();
                        P = parentOf(parent);
                        A.setLeftTree(null);
                        A.setRightTree(null);
			if (B != null) {
			   B.setRightTree(A);
			   B.setLeftTree(D);
			}
			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 (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();
                        A.setRightTree(null);
                        A.setColor(Color.black);
                        if (B != null) B.setColor(Color.red);
                     } else if (z == 1 && parent.leftTreeOf() == null) {
			parent.setColor(Color.black);
		     }
                     deleteDot(panel.dotOf());
                     reLevel(head,0,0);
                  } else if (parentOf(panel.dotOf()) != null &&
			     parentOf(panel.dotOf()).colorOf() == Color.black){
                     Dot A=null,B=null,C=null,D=null,P=null;
                     int z;
           
                     Dot parent = parentOf(panel.dotOf());
                     if (parent != null) {
                        if (parent.leftTreeOf() == panel.dotOf())
                           z = 0;
                        else
                           z = 1;
                     } else 
			z = -1;

                     if (panel.saveColorOf() == Color.red) {
                        if (parent.leftTreeOf() == panel.dotOf())
                           parent.setLeftTree(null);
                        else
                           parent.setRightTree(null);
                     } 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();
			   D = B.rightTreeOf();
			}
                        P = parentOf(parent);
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                        } else 
			   head = B;
                        
                        if (C != null && 
			    C.leftTreeOf() == null && 
			    C.rightTreeOf() == null){
                           if (B != null) B.setLeftTree(A);
                           A.setRightTree(C);
                           A.setLeftTree(null);
			   if (B != null) B.setColor(Color.black);
			   A.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           C.setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);           
                        } else if (C != null &&
				   C.leftTreeOf() == null && 
				   C.rightTreeOf() != null) {
                           C.setLeftTree(A);
                           A.setLeftTree(null);
                           A.setRightTree(null);
                           if (B != null) B.setColor(Color.black);
                           C.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           A.setColor(Color.red);
                           C.rightTreeOf().setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                               D.leftTreeOf().setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                               D.rightTreeOf().setColor(Color.red);
                        } else if (C != null && 
				   C.leftTreeOf() != null && 
				   C.rightTreeOf() == null) {
                           Dot E = C.leftTreeOf();
                           if (B != null) B.setLeftTree(E);
                           if (E != null) {
			      E.setRightTree(C);
			      E.setLeftTree(A);
			   }
                           A.setRightTree(null);
                           A.setLeftTree(null);
                           C.setLeftTree(null);
                           C.setRightTree(null);
                           if (B != null) B.setColor(Color.black);
                           if (E != null) E.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           A.setColor(Color.red);
                           C.setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                               D.leftTreeOf().setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                               D.rightTreeOf().setColor(Color.red);  
                        } else if (C != null) {
                           if (B != null && B.leftTreeOf() != null)
			      B.leftTreeOf().leftTreeOf().setLeftTree(A);
                           A.setLeftTree(null);
                           A.setRightTree(null);
                           if (B != null) B.setColor(Color.black);
                           C.setColor(Color.red);
                           if (D != null) D.setColor(Color.black);
                           C.leftTreeOf().setColor(Color.black);
                           C.rightTreeOf().setColor(Color.black);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);  
                           A.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.black);
                        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();
                        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.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);
                        if (P != null) {
                           if (P.leftTreeOf() == parent)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                        } else
                           head = B;
                        if (C != null &&
			    C.rightTreeOf() == null && 
			    C.leftTreeOf() == null){
                           if (B != null) B.setRightTree(A);
                           A.setLeftTree(C);
                           A.setRightTree(null);
                           if (B != null) B.setColor(Color.black);
                           A.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           C.setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                        } else if (C != null &&
				   C.rightTreeOf() == null && 
				   C.leftTreeOf() != null) {
                           C.setRightTree(A);
                           A.setRightTree(null);
                           A.setLeftTree(null);
                           if (B != null) B.setColor(Color.black);
                           C.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           A.setColor(Color.red);
                           C.leftTreeOf().setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                        } else if (C != null &&
				   C.rightTreeOf() != null && 
				   C.leftTreeOf() == null) {
                           Dot E = C.rightTreeOf();
                           if (B != null) B.setRightTree(E);
			   if (E != null) {
			      E.setLeftTree(C);
			      E.setRightTree(A);
			   }
                           A.setLeftTree(null);
                           A.setRightTree(null);
                           C.setRightTree(null);
                           C.setLeftTree(null);
                           if (B != null) B.setColor(Color.black);
                           if (E != null) E.setColor(Color.black);
                           if (D != null) D.setColor(Color.black);
                           A.setColor(Color.red);
                           C.setColor(Color.red);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                        } else {
			   if (B != null && B.rightTreeOf() != null)
			      B.rightTreeOf().rightTreeOf().setRightTree(A);
                           A.setLeftTree(null);
                           A.setRightTree(null);
                           if (B != null) B.setColor(Color.black);
                           C.setColor(Color.red);
                           if (D != null) D.setColor(Color.black);
                           C.rightTreeOf().setColor(Color.black);
                           C.leftTreeOf().setColor(Color.black);
                           if (D != null && D.rightTreeOf() != null)
                              D.rightTreeOf().setColor(Color.red);
                           if (D != null && D.leftTreeOf() != null)
                              D.leftTreeOf().setColor(Color.red);
                           A.setColor(Color.red);
                        }           
                     } else if (z==1 && 
				parent.leftTreeOf() != null &&
				(parent.leftTreeOf().leftTreeOf() != null &&
				 parent.leftTreeOf().rightTreeOf() == null)) {
                        A = parent;
                        B = parent.leftTreeOf();
                        if (B != null) D = B.leftTreeOf();
                        P = parentOf(parent);
                        A.setLeftTree(null);
                        A.setRightTree(null);
			if (B != null) {
			   B.setRightTree(A);
			   B.setLeftTree(D);
			}
			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.black);
                        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.black);