rb.java

红黑数算法及演示源代码

                     } else if (parentOf(parent) == null) {
			// triangle of three blacks at root (z==0 or z==1)
                        head = parent;
                        if (parent.leftTreeOf() == panel.dotOf())
                           parent.rightTreeOf().setColor(Color.red);
                        else
                           parent.leftTreeOf().setColor(Color.red);
                     } else {
			// There is a triangle of three blacks at bottom
                        B = parentOf(panel.dotOf());
                        if (B != null && B.rightTreeOf() == panel.dotOf()) {
                           if (B.leftTreeOf() != null) 
			      B.leftTreeOf().setColor(Color.red);
			} else if (B != null && B.rightTreeOf() != null)
                           B.rightTreeOf().setColor(Color.red);

                        pushupward = B;
                        deleteDot(panel.dotOf());
                        reLevel(head,0,0);
                        panel.setRemoving(true);
                        bgcolor = new Color(0,190,190);
                        step = 2;
                        return super.action(evt, arg);
                     }

                     deleteDot(panel.dotOf());
                     reLevel(head,0,0);
                  }
                  panel.setRemoving(false);
                  bgcolor = new Color(190,190,190);        
                  step = 0;
               }
            } else if (step == 1) {
               pushdownward.setColor(downSaveColor);
	       if (pushdownward.leftTreeOf() != null && 
		   pushdownward.leftTreeOf().leftTreeOf() != null) {
		  pushdownward = pushdownward.leftTreeOf();
		  downSaveColor = pushdownward.colorOf();
		  pushdownward.setColor(Color.yellow);
		  step = 1;
               } else if (pushdownward != null && 
			  pushdownward.leftTreeOf() != null) {
                  pushdownward.leftTreeOf().setColor(Color.yellow);
                  step = 3;
               } else
		  step = 3;
            } else if (step == 2) { 
	       // going up with one less black depth on one side
               Dot A=null,B=null,C=null,D=null,E=null,F=null,G=null,P=null;
               
               A = pushupward;
               P = parentOf(A);
               if (P == null) {
                  head = A;
                  panel.setRemoving(false);
                  bgcolor = new Color(190,190,190);
                  step = 0;
               } else {
                  E = parentOf(P);         // Grab E here before parent is lost
                  if (P.leftTreeOf() == A) { // Rotate
                     B = P.rightTreeOf();
                     if (B != null) {
			C = B.leftTreeOf();
			D = B.rightTreeOf();
		     }
                     if (D != null && D.colorOf() == Color.black &&
                         C != null && C.colorOf() == Color.red &&
                         B != null && B.colorOf() == Color.black) {
                        P.setRightTree(C);
			B.setLeftTree(C.rightTreeOf());
			C.setRightTree(B);
			B.setColor(Color.red);
			C.setColor(Color.black);

                        reLevel(head,0,0);
                        step = 2;
                        return super.action(evt, arg);
                     } else if (D != null && D.colorOf() == Color.black &&
				C != null && C.colorOf() == Color.black &&
				B != null && B.colorOf() == Color.red) {
                        F = C.leftTreeOf();
                        G = C.rightTreeOf();
                        if (F != null && G != null) {
                           if (G.colorOf() == Color.black) {
                              if (E != null) {
                                 if (E.leftTreeOf() == P) E.setLeftTree(B);
                                 else E.setRightTree(B);
                              } else 
				 head = B;
			      B.setLeftTree(P);
			      P.setRightTree(C);
			      B.setColor(Color.black);
			      C.setColor(Color.red);
			      // Triple Rotation
			      if (C.leftTreeOf() != null &&
				  C.leftTreeOf().colorOf() == Color.red) {
				 Dot g[] = new Dot[100];
				 int idx = 0;
				 Dot ptr = C.leftTreeOf();
				 while (ptr != null) {
				    g[idx++] = ptr;
				    ptr = parentOf(ptr);
				 }
				 for (int i=idx-1 ; i >= 0 ; i--)
				    ss[ssindex++] = g[i];
				 ssindex--;
				 inserting = true;
			      } else {
				 bgcolor = new Color(190,190,190);
			      }
                           } else {
			      // Check this one for correct coloring
                              if (E != null) {
                                 if (E.leftTreeOf() == P) E.setLeftTree(C);
                                 else E.setRightTree(C);
                              } else 
				 head = C;
                              C.setLeftTree(P);
                              C.setRightTree(B);
                              B.setLeftTree(G);
                              P.setRightTree(F);
                              if (G != null && G.colorOf() == Color.red) {
                                 G.setColor(Color.black);
                              } else {
                                 B.setColor(Color.black);
                                 D.setColor(Color.red);
                              }
                           }
                           reLevel(head,0,0);
                           step = 0;
                           panel.setRemoving(false);
                           return super.action(evt, arg);
                        }
                     } else {
                        P.setRightTree(C);
                        if (B != null) B.setLeftTree(P);
                     }
                  } else {
                     B = P.leftTreeOf();
		     if (B != null) {
			C = B.rightTreeOf();
			D = B.leftTreeOf();
		     }
                     if (D != null && D.colorOf() == Color.black &&
                         C != null && C.colorOf() == Color.red &&
                         B != null && B.colorOf() == Color.black) {
                        P.setLeftTree(C);
                        B.setRightTree(C.leftTreeOf());
                        C.setLeftTree(B);
                        B.setColor(Color.red);
                        C.setColor(Color.black);
                        reLevel(head,0,0);
                        step = 2;
                        return super.action(evt, arg);
                     } else if (D != null && D.colorOf() == Color.black &&
				C != null && C.colorOf() == Color.black &&
				B != null && B.colorOf() == Color.red) {
                        F = C.rightTreeOf();
                        G = C.leftTreeOf();
                        if (F != null && G != null) {
                           if (G.colorOf() == Color.black) {
                              if (E != null) {
                                 if (E.leftTreeOf() == P) E.setLeftTree(B);
                                 else E.setRightTree(B);
                              } else 
				 head = B;
                              B.setRightTree(P);
                              P.setLeftTree(C);
                              B.setColor(Color.black);
                              C.setColor(Color.red);
			      // Triple Rotation
			      if (C.rightTreeOf() != null &&
				  C.rightTreeOf().colorOf() == Color.red) {
				 Dot g[] = new Dot[100];
				 int idx = 0;
				 Dot ptr = C.rightTreeOf();
				 while (ptr != null) {
				    g[idx++] = ptr;
				    ptr = parentOf(ptr);
				 }
				 for (int i=idx-1 ; i >= 0 ; i--)
				    ss[ssindex++] = g[i];
				 ssindex--;
				 inserting = true;
			      } else {
				 bgcolor = new Color(190,190,190);
			      }
                           } else {
                              if (E != null) {
                                 if (E.leftTreeOf() == P) E.setLeftTree(C);
                                 else E.setRightTree(C);
                              } else 
				 head = C;
                              C.setRightTree(P);
                              C.setLeftTree(B);
                              B.setRightTree(G);
                              P.setLeftTree(F);
                              if (G.colorOf() == Color.red) {
                                 G.setColor(Color.black);
                              } else {
                                 B.setColor(Color.black);
                                 D.setColor(Color.red);
                              }
			      bgcolor = new Color(190,190,190);
                           }
			   reLevel(head,0,0);
			   step = 0;
			   panel.setRemoving(false);
                           return super.action(evt, arg);
                        }
                     } else {
                        P.setLeftTree(C);
                        if (B != null) B.setRightTree(P);
                     }
                  }
                  
                  if (E != null) {
                     if (E.leftTreeOf() == P) E.setLeftTree(B);
                     else E.setRightTree(B);
                  } else 
		     head = B;
                  
                  if (P.colorOf() == Color.red) {
                     if (C != null && C.colorOf() == Color.red) {
                        if (B != null && B != head) B.setColor(Color.red);
                        else if (B != null) B.setColor(Color.black);
                        if (B != null && B.leftTreeOf() != null)
			   B.leftTreeOf().setColor(Color.black);
                        if (B != null && B.rightTreeOf() != null) 
			   B.rightTreeOf().setColor(Color.black);
                     }
                     panel.setRemoving(false);
                     bgcolor = new Color(190,190,190);
                     step = 0;
                  } else {
                     if (B != null && B.colorOf() == Color.red) {
                        B.setColor(Color.black);
                        if (C != null) C.setColor(Color.red);
                        panel.setRemoving(false);
                        bgcolor = new Color(190,190,190);
                        step = 0;
                     } else if (D != null && D.colorOf() == Color.red) {
                        D.setColor(Color.black);
                        panel.setRemoving(false);
                        bgcolor = new Color(190,190,190);
                        step = 0;
                     } else {
			// case D = B = P = black, C = red already covered
                        if (P != null) P.setColor(Color.red);
                        if (E == null) {
                           panel.setRemoving(false);
                           bgcolor = new Color(190,190,190);
                           step = 0;
                        } else {
                           pushupward = B;
                           step = 2;
                        }
                     }
                  }
               }
               reLevel(head,0,0);
            } else if (step == 3) {
	       if (pushdownward != null &&
		   pushdownward.leftTreeOf() != null) {
		  t_dot = pushdownward.leftTreeOf().rightTreeOf();
		  panel.dotOf().setNumber(pushdownward.leftTreeOf().numberOf());
		  panel.dotOf().setColor(panel.saveColorOf());
		  deleteDot(pushdownward.leftTreeOf());
	       }
               step = 4;     
            } else if (step == 4) {
               if (t_dot != null) {
		  if (pushdownward.colorOf() == Color.red &&
		      !(pushdownward.rightTreeOf() != null &&
			pushdownward.rightTreeOf().colorOf() == Color.black)) {
		     t_dot.setColor(Color.red);
		     pushdownward.setColor(Color.black);
		  } else
		     t_dot.setColor(Color.black);
	       } else {
                  if (pushdownward != null &&
		      pushdownward.colorOf() == Color.black) {
                     if (pushdownward.rightTreeOf() == null) {
                        pushdownward.setLeftTree(null);
                     } else if (pushdownward.rightTreeOf().colorOf() == Color.red) {
                        Dot P = parentOf(pushdownward);
                        Dot B = pushdownward.rightTreeOf();
			Dot A=null, C=null;
			if (B != null) {
			   A = B.leftTreeOf();
			   C = B.rightTreeOf();
			}
                        if (A != null || C != null) {
                           if (P.leftTreeOf() == pushdownward)
                              P.setLeftTree(B);
                           else
                              P.setRightTree(B);
                           if (A != null &&
			       A.leftTreeOf() == null && 
			       A.rightTreeOf() == null) {
                              if (B != null) B.setLeftTree(pushdownward);
                              pushdownward.setRightTree(A);
                              pushdownward.setLeftTree(null);
                              if (B != null) B.setColor(Color.black);
                              pushdownward.setColor(Color.black);
                              if (C != null) C.setColor(Color.black);
                              if (A != null) A.setColor(Color.red);
                           } else if (A != null &&
				      A.leftTreeOf()==null && 
				      A.rightTreeOf()!=null) {
                              A.setLeftTree(pushdownward);
                              pushdownward.setLeftTree(null);
                              pushdownward.setRightTree(null);
                              pushdownward.setColor(Color.red);
                              if (B != null) B.setColor(Color.black);
                           } else if (A != null &&
				      A.leftTreeOf()!=null && 
				      A.rightTreeOf()==null) {
                              Dot E = A.leftTreeOf();
                              if (B != null) B.setLeftTree(E);
                              if (E != null) {
				 E.setLeftTree(pushdownward);
				 E.setRightTree(A);
			      }
                              A.setLeftTree(null);
                              A.setRightTree(null);
                              pushdownward.setLeftTree(null);
                              pushdownward.setRightTree(null);
                              if (E != null) E.setColor(Color.red);
                              if (B != null) B.setColor(Color.black);
                              pushdownward.setColor(Color.black);
                              A.setColor(Color.black);
                           } else if (A != null) {