redblacktree.java

Java数据结构开发包

     */	
    public final Object key() { return key_; }

    
    /**	
     * Takes O(1) time
     * Sets my key
     * @param key my new key
     */
    private final void setKey(Object key) { key_ = key; }

    
    /**
     * Takes O(1) time
     * @return my position in the tree
     */
    private final Position treePosition() { return treepos_; }

    
    /**
     * Takes O(1) time
     * Sets my position in the tree
     * @param position my new position
     */
    private final void setPosition(Position position) {treepos_ = position;}

    
    /**
     * Takes O(1) time
     * protected so subclass can print out in toString
     * @return my position's color
     */
    public final int color() { return color_; }

    
    /**
     * Takes O(1) time
     * protected so classes using my subclass can use me
     * Sets my position's color
     * @param color my new color
     */
    private final void setColor(int color) { color_ = color; }

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

  } // end of RBTLocator class def


  
  /**
   * A <code>BinaryTree</code> that supports AVL/RedBlack Tree restructuring. 
   * (also known as Tree Rotation -- see Goodrich,Tamassia ch.7) 
   * Has its own cut/link/replaceSubtree to keep operations O(1)
   * with underscores to denote the O(1) versions
   * (we can be free of the responsibility to do container modifications
   * because we are modifying only within our own structure)
   * Note that no external classes may call the O(1) versions; for
   * security, they must call the O(N) versions.
   * All other methods function as previous
   *
 * @author Ming-En Cho (mec)
 * @author Mike Boilen (mgb)
 * @author Mark Handy (mdh)
 * @author Ryan Shaun Baker (rsb)
   * @version JDSL 2.1.1 
   */
  private static class RestructurableNodeBinaryTree extends NodeBinaryTree {

    // used as globals during restructure(.)
    private Position grandchild_;
    private Position parent_;
    private Position grandparent_;
    protected boolean restructuring_ = false;

    
    public RestructurableNodeBinaryTree(){
      super();
    }

    
    protected RestructurableNodeBinaryTree(NBTNode n){
      super(n);
    }

    
    /**
     *
     * O(1)
     *
     * Performs a rotation (restructuring) of the following three nodes:
     * the node specified, its parent, and its grandparent.  The node
     * specified (call it x) winds up one or two levels closer to the root,
     * but the inorder traversal of the entire tree is unaffected. Takes
     * constant time, assuming that cut(.) and link(.) take constant time.
     *
     * The algorithm is <br>
     * <ol>
     * <li>detach the subtree rooted at grandparent from the main tree
     * <li>detach the four uninvolved subtrees (one child of grandparent,
     * one child of parent, both children of x)
     * <li> perform an inorder traversal on the resulting minitree (the
     * three involved nodes and the four vestigial leaves)
     * <li> cut the minitree apart and reassemble it so that the inorder-median
     * of the three involved nodes is the new root of the minitree
     * <li> put back the snipped-off subtrees, in order (they won't necessarily
     * reattach to their original parents)
     * <li> reattach the rotated subtree to the main tree, in the same place.
     * </ol>
     *
     * (see Goodrich,Tamassia ch.7)
     *
     * @param grandchild The position to rotate at.
     * @exception BoundaryViolationException if grandchild does not have a 
     * grandparent -- taking the rotation above the root -- or on the attempt 
     * to rotate around an external.
     * @exception InvalidAccessorException if <code>grandchild</code> is
     *  invalid
     */
    public Position restructure (Position grandchild) throws
    BoundaryViolationException, InvalidAccessorException {
	
      restructuring_ = true;

      if (isExternal(grandchild))
	throw new BoundaryViolationException("cannot rotate on an external");
	
      //positions involved in this rotation
      grandchild_ = grandchild;
      parent_ = parent(grandchild);
      grandparent_ = parent(parent_);

      // used later, to know where to reattach the rotated subtree
      // to the main tree
      boolean gparentIsRoot = isRoot(grandparent_);
      boolean gparentIsRightChild = false;
      Position ggparent = null;
      if (! gparentIsRoot) {
	ggparent = parent(grandparent_);
	if (rightChild(ggparent)==grandparent_)
	  gparentIsRightChild=true;
      }
	
      // cut off all of the subtrees that aren't involved in the rotation,
      // and cut the involved subtree off from the main tree
      RestructurableNodeBinaryTree subtree =  pruneSubtree();

      //traverse the tree, to find the order of the subtrees
      InOrderIterator iterator = new InOrderIterator(subtree);
	
      //cut apart the subtree

      iterator.nextPosition();
      Position zero  = iterator.position();
      iterator.nextPosition();
      Position left = iterator.position();	
      iterator.nextPosition();
      Position two = iterator.position();	
      iterator.nextPosition();
      Position center = iterator.position();	
      iterator.nextPosition();
      Position four = iterator.position();	
      iterator.nextPosition();
      Position right = iterator.position();	
      iterator.nextPosition();
      Position six = iterator.position();	

      RestructurableNodeBinaryTree grandchildTree = subtree._cut(grandchild_);
      RestructurableNodeBinaryTree parentTree = subtree._cut(parent_);
      RestructurableNodeBinaryTree grandparentTree
	= subtree._cut(grandparent_);	
      RestructurableNodeBinaryTree leftTree, rightTree, centerTree;
	
      //re-link the subtree
      if (grandchildTree.root()==center){
	centerTree = grandchildTree;
	if (parentTree.root()==right){
	  rightTree = parentTree;
	  leftTree = grandparentTree;
	}
	else{
	  rightTree = grandparentTree;
	  leftTree = parentTree;
	}
      }
      else{
	centerTree = parentTree;
	if (grandchildTree.root()==right){
	  rightTree = grandchildTree;
	  leftTree = grandparentTree;
	}
	else{
	  rightTree = grandparentTree;
	  leftTree = grandchildTree;
	}
      }

      // retrieve the uninvolved subtrees and reattach them
      // to the involved subtree
      leftTree._replaceSubtree(leftTree.leftChild(leftTree.root()),
			       (BinaryTree)zero.element());
      leftTree._replaceSubtree(leftTree.rightChild(leftTree.root()),
			       (BinaryTree)two.element());
	
      rightTree._replaceSubtree(rightTree.leftChild(rightTree.root()),
				(BinaryTree)four.element());
      rightTree._replaceSubtree(rightTree.rightChild(rightTree.root()),
				(BinaryTree)six.element());	  
	
      Position root = centerTree.root();

	
      centerTree._replaceSubtree(centerTree.leftChild(root), leftTree);
      centerTree._replaceSubtree(centerTree.rightChild(root), rightTree);
	
      // reattach the rotated subtree to the rest of the tree
      if ( gparentIsRoot ){
	_link(root(), centerTree);
      }
      else{
	if (gparentIsRightChild) {
	  _link(rightChild(ggparent), centerTree);
	}
	else {
	  _link(leftChild(ggparent), centerTree);
	}
      }
	
      restructuring_ = false;

      return root;
    }
    
    
    /**
     * Cut off all uninvolved subtrees before rotating, and store the
     * subtrees in the respective leaves left behind by the cutting.
     */
    private RestructurableNodeBinaryTree pruneSubtree() {
      RestructurableNodeBinaryTree temp1 = _cut(leftChild(grandchild_));
      this.replaceElement(leftChild(grandchild_), temp1);
	
      RestructurableNodeBinaryTree temp2 = _cut(rightChild(grandchild_));
      this.replaceElement(rightChild(grandchild_), temp2);
	
      RestructurableNodeBinaryTree temp3;
	
      if (grandchild_== rightChild(parent_)){
	temp3 = _cut(leftChild(parent_));
	this.replaceElement(leftChild(parent_), temp3);    
      }
      else{
	temp3 = _cut(rightChild(parent_));
	this.replaceElement(rightChild(parent_), temp3); 
      }
	
      RestructurableNodeBinaryTree temp4;
	
      if (parent_ == rightChild(grandparent_)){
	temp4 = _cut(leftChild(grandparent_));
	this.replaceElement(leftChild(grandparent_), temp4); 
      }
      else{
	temp4 = _cut(rightChild(grandparent_));
	this.replaceElement(rightChild(grandparent_), temp4); 
      }
	
      RestructurableNodeBinaryTree toret = _cut(grandparent_);
      toret._size = 7;   //always true at this point, and necessary for IOI
                         // to function properly
	
      return toret;
    }
    

    /**
     * Returns a new <code>RestructurableNodeBinaryTree.</code>
     * @return a RestructurableNodeBinaryTree
     */
    public Container newContainer() {
      return new RestructurableNodeBinaryTree();
    }

    
    /**
     * O(1)
     * modified from the code in NodeBinaryTree to function in O(1)
     * (includes removing container modification and not checking for
     * container)
     */
    private RestructurableNodeBinaryTree _cut (Position rootOfSubtree) {
      // cutting means replacing the subtree with a leaf (i.e., with a newly
      // constructed tree)
      RestructurableNodeBinaryTree nc
	= (RestructurableNodeBinaryTree)newContainer();
      return (RestructurableNodeBinaryTree)(_replaceSubtree(rootOfSubtree,nc));
    }


    /**
     * O(1)
     * modified from the code in NodeBinaryTree to function in O(1)
     * (includes removing container modification and not checking for
     * container)
     */
    private void _link (Position mustBeExternal, BinaryTree newSubtree) {
      NBTNode x = checkPosition (mustBeExternal);
      if (isInternal(x))
	throw new InvalidAccessorException
	  ("You can't link at an internal node");
      _replaceSubtree (mustBeExternal, newSubtree);
    }


    /** 
     * O(1)
     * modified from the code in NodeBinaryTree to function in O(1)
     * (includes removing container modification and not checking for
     * container)
     */
    private RestructurableNodeBinaryTree _replaceSubtree
      (Position subtreeRoot, BinaryTree newSubtree) {

      if ( ! (newSubtree instanceof NodeBinaryTree) )
	throw new InvalidContainerException("incompatible type of tree");
      RestructurableNodeBinaryTree toSwapIn
	= (RestructurableNodeBinaryTree) newSubtree;

      // get the roots of the subtrees to be swapped
      NBTNode oldSubtreeRoot = checkPosition (subtreeRoot);
      NBTNode newSubtreeRoot = (NBTNode) toSwapIn.root();

      oldSubtreeRoot.replaceSelf (newSubtreeRoot);

      // make a new tree out of the nodes swapped out; the constructor
      // makes a new tree wrapper pointing to oldSubtreeRoot
      // and forces oldSubtreeRoot to point up to its new container
      RestructurableNodeBinaryTree toReturn
	= new RestructurableNodeBinaryTree(oldSubtreeRoot);

      toReturn.restructuring_ = true;//it must be restructuring, because
      //that's the only thing this method can be used for

      return toReturn;
    }

 
    /**
     * We don't check container if the position is in the middle
     * of a restructuring operation -- otherwise this method is
     * the same as the one it overrides.
     */
    protected NBTNode checkPosition (Accessor a) throws
    InvalidAccessorException {
//       if (a==null)
// 	throw new InvalidAccessorException("null position");

//       if (!(a instanceof NBTNode))
// 	throw new InvalidAccessorException("position of wrong class: "
// 					   + a.getClass());

//       NBTNode n = (NBTNode) a;

//       if ((!restructuring_) && (!(this.contains(n)))) {
// 	throw new InvalidAccessorException
// 	  ("A different container holds this NBTNode!");
//       }
//       return n;
      return (NBTNode) a;
    }
    
  } // end of RestructurableBinaryTree class def

} // end of RedBlackTree class def