redblacktree.java

Java数据结构开发包

      }
      else {
	boolean founduncle = false;
	while (!founduncle){
	  current = tree_.parent(current);
	  if (tree_.leftChild(tree_.parent(current)) == current)
	    founduncle = true;
	  if (current == tree_.root())
	    throw new BoundaryViolationException("Empty tree");
	}
	current = tree_.parent(current);
      }
    }
    else {
      current = tree_.rightChild(current);
      while (!tree_.isExternal(current))
	current = tree_.leftChild(current);
    }
    return (current);
  }
    
    
  /**
   * Takes O(log N) time -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   * Moves the current node backward, relative to an in-order ordering
   * of the nodes.
   * @return the in-order-previous of the current position, including
   * the leaves
   * @exception BoundaryViolationException If the given node is last
   * @param current The position to take the prev of
   */
  private Position prev(Position current) throws BoundaryViolationException {
    if (tree_.isExternal(current)) {
      if (current == tree_.root())
	throw new BoundaryViolationException("Empty tree");
      if  (tree_.rightChild(tree_.parent(current)) == current){
	current = tree_.parent(current);
      }
      else{
	boolean founduncle = false;
	while (!founduncle){
	  current = tree_.parent(current);
	  if (tree_.rightChild(tree_.parent(current)) == current)
	    founduncle = true;
	  if (current == tree_.root())
	    throw new BoundaryViolationException("Empty tree");
	}
	current = tree_.parent(current);
      }
    }
    else {
      current = tree_.leftChild(current);
      while (!tree_.isExternal(current))
	current = tree_.rightChild(current);
    }
    return (current);	
  }

  
  /**
   * Takes O(log N) time to traverse the height of the tree
   * where N is the number of locators in the tree and O(logN) is
   * the height of the tree
   */
  public Locator first(){
    Locator before = InspectableOrderedDictionary.BOUNDARY_VIOLATION;
    Position cur = tree_.root();
    while (!tree_.isExternal(cur)){
//       before = checkLocator(cur.element());
      before = (RBTLocator)cur.element();
      cur = tree_.leftChild(cur);
    }
    return before;
  }

  
  /**
   * Takes O(log N) time to traverse the height of the tree
   * where N is the number of locators in the tree and O(logN) is
   * the height of the tree
   */
  public Locator last(){
    Locator before = InspectableOrderedDictionary.BOUNDARY_VIOLATION;
    Position cur = tree_.root();
    while (!tree_.isExternal(cur)){
//       before = checkLocator(cur.element());
      before = (RBTLocator)cur.element();
      cur = tree_.rightChild(cur);
    }
    return before;
  }

  
  /**
   * Takes O(1) time
   * Convenience method for casting an  element of the underlying
   * tree, which should be a ColorHolder
   */
//   private ColorHolder checkHolder(Object treeElement) throws
//   InvalidAccessorException {
//     if (treeElement == null)
//       throw new InvalidMethodCallException
// 	("Tree element (ColorHolder) is null");
//     try{
//       return (ColorHolder) treeElement;
//     }
//     catch(ClassCastException cce) {
//       throw new InvalidMethodCallException("Tree element not a ColorHolder");
//     }
//   }

  
  /**
   * Takes O(1) time
   * Safety method for checking a locator given to us by the user
   * (checks whether this is its container)
   *
   * @param a The accessor
   * @return The casted RBTLocator
   */
  private RBTLocator checkLocator (Object a) throws
  InvalidAccessorException {
    if (a == null)
      throw new InvalidAccessorException("Locator is null");
    if (!(a instanceof RBTLocator))
      throw new InvalidAccessorException("Not a Locator");

    RBTLocator rbtl = (RBTLocator)a;

    if (rbtl.container() != this)
      throw new InvalidAccessorException("Locator from a different container");
    return rbtl;
  }


  /**
   * Takes O(log N) time -- where N = the number of locators in the
   * tree and O(logN) = the height of the tree -- may traverse down
   * the height one path
   *
   * Service method to search underlying tree recursively
   *
   * @param key Key to search for
   * @param subtreeRoot The subtree to search in
   */
  private Position findInSubtree(Object key, Position subtreeRoot) throws
  InvalidKeyException{
    Position node = subtreeRoot;

//     if (tree_.isExternal(subtreeRoot))
//       return subtreeRoot;
//     // search here first, then left or right if necessary
//     Object rootKey = checkLocator(subtreeRoot.element()) . key();
//     if (comparator_.isEqualTo(key, rootKey))
//       return subtreeRoot;
//     if (comparator_.isGreaterThan(key,rootKey))
//       return findInSubtree(key,tree_.rightChild(subtreeRoot));
//     else
//       return findInSubtree(key, tree_.leftChild(subtreeRoot));

    while (tree_.isInternal(node)) {
//       Object nodeKey = checkLocator(node.element()).key();
      Object nodeKey = ((RBTLocator)node.element()).key();
      int result = comparator_.compare(key,nodeKey);
      if (result == 0)
	break;
      else if (result < 0)
	node = tree_.leftChild(node);
      else
	node = tree_.rightChild(node);
    }
    return node;
  }

  
  // convenience methods for dealing with the fact that colors conceptually
  // belong to positions of the underlying tree, but in implementation
  // colors are stored by locators

  /**
   * Returns whether or not the given position of the underlying tre
   * is red; for visualization/testing purposes.
   *
   * @param p The position to check
   */
  public final boolean isRed (Position p) {
//     return checkHolder(p.element()).color()==RED;
    return ((ColorHolder)p.element()).color() == RED;
  }

  
  /**
   * Returns whether or not the given position of the underlying tre
   * is black; for visualization/testing purposes.
   *
   * @param p The position to check
   */
  public final boolean isBlack (Position p) {
//     return checkHolder(p.element()).color()==BLACK;
    return ((ColorHolder)p.element()).color() == BLACK;
  }

  
  /**
   * Returns whether or not the given position of the underlying tre
   * is double-black; for visualization/testing purposes.
   *
   * @param p The position to check
   */
  public final boolean isDoubleBlack (Position p) {
//     return checkHolder(p.element()).color()==DOUBLEBLACK;
    return ((ColorHolder)p.element()).color() == DOUBLEBLACK;
  }

  
  private final void makeRed (Position p) {
    assert tree_.isInternal(p) : "External nodes should never be red!";
//     checkLocator (p.element()).setColor(RED);
    ((RBTLocator)p.element()).setColor(RED);
  }

  
  private final void makeBlack (Position p) {
    if (tree_.isExternal(p))
      tree_.replaceElement(p,bch_);
    else
//       checkLocator (p.element()).setColor (BLACK);
      ((RBTLocator)p.element()).setColor(BLACK);
  }

  
  private final void makeDoubleBlack (Position p) {
    if (tree_.isExternal(p))	
      tree_.replaceElement(p,dbch_);
    else
//       checkLocator (p.element()).setColor (DOUBLEBLACK);
      ((RBTLocator)p.element()).setColor(DOUBLEBLACK);
  }


  /**
   * Used for visualization and testers
   */
  public InspectableBinaryTree inspectableBinaryTree(){
    return tree_;
  }

  
  public String toString(){
    return ToString.stringfor(this);
  }

  
  /**
   * Any class implementing this interface has a color. Positions are colored
   * by placing an implementation of this class in their element.
   */
  private static interface ColorHolder{      
    /**
     * Package-friendly because the compiler doesn't allow private interface
     * methods
     * @return my position's color
     */
    int color();
  }

  
  /**
   * The color holder for black external positions
   */
  private static class BlackColorHolder implements ColorHolder{
    
    /**
     * Takes O(1) time
     * @return my position's color -- BLACK
     */
    public final int color(){ return BLACK;}

  }


  /**
   * The color holder for double-black external positions
   */
  private static class DoubleBlackColorHolder implements ColorHolder{
    
    /**
     * Takes O(1) time
     * @return my position's color -- DOUBLEBLACK
     */
    public final int color(){ return DOUBLEBLACK;}

  }


  /**
   * Data-holder class: holds color, key, and position in underlying tree,
   * plus administrative info.  
   * <p>
   */
  private static class RBTLocator implements Locator, ColorHolder{
      
    /**
     * The color of the position this holder is in
     */
    private int color_ = RED;

    /**
     * The tree position this color holder is associated with
     */
    private Position treepos_;

    /**
     * This locator's key
     */
    private Object key_;

    /**
     * This locator's element
     */
    private Object element_;

    /**
     * This locator's container
     */
    private RedBlackTree container_;

    
    /**
     * Takes O(1) time
     * A constructor for setting all RBTLocator fields
     */
    private RBTLocator(Object key, Object element,
		       RedBlackTree container, Position position) {
      key_ = key;
      element_ = element;
      container_ = container;
      treepos_ = position;
    }

    
    /**
     * Takes O(1) time
     *  @return  this node's container.
     */
    private final InspectableContainer container(){
      return container_;
    }

    
    /**
     * Takes O(1) time
     *  @param this node's new container.
     */
    private final void setContainer(RedBlackTree container){
      container_ = container;
    }

    
    /**
     * Takes O(1) time
     */
    public final Object element(){
      return element_;
    }

    
    /**	
     * Takes O(1) time
     * Replaces my element
     * @param newElement my new element
     */
    private final void setElement(Object element) { element_ = element; }

    
    /**
     * Takes O(1) time
     * @return my key