redblacktree.java

Java数据结构开发包

      return BOUNDARY_VIOLATION;
    }
  }

  
  /**
   * Takes O(logN) time -- may need to traverse the height of the tree
   * to find the next note that we do not return color-locators in the
   * leaves -- we only return key locators.
   */
  public Locator before(Locator locator) throws InvalidAccessorException {
    Position p = checkLocator(locator).treePosition();
    // p is an internal (if there are no bugs...)
    p = prev(p); // now points to a leaf
    try {
//       return checkLocator(prev(p).element());
      return (RBTLocator)prev(p).element();
    }
    catch (BoundaryViolationException bve) {
      return BOUNDARY_VIOLATION;
    }
  }

  
  /**
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   * The worst-case insertion would restructure once each step up the tree.
   */    
  public Locator insert(Object key, Object element) throws
  InvalidKeyException {
    Locator toReturn = new RBTLocator(key,element,this,null);
    insertLoc (toReturn);
    return toReturn;
  }

  
  /**
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * The worst-case insertion would restructure once each step up the tree.
   * Finds the proper BST place to put the new locator
   * Places it in colored red, and then checks if the tree
   * still maintains Red Black Tree properties; if not,
   * go to the insertion cases
   * This method is private, because we currently do not have the ability
   * to insert a free-floating locator in KBCs.
   *
   * @param loc The locator to insert
   */    
  private void insertLoc (Locator loc) throws InvalidKeyException,
  InvalidAccessorException {
    if (loc == null)
      throw new InvalidAccessorException("Null locator passed in.");
    RBTLocator rbtl = null;
    try{
      rbtl = (RBTLocator) loc;
    }
    catch (ClassCastException e){
      throw new InvalidAccessorException("Wrong type of locator passed in.");
    }
    if ( ! comparator_.isComparable(rbtl.key()))
      throw new InvalidKeyException("Key to insert is not comparable");
      
    // find a leaf at which to insert, expand the leaf, and do the deed
    Position p = findInSubtree(rbtl.key(), tree_.root());  
    if (tree_.isInternal(p)) {
      p = next(p);
    }
    tree_.expandExternal(p);
    tree_.replaceElement(p, rbtl);	
    rbtl.setContainer(this);
    rbtl.setPosition(p);
    makeRed(p);
      
    // color both new leaves black
    tree_.replaceElement(tree_.rightChild(p),bch_);
    tree_.replaceElement(tree_.leftChild(p), bch_);
      
    checkDoubleRed(p);

    // root should always be black 
    makeBlack (tree_.root());
      
    size_++;
  }

  
  /**
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * Check for double reds, then rotate or promote if necessary
   * Protected for purposes of allowing snapshots during visualization
   * @param p The position that would be the child of the two double reds
   */
  protected void checkDoubleRed(Position p) {
    if (tree_.isRoot(p)) return; //the first node inserted can't have doublered
    Position parent = tree_.parent(p);
    if (tree_.isRoot(parent)) return; // the root will be made black in insertloc
    else if (isRed(parent)) { 
      Position uncle = tree_.sibling(parent);
      if (isRed(uncle)) {
	colorPromotion(parent,uncle);
      }
      else {
	// rotate and correct the colors, and we're done
	Position newroot = tree_.restructure(p);
	makeBlack (newroot);
	makeRed (tree_.leftChild(newroot));
	makeRed (tree_.rightChild(newroot));
      }
    }
  }

  
  /**
   * Takes O(logN) time -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * Do a color promotion and then check if colors are now wrong higher up   
   * Protected for purposes of allowing snapshots during visualization
   * @param parent The position that would be the parent of the two double reds
   * @param uncle parent's sibling
   */
  protected void colorPromotion(Position parent, Position uncle) {    
    makeBlack (parent);
    makeBlack (uncle);
    Position grandParent = tree_.parent(parent);
    makeRed (grandParent);
    //check for double red at the next level up
    checkDoubleRed(grandParent);
  }

  
  /**
   * Takes O(RlogN) time
   * where R = the number of objects with key key
   * and log N = the height of the tree (N locators in the tree)
   * (one removal case per each object)
   */ 
  public LocatorIterator removeAll (Object key) throws InvalidKeyException{
    LocatorIterator toret = findAll(key);
    while (toret.hasNext()) {
      remove(toret.nextLocator());
    }
    // since iterators have snapshot semantics, we can reuse toret
    toret.reset();
    return toret;
  }

  
  /**
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * The worst-case removal would restructure once each step up the tree.
   * Finds the locator to remove, then removes it.
   */
  public Locator removeKey (Object key) throws InvalidKeyException{
    Locator toret = find(key);
    remove(toret);
    return toret;
  }

  
  /**
   * Takes O(logN) time  -- where N = the number of locators in the tree
   * and O(logN) = the height of the tree
   *
   * The worst-case removal would restructure once each step up the tree.
   * 
   * Ensures that the locator has a leaf child (Swapping if necessary)
   * Then removes it. 
   * This leaves a double-black node, which we then resolve to a black node.
   * This may propagate the double-black up the tree, in which case
   * more resolutions will be necessary.
   * The number of resolutions (repairs to the tree) will be <= O(log N)
   *
   */
  public void remove (Locator locator) throws InvalidAccessorException {
    RBTLocator loc = checkLocator(locator);
    Position locpos = loc.treePosition();

    assert tree_.isInternal(locpos)
      : "Locator's position is an external -- indicates bug in r-b tree";

    // first need to assure that the position to be removed from the
    // tree is above a leaf.  Either it is already so or we have to swap
    // to make it so.
    Position leaf = null; 
	
    if ( tree_.isInternal(tree_.rightChild(locpos)) &&
	 tree_.isInternal(tree_.leftChild (locpos)) ) {
      // swap locpos with its predecessor internal node
      leaf = prev(locpos);
      Position swapwith = tree_.parent( leaf );
//       RBTLocator swapwithRBTLocator = checkLocator( swapwith.element() );
      RBTLocator swapwithRBTLocator = (RBTLocator)swapwith.element();

      // swap semantics: leave colors associated with their
      // tree positions while swapping the locators stored at the
      // positions.  But colors are implemented as being held by the
      // locators, so we swap locators, update locators' position-pointers
      // for consistency, then reswap the locators' colors.
      tree_.swapElements(locpos, swapwith); 
      swapwithRBTLocator.setPosition(locpos);
      loc.setPosition(swapwith);
      int tempColor = swapwithRBTLocator.color();
      swapwithRBTLocator.setColor(loc.color());
      loc.setColor(tempColor);
    }
    else 
      if (tree_.isExternal(tree_.leftChild(locpos))) 
	leaf = tree_.leftChild(locpos);
      else // right child must be external 
	leaf = tree_.rightChild(locpos);

    // now the locator to be removed is above a leaf, so we can 
    // remove above the leaf.
    // But first: leaf's sibling is either a leaf or a minimal subtree,
    // and it will move up a level to become locpos's parent's new child
    Position leafsib = tree_.sibling(leaf);
    tree_.removeAboveExternal(leaf);
	
    // if locpos was black (after any swap), then by removing it we 
    // decreased the black depth of the leaves in leafsib's subtree
    if (loc.color()==BLACK){ 
      recolorAfterRemove(leafsib);
    }
    makeBlack( tree_.root() ); 
    loc.setContainer(null);
    size_--;
  }
    

  /**
   * Takes O(logN) time -- where N = the number of locators in the
   * tree and O(logN) = the height of the tree.
   *
   * Recolors after removal, i.e., delegate to appropriate case; can
   * be called recursively for case 2.  Protected for purposes of
   * allowing snapshots during visualization
   *
   * @param p The node to recolor above
   */
  protected void recolorAfterRemove(Position p) {
      
    assert tree_.contains(p) : "Position is from the wrong tree";
      
    if ( (isBlack(p) || isDoubleBlack(p)) &&
	 ! tree_.isRoot(p) ) {

      // if p is black then
      // p's black depth is too low, so insert an illegal extra black
      // edge above p to restore p's black depth.  Then deal
      // with the illegal edge
	  
      makeDoubleBlack(p ); 

      //if sib is red, then case3 and continue to case 1 or case 2
      Position sibling = tree_.sibling(p);
      if (isRed(sibling)){
	case3( sibling );
	sibling = tree_.sibling(p);
      }
      if (isBlack(sibling)) {
	Position parent = tree_.parent(p);
	Position sibLeft = tree_.leftChild(sibling);
	Position sibRight = tree_.rightChild(sibling);
		
	if (isBlack(sibLeft)&&isBlack(sibRight)) {
	  case2(sibling);
	  if (isDoubleBlack(parent))//still a double black to resolve
	    recolorAfterRemove(parent);
	}else
	  if (isBlack(sibRight)&&isRed(sibLeft)) 
	    case1(sibling,sibLeft);
	  else
	    case1(sibling,sibRight);
      }
    }
    else makeBlack( p );
  }

  
  /**
   * Takes O(1) time
   * Implements case 1, the Restructuring case
   *
   * Protected for purposes of allowing snapshots during visualization
   *
   * @param y -- the sibling of the double-black node
   * @param z -- the red child of y
   */
  protected void case1(Position y, Position z){
    assert tree_.contains(y) && tree_.contains(z)
      : "Position is from the wrong tree";

    Position x = tree_.parent(y);// The parent of the double-black node
    Position r = tree_.sibling(y);//The double-black node

//     int xcolor = checkLocator((Locator)x.element()).color();
    int xcolor = ((RBTLocator)x.element()).color();

    Position b = tree_.restructure(z);// The root of the restructured subtree
    Position a = tree_.leftChild(b);
    Position c = tree_.rightChild(b);

    makeBlack(a);
    makeBlack(c);

//     checkLocator((Locator)b.element()).setColor(xcolor);
    ((RBTLocator)b.element()).setColor(xcolor);
    makeBlack(r);
  }


  /**
   * Takes O(1) time
   * Implements case 2, the Recoloring case
   *
   * Protected for purposes of allowing snapshots during visualization
   * @param y -- the sibling of the double-black node
   */
  protected void case2(Position y){     
    assert tree_.contains(y) : "Position is from the wrong tree";

    Position x = tree_.parent(y);// The parent of the double-black node
    Position r = tree_.sibling(y);//The double-black node

    makeBlack(r);
    makeRed(y);
    if (isRed(x))
      makeBlack(x);
    else
      makeDoubleBlack(x);
  }

  
  /**
   * Takes O(1) time
   * Implements case 3, the Adjustment case    
   * Protected for purposes of allowing snapshots during visualization
   *
   * @param y -- the sibling of the double-black node
   */
  protected void case3(Position y){
    assert tree_.contains(y) : "Position is from the wrong tree";

    Position x = tree_.parent(y);// The parent of the double-black node
    Position z = null;
    if (tree_.rightChild(x)==y)
      z = tree_.rightChild(y);
    else
      z = tree_.leftChild(y);

    tree_.restructure(z);

    makeBlack(y);
    makeRed(x);
  }


  /**
   * 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 forward, in order
   * @return Inorder-next of the current node.
   * @exception BoundaryViolationException If the given node is last
   * @param current The position to take the next of
   */
  private Position next(Position current) throws BoundaryViolationException {
    if (tree_.isExternal(current)){
      if (current == tree_.root())
	throw new BoundaryViolationException("Empty tree");
      if  (tree_.leftChild(tree_.parent(current)) == current){
	current = tree_.parent(current);