rb.java

红黑数算法及演示源代码

      } else if (head != null && head.colorOf() != Color.black) 
	 head.setColor(Color.black);

      if (!panel.removingOf() && 
	  rev1 == null && rev2 == null && rev3 == null &&
	  temp == null && !(head == null && newest != null) &&
	  ssindex == 0 && (head != null && head.colorOf() == Color.black)) {
	 bgcolor = new Color(190,190,190);
	 inserting = false;
      }
   }

   public void start() {  panel.start();  }

   public void stop()  {  panel.stop();   }

   Dot copyTree(Dot root) {
      if (root == null) return null;
      Dot dot = new Dot(root.numberOf(), root.colorOf());
      dot.setTop(root.topOf());
      dot.setLeft(root.leftOf());
      dot.setLevel(root.levelOf());
      dot.setIndent(root.indentOf());
      dot.setLeftTree(copyTree(root.leftTreeOf()));
      dot.setRightTree(copyTree(root.rightTreeOf()));
      root.setShadow(dot);
      return dot;
   }

   int insertCopy(Dot root, Dot p[], int ss) {
      if (root == null) return ss;
      p[ss++] = root;
      ss = insertCopy(root.leftTreeOf(), p, ss);
      ss = insertCopy(root.rightTreeOf(), p, ss);
      return ss;
   }

   void reLevel(Dot dot, int ind, int lvl) {
      if (dot == null) return;
      dot.setLevel(lvl);
      dot.setIndent(ind);
      reLevel(dot.leftTreeOf(),  2*ind, lvl+1);
      reLevel(dot.rightTreeOf(), 2*ind+1 , lvl+1);
   }

   void leftRotate(Dot chld, Dot prnt) {
      prnt.setLeftTree(chld.rightTreeOf());
      chld.setRightTree(prnt.leftTreeOf().leftTreeOf());
      prnt.leftTreeOf().setLeftTree(chld);
      reLevel(head, 0, 0);
   }

   void srightRotate(Dot chld, Dot prnt) {
      prnt.setRightTree(chld.leftTreeOf());
      chld.setLeftTree(prnt.rightTreeOf().rightTreeOf());
      prnt.rightTreeOf().setRightTree(chld);
      reLevel(head, 0, 0);
   }

   void rightRotate(Dot chld, Dot prnt) {
      prnt.setLeftTree(chld.leftTreeOf());
      chld.setLeftTree(prnt.leftTreeOf().rightTreeOf());
      prnt.leftTreeOf().setRightTree(chld);
      reLevel(head, 0, 0);
   }

   void sleftRotate(Dot chld, Dot prnt) {
      prnt.setRightTree(chld.rightTreeOf());
      chld.setRightTree(prnt.rightTreeOf().leftTreeOf());
      prnt.rightTreeOf().setLeftTree(chld);
      reLevel(head, 0, 0);
   }

   void rightRotate(Dot dot) {
      head = dot.leftTreeOf();
      dot.setLeftTree(head.rightTreeOf());
      head.setRightTree(dot);
      reLevel(head, 0, 0);
   }

   void sleftRotate(Dot dot) {
      head = dot.rightTreeOf();
      dot.setRightTree(head.leftTreeOf());
      head.setLeftTree(dot);
      reLevel(head, 0, 0);
   }
  
   int upward() {
      if (ssindex > 0) {
         if (ss[ssindex-1].colorOf() == Color.red &&
             ss[ssindex].colorOf() == Color.red) {
            if (ssindex > 1 && 
		ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
                ss[ssindex-1] == ss[ssindex-2].leftTreeOf()) {
               if (ss[ssindex-2].rightTreeOf() == null ||
                   ss[ssindex-2].rightTreeOf().colorOf() == Color.black) {
                  if (ssindex > 2) {
                     if (ss[ssindex-3].leftTreeOf() == ss[ssindex-2])
                        rightRotate(ss[ssindex-2], ss[ssindex-3]);
                     else
                        srightRotate(ss[ssindex-2], ss[ssindex-3]);
                     play(getCodeBase(), "audio/ah.au");
                     rev1 = ss[ssindex-1];
                     rev2 = ss[ssindex-2];
                     ss[ssindex-2] = ss[ssindex-1];
                     ssindex -= 2;
                     return 1;
                  } else {
                     rightRotate(ss[ssindex-2]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = head;
                     rev2 = head.rightTreeOf();
                     ssindex = 0;
                     return 1;
                  }
               } else {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            } else if (ssindex > 1 && 
		       ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
		       ss[ssindex-1] == ss[ssindex-2].leftTreeOf()) {
               if (ss[ssindex-2].rightTreeOf() == null ||
                   ss[ssindex-2].rightTreeOf().colorOf() == Color.black) {
                  leftRotate(ss[ssindex-1], ss[ssindex-2]);
                  play(getCodeBase(), "audio/ah.au");
                  Dot tt = ss[ssindex];
                  ss[ssindex] = ss[ssindex-1];
                  ss[ssindex-1] = tt;
                  return 1;
               } else {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            } else if (ssindex > 1 && 
		       ss[ssindex] == ss[ssindex-1].rightTreeOf() &&
		       ss[ssindex-1] == ss[ssindex-2].rightTreeOf()) {
               if (ss[ssindex-2].leftTreeOf() == null ||
                   ss[ssindex-2].leftTreeOf().colorOf() == Color.black) {
                  if (ssindex > 2) {
                     if (ss[ssindex-3].rightTreeOf() == ss[ssindex-2])
                        sleftRotate(ss[ssindex-2], ss[ssindex-3]);
                     else
                        leftRotate(ss[ssindex-2], ss[ssindex-3]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = ss[ssindex-1];
                     rev2 = ss[ssindex-2];
                     ss[ssindex-2] = ss[ssindex-1];
                     ssindex -= 2;
                     return 1;
                  } else {
                     sleftRotate(ss[ssindex-2]);
                     play(getCodeBase(), "audio/ooh.au");
                     rev1 = head;
                     rev2 = head.leftTreeOf();
                     ssindex = 0;
                     return 1;
                  }
               } else {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            } else if (ssindex > 1 && 
		       ss[ssindex] == ss[ssindex-1].leftTreeOf() &&
		       ss[ssindex-1] == ss[ssindex-2].rightTreeOf()) {
               if (ss[ssindex-2].leftTreeOf() == null ||
                   ss[ssindex-2].leftTreeOf().colorOf() == Color.black) {
                  srightRotate(ss[ssindex-1], ss[ssindex-2]);
                  play(getCodeBase(), "audio/ah.au");
                  Dot tt = ss[ssindex];
                  ss[ssindex] = ss[ssindex-1];
                  ss[ssindex-1] = tt;
                  return 1;
               } else {
                  rev1 = ss[ssindex-2];
                  rev2 = ss[ssindex-2].leftTreeOf();
                  rev3 = ss[ssindex-2].rightTreeOf();
                  ssindex -= 2;
                  return 2;
               }
            }
         } else { return 0; }
      }
      return 0;
   }

   Dot insertDot(Dot dot, Dot root) {
      if (root == null) return null;

      if (dot.numberOf() == root.numberOf()) {
         play(getCodeBase(), "audio/drip.au");
			ssindex = 0;
         return newest = temp = null;
      } else if (dot.numberOf() < root.numberOf()) {
         dot.setLevel(root.levelOf()+1);
         dot.setIndent(2*root.indentOf());
         if (root.leftTreeOf() == null) {
            stopdot.setColor(Color.green);
            return stopdot;
         }
         return root.leftTreeOf();
      } else {
         dot.setLevel(root.levelOf()+1);
         dot.setIndent(2*root.indentOf()+1);
         if (root.rightTreeOf() == null) {
            stopdot.setColor(Color.yellow);
            return stopdot;
         }
         return root.rightTreeOf();
      }
   }

   Dot reverseColor(Dot dot) {
      if (dot.colorOf() == Color.black) dot.setColor(Color.red);
      else
      if (dot.colorOf() == Color.red) dot.setColor(Color.black);
      return null;
   }
   
   void deleteDot(Dot d) {
      int m;
      for (int k=0 ; k < ndots ; k++) {
         if (dot[k] == null) continue;
         if (dot[k] == d) {
            dot[k] = null;
            break;
         }
      }
      for (int k=0 ; k < ndots ; k++) {
         if (dot[k] == null) continue;
         if (dot[k].leftTreeOf() == d) {
            dot[k].setLeftTree(null);
            break;
         }
         if (dot[k].rightTreeOf() == d) {
            dot[k].setRightTree(null);
            break;
         }
      }
      for (int k=0 ; k < ndots ; k++) if (dot[k] != null) return;
      head = null;
      return;
   }

   Dot parentOf (Dot d) {
      for (int k=0 ; k < ndots ; k++) {
         if (dot[k] == null) continue;
         if (dot[k].leftTreeOf() == d) return dot[k];
         if (dot[k].rightTreeOf() == d) return dot[k];
      }
      return null;
   }

   public boolean action (Event evt, Object arg) {
      if (evt.target.equals(colorit)) {
	 if (panel.saved_pick != null) {
	    if (panel.saved_pick.colorOf() == Color.red)
	       panel.saved_pick.setColor(Color.black);
	    else
	       panel.saved_pick.setColor(Color.red);
	 }
      } else if (evt.target.equals(startbutton)) {
         ndots = cndots = ssindex = 0;
         head = chead = rev1 = rev2 = rev3 = newest = temp = null;
         for (int i=0 ; i < 100 ; i++) { dot[i] = cdot[i] = ss[i] = null; }
         bgcolor = new Color(190, 190, 190);
         inserting = false;
         return super.action(evt, arg);
      } else if (evt.target.equals(undobutton)) {
         if (panel.removingOf()) return super.action(evt, arg);
         if (chead == null) return super.action(evt, arg);
         for (int i=0 ; i < ndots ; i++) {
             if (dot[i] == null) continue;
             if ((shadow = dot[i].shadowOf()) != null) {
               shadow.setLeft(dot[i].leftOf());
               shadow.setTop(dot[i].topOf());
            }
         }
         for (int i=0 ; i < cndots ; i++) { dot[i] = cdot[i]; ss[i] = null; }
         ndots = cndots;
         head = chead;
         chead = null;
         rev1 = rev2 = rev3 = newest = temp = null;
         ssindex = 0;
         return super.action(evt, arg);
      } else if (evt.target.equals(addbutton)) {
         if (rev1 != null || rev2 != null || rev3 != null ||
             temp != null || (head == null && newest != null) ||
             ssindex != 0 || (head != null && head.colorOf() != Color.black)) {
            play(getCodeBase(), "audio/ooh.au");
         } else if (newest == null && !panel.removingOf()) {
            int num = 0;
            inserting = true;
            ndots = insertCopy(head = copyTree(head), dot, 0); /* try it */
            cndots = insertCopy(chead = copyTree(head), cdot, 0);
            ssindex = 0;
            try { num = Integer.parseInt(val.getText()); }
            catch (NumberFormatException e) { return super.action(evt, arg); }
            newest = new Dot(num, Color.red);
            newest.setLevel(0);
            newest.setIndent(0);
            temp = head;
            bgcolor = new Color(0,190,190);
         }
         return super.action(evt, arg);
      } else if (evt.target.equals(nextbutton)) {
         if (panel.removingOf() && head != null) {  // deleting a node
	    if (step == 0) { // beginning to go down;
               if (panel.dotOf().leftTreeOf() != null &&
                   panel.dotOf().rightTreeOf() != null) { // both children
                  Dot P = parentOf(panel.dotOf());
                  Dot A = panel.dotOf().leftTreeOf();
                  Dot B = panel.dotOf();
                  Dot C = panel.dotOf().rightTreeOf();

                  if (C != null && 
		      C.leftTreeOf() == null && C.rightTreeOf() == null) {
                     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;
                        C.setLeftTree(A.rightTreeOf());
                        A.setRightTree(C);
			if (B != null && B.colorOf() == Color.red) {
			   A.setColor(Color.black);
			   C.leftTreeOf().setColor(Color.red);