redblacktree.java

关于迭代器、构造器

		    // coloring gp red may introduce problems higher up
		    grandParent.setRed();
		    aunt.setBlack();
		    parent.setBlack();
		    grandParent.redFixup();
		} else {
		    if (isLeftChild()) {
			// this:red, parent:red, grand:black, aunt:black
			// ensure that this is on outside for later rotate
			parent.rotateRight();
			parent.redFixup(); // parent is now child of this
		    } else {
			// assertion: this is on outside
			// this:red, parent:red, gp: black, aunt:black
			// rotate right @ gp, and make this & gp red sibs
			// under black parent
			grandParent.rotateLeft();
			grandParent.setRed();
			parent.setBlack();
		    }
		}
	    }
	}
    }

    /**
     * Remove an value "equals to" the indicated value.  Only one value
     * is removed, and no guarantee is made concerning which of duplicate
     * values are removed.  Value returned is no longer part of the
     * structure
     * 
     * @param val Value sought to be removed from tree
     * @return Actual value removed from tree
     * @pre c is non-null
     * @post the value is removed; resulting tree is returned
     */
    public RedBlackTree remove(Comparable c)
    {
	// find the target node - the node whose value is removed
	RedBlackTree target = locate(c);
	if (target.isEmpty()) return root();

	// determine the node to be disconnected:
	// two cases: if degree < 2 we remove target node;
	//            otherwise, remove predecessor
	RedBlackTree freeNode;
	if (target.left().isEmpty() ||
	    target.right().isEmpty()) // simply re-root tree at right
	{
	    // < two children: target node is easily freed
	    freeNode = target;
	} else {
	    // two children: find predecessor
	    freeNode = target.left();
	    while (!freeNode.right().isEmpty())
	    {
		freeNode = freeNode.right();
	    }
	    // freeNode is predecessor
	}

	target.value = freeNode.value; // move value reference

	// child will be orphaned by the freeing of freeNode;
	// reparent this child carefully (it may be EMPTY)
	RedBlackTree child;
	if (freeNode.left().isEmpty())
	{
	    child = freeNode.right();
	} else {
	    child = freeNode.left();
	}

	// if child is empty, we need to set its parent, temporarily
	child.setParent(freeNode.parent());
	if (!freeNode.isRoot())
	{
	    if (freeNode.isLeftChild())
	    {
		freeNode.parent().setLeft(child);
	    } else {
		freeNode.parent().setRight(child);
	    }
	}

	// Assertion: child has been reparented
	RedBlackTree result = child.root();	
	if (freeNode.isBlack()) child.blackFixup();
	return result.root();
    }

    /**
     * If a black node has just been removed above this;
     * this node is the root of a black-height balanced tree, but
     * the ancestors of this node are shy one black node on this branch.
     * This method restores black-height balance to such an imbalanced
     * tree.
     *
     * @pre a black node has just been removed above this;
     *      this node is the root of a black-height balanced tree, but
     *      the ancestors of this node are shy one black node on this branch
     * @post the tree is black-height balanced
    */
    protected void blackFixup()
    {
	// if root - we're actually balanced; if red, set to black
	if (isRoot() || isRed())
	{
	    setBlack();
	} else {
	    RedBlackTree sibling, parent; // temporary refs to relates
	    // we hold onto our parent because the nodes shift about
	    parent = parent();

	    if (isLeftChild())
	    {
		// our sibling: can't be a leaf (see text)
		sibling = parent.right();

		if (sibling.isRed()) // and, thus, parent is black
		{
		    // lower this, but leave black heights the same
		    // then reconsider node with a red parent
		    sibling.setBlack();
		    parent.setRed();
		    parent.rotateLeft();
		    blackFixup(); // this node might have adopted 
		} else
		if (sibling.left().isBlack() && sibling.right().isBlack())
		{
		    // sibling black with black children: sib can be red
		    // remove sib as one black node in sibling paths, and
		    // push missing black problem up to parent
		    sibling.setRed();
		    parent.blackFixup();
		} else {
		    if (sibling.right().isBlack())
		    {
			// this:black, sib:black, sib.l:red, sib.r:black
			// heighten sibling tree, making sib:r red and
			// sib.l black (both sib.l's children were black)
			sibling.left().setBlack();
			sibling.setRed();
			sibling.rotateRight();
			sibling = parent.right();
		    }
		    // this: black, sib:black, sib:l black, sib.r:red 
		    // this tree deepens with parent as new black node
		    // sibling holds the previous parent color and
		    // sibling color (black) moves down to right;
		    // this adds a black node to all paths in this tree
		    // so we're done; finish by checking color of root
		    sibling.setRed(parent.isRed()); // copy color
		    parent.setBlack();
		    sibling.right().setBlack();
		    parent.rotateLeft();
		    root().blackFixup(); // finish by coloring root
		}
	    } else { // isRightChild
		// our sibling: can't be a leaf (see text)
		sibling = parent.left();

		if (sibling.isRed()) // and, thus, parent is black
		{
		    // lower this, but leave black heights the same
		    // then reconsider node with a red parent
		    sibling.setBlack();
		    parent.setRed();
		    parent.rotateRight();
		    blackFixup(); // this node might have adopted 
		} else
		if (sibling.left().isBlack() && sibling.right().isBlack())
		{
		    // sibling black with black children: sib can be red
		    // remove sib as one black node in sibling paths, and
		    // push missing black problem up to parent
		    sibling.setRed();
		    parent.blackFixup();
		} else {
		    if (sibling.left().isBlack())
		    {
			// this:black, sib:black, sib.r:red, sib.l:black
			// heighten sibling tree, making sib:l red and
			// sib.r black (both sib.r's children were black)
			sibling.right().setBlack();
			sibling.setRed();
			sibling.rotateLeft();
			sibling = parent.left();
		    }
		    // this: black, sib:black, sib:r black, sib.l:red 
		    // this tree deepens with parent as new black node
		    // sibling holds the previous parent color and
		    // sibling color (black) moves down to left;
		    // this adds a black node to all paths in this tree
		    // so we're done; finish by checking color of root
		    sibling.setRed(parent.isRed()); // copy color
		    parent.setBlack();
		    sibling.left().setBlack();
		    parent.rotateRight();
		    root().blackFixup(); // finish by coloring root
		}
	    } 
	}
    }

    /**
     * Determines if the red black search tree contains a value
     *
     * @param val The value sought.  Should be non-null
     * @return True iff the tree contains a value "equals to" sought value
     *
     * @pre c is non-null
     * @post returns true iff c is contained within the tree
     */
    public boolean contains(Comparable c)
    {
	return locate(c) != null;
    }
    
    /**
     * Locates a value in the search tree or returns the largest value
     * less than <code>value</code>.
     *
     * @pre c is non-null
     * @post returns a node of this tree that contains c, or null
     */
    protected RedBlackTree locate(Comparable c)
    {
	if (isEmpty()) return null;
	int relation = c.compareTo(value());
	if (relation == 0) return this;
	if (relation < 0) return left().locate(c);
	else return right().locate(c);
    }

    /**
     * Returns a c-equivalent value from tree, or null.
     *
     * @param c The c-equivalent value we are looking for in the tree.
     * @pre c is non-null
     * @post returns a c-equivalent value from tree, or null
     */
    public Comparable get(Comparable c)
    {
	RedBlackTree n = locate(c);
	if (n == null) return null;
	else return (Comparable)n.value();
    }

    /**
     * Returns true if this node is consistently structured
     *
     * @post returns true if this node is consistently structured
     */
    public boolean consistency()
    {
	return wellConnected(null) && redConsistency() && blackConsistency();
    }

    /**
     * Returns the black height of this subtree.
     *
     * @pre tree is black-height balanced
     * @post returns the black height of this subtree
     */
    protected int blackHeight()
    {
	if (isEmpty()) return 0;
	if (isBlack()) return 1 + left().blackHeight();
	else return  left().blackHeight();
    }

    /**
     * Returns true if no red node in subtree has red children
     * 
     * @post returns true if no red node in subtree has red children
     */
    protected boolean redConsistency()
    {
	if (isEmpty()) return true;
	if (isRed() && (left().isRed() || right().isRed())) return false;
	return left().redConsistency() && right().redConsistency();
    }

    /**
     * Returns true if black properties of tree are correct
     *
     * @post returns true if black properties of tree are correct
     */
    protected boolean blackConsistency()
    {
	if (!isRoot()) // must be called on root
	{
	    Assert.debug("Tree consistency not tested at root.");
	    return false;
	}
	if (!isBlack()) // root must be black
	{
	    Assert.debug("Root is not black.");
	    return false;
	}
	// the number of black nodes on way to any leaf must be same
	if (!consistentlyBlackHeight(blackHeight()))
	{
	    Assert.debug("Black height inconsistent.");
	    return false;
	}
	return true;
    }

    /**
     * Checks to make sure that the black height of tree is height
     * @post checks to make sure that the black height of tree is height
     */
    protected boolean consistentlyBlackHeight(int height)
    {
	if (isEmpty()) return height == 0;
	if (isBlack()) height--;
	return left().consistentlyBlackHeight(height) &&
	    right().consistentlyBlackHeight(height);
    }

    /**
     * Returns true iff this tree is well-connected.
     */
    public boolean wellConnected(RedBlackTree expectedParent)
    {
	boolean ok = true;
	if (isEmpty())
	{
	    /*if (parent != null) {
		ok = false;
		Assert.debug("EMPTY parent not null.");
		}*/
	    if (left != this) {
		ok = false;
		Assert.debug("EMPTY left not self.");
	    }
	    if (right != this) {
		ok = false;
		Assert.debug("EMPTY right not self.");
	    }
	} else {
	    if (expectedParent != parent()) 
	    {	
		Object expectedParentValue;
		ok = false;
		if (expectedParent == null) expectedParentValue = "null";
		else expectedParentValue = expectedParent.value();
		Object parentValue;
		if (parent == null) parentValue = "null";
		else parentValue = parent.value();
		Assert.debug("Parent of "+value()+" was not "+expectedParentValue+", but "+parentValue);
	    }
	    if (value == null) {
		ok = false;
		Assert.debug("null value found in tree");
	    }
	    ok = ok & left().wellConnected(this) &
		right().wellConnected(this);
	}
	return ok;
    }

    /**
     *
     */
    public void print()
    {
	if (isEmpty()) return;
	left().print();
	System.out.println(value());
	right().print();
    }

    /**
     * Returns an in-order iterator over the subtree rooted at 
     * this node.
     * 
     * @return An in-order iterator over the subtree rooted at 
     * this node.
     */
    public Iterator iterator(){
	return new RedBlackIterator(this);
    }
    
    
    /**
     * Computes hash code associated with values of tree.
     *
     * @post computes hash code associated with values of tree
     */
    public int hashCode()
    {
	if (isEmpty()) return 0;
	int result = left().hashCode() + right().hashCode();
	if (value() != null) result += value().hashCode();
	return result;
    }

    /**
     * Returns a string representing the tree rooted at this node.
     * <font color="#FF0000">WARNING</font> this can be a very long string.
     * 
     * @return A string representing the tree rooted at this node.
     */
    public String treeString(){
	String s = "";
	for (int i=0; i < this.depth(); i++){
	    s += "\t|";
	}
	
	s += ("<" + value() + " : " + 
	      getHand() + " : " + getColor()+ ">\n");
	
	if (left  != EMPTY) s += left.treeString();
	if (right != EMPTY) s += right.treeString();

	return s;
    }

    /**
     * Support method for {@link #toString}. Returns R if this is node 
     * is a right child, L if this node is a left child and Root if this
     * node is the root.
     * 
     * @return R if this is node 
     * is a right child, L if this node is a left child and Root if this
     * node is the root.
     */
    private String getHand(){
	if (isRightChild()) return "R";
	if (isLeftChild()) return "L";
	return "Root";	
    }

    /**
     * Support method for {@link #toString}. Returns Red if this is node 
     * is a red, and Black if this node is black.
     * 
     * @return R if this is node 
     * is a right child, L if this node is a left child and Root if this
     * node is the root.
     */
    private String getColor(){
	if (isRed) return "Red";
	return "Black";
    }

    /**
     * Returns string representation of red-black tree.
     *
     * @pre returns string representation of red-black tree
     */
    public String toString()
    {
	if (isEmpty()) return "";
	if (isRed()) return "(" + left() + value() + right() +")";
	else         return "[" + left() + value() + right() +"]";
    }
}