redblacktree.java

关于迭代器、构造器

// An implementation of red-black trees.
// (c) 2000, 2001 duane a. bailey
package structure;
import java.util.Iterator;

/**
 * This class implements a single node of a red-black tree.  It is a
 * recursive structure.  Relationships between nodes are 
 * doubly linked, with parent and child references.  Many characteristics
 * of trees may be detected with static methods.
 *
 * @version $Id: BinaryTree.java,v 4.0 2000/12/27 20:57:33 bailey Exp bailey $
 * @author, 2002 duane a. bailey, evan s. sandhaus
 * @see structure.AVLTree
 * @see structure.BinaryTree
 * @see structure.BinarySearchTree
 */
public class RedBlackTree{
    /**
     * The left child of this node, or EMPTY
     */
    protected RedBlackTree left;

    /**
     * The right child of this node, or EMPTY
     */
    protected RedBlackTree right;

    /**
     * The parent of this node, or null
     */
    protected RedBlackTree parent;

    /**
     * The value stored in this node
     */
    protected Comparable value;

    /**
     * The color of this node - red or black (not red)
     */
    protected boolean isRed;

    /**
     * the unique empty node; used as children on leaf trees and
     * as empty search trees.
     */
    public static final RedBlackTree EMPTY = new RedBlackTree();

    /**
     * A one-time constructor, for constructing empty trees.
     * @post Private constructor that generates the EMPTY node
     * @return the EMPTY node; leaves have EMPTY as children
     */
    protected RedBlackTree()
    {
	value = null;
	parent = null;
	left = right = this;
	isRed = false;  // empty trees below the leaves should be black
    }

     /**
     * Constructs a red-black tree with no children, value of the node 
     * is provided by the user
     *
     * @param value A (possibly null) value to be referenced by node
     * @pre v is a non-null Comparable
     * @post constructs a single node red-black tree
     */
    public RedBlackTree(Comparable v)
    {
	value = v;
	parent = null;
	left = right = EMPTY;
	isRed = false;  // roots of tree should be colored black
    }

    /**
     * Determines if this tree is red.
     *
     * @return Whether or not this node is red
     * @post returns whether or not this node is red
     */
    protected boolean isRed()
    {
	return isRed;
    }

    /**
     * Determines if this tree is black.
     *
     * @return Whether or not this node is black
     * @post returns whether or not this node is black
     */
    protected boolean isBlack()
    {
	return !isRed;
    }

    /**
     * Set this node to be a red node
     *
     * @post sets this node red 
     */
    protected void setRed()
    {
	isRed = true;
    }

    /**
     * Set this node to be a red or black node, depending on value of 
     * <code>isRed</code>.
     * @post sets this node red or black, depending on boolean isRed
     */
    protected void setRed(boolean isRed)
    {
	this.isRed = isRed;
    }

    /**
     * Set this node to be black
     * @post sets this node black
     */
    protected void setBlack()
    {
	isRed = false;
    }

  
    /**
     * Returns value associated with this node
     *
     * @post Returns value associated with this node
     * @return The node's value
     */
    protected Object value()
    {
	return value;
    }

    /**
     * Get left subtree of current node
     *
     * @post Returns reference to left subtree, or null
     * @return The left subtree of this node
     */
    protected RedBlackTree left()
    {
	return left;
    }

    /**
     * Get right subtree of current node
     *
     * @post Returns reference to right subtree, or null
     * @return The right subtree of this node
     */
    protected RedBlackTree right()
    {
	return right;
    }


    /**
     * Get reference to parent of this node
     *
     * @post Returns reference to parent node, or null
     * @return Reference to parent of this node
     */
    protected RedBlackTree parent()
    {
	return parent;
    }

    /**
     * Update the parent of this node
     *
     * @post Re-parents this node to parent reference, or null
     * @param newParent A reference to the new parent of this node
     */
    protected void setParent(RedBlackTree newParent)
    {
	parent = newParent;
    }

    /**
     * Update the left subtree of this node.  Parent of the left subtree
     * is updated consistently.  Existing subtree is detached
     *
     * @pre newLeft is a non-null RedBlackTree node, possibly EMPTY
     * @post does nothing to the EMPTY node;
     *       else makes newLeft a left child of this, 
     *       and this newLeft's parent
    */
    protected void setLeft(RedBlackTree newLeft)
    {
	if (isEmpty()) return;
	if (left.parent() == this) left.setParent(null);
	left = newLeft;
	left.setParent(this);
    }

    /**
     * Update the right subtree of this node.  Parent of the right subtree
     * is updated consistently.  Existing subtree is detached
     *
     * @pre newRight is a non-null RedBlackTree node, possibly EMPTY
     * @post does nothing to the EMPTY node;
     *       else makes newRight a right child of this, 
     *       and this newRight's parent
    */
    protected void setRight(RedBlackTree newRight)
    {
	if (isEmpty()) return;
	if (right.parent() == this) right.setParent(null);
	right = newRight;
	right.setParent(this);
    }

    /**
     * Determine if this node is a left child
     *
     * @post Returns true if this is a left child of parent
     * @return True iff this node is a left child of parent
     */
    public boolean isLeftChild(){
	if (parent() == null) return false;
	return this == parent().left();
    }

    /**
     * Determine if this node is a right child
     *
     * @post Returns true if this is a right child of parent
     * @return True iff this node is a right child of parent
     */
    public boolean isRightChild(){
	if (parent() == null) return false;
	return this == parent().right();
    }

    /**
     * Returns true if tree is empty.
     *
     * @post Returns true iff the tree rooted at node is empty
     * @return True iff tree is empty
     */
    public boolean isEmpty()
    {
	return this == EMPTY;
    }

    
    /**
     * Determine if this node is a root.
     *
     * @post Returns true if this is a root node
     * @return true iff this is a root node
     */
    protected boolean isRoot()
    {
	return parent == null;
    }

    /**
     * Returns reference to root of tree containing n
     *
     * @pre this node not EMPTY
     * @post Returns the root of the tree node n
     * @return Root of tree
     */
    protected RedBlackTree root()
    {
	RedBlackTree result = this;
	while (!result.isRoot()) {
	    result = result.parent();
	}
	return result;
    }

    /**
     * Compute the depth of a node.  The depth is the path length
     * from node to root
     *
     * @post Returns the depth of a node in the tree
     * @return The path length to root of tree
     */
    public int depth(){
	if (parent() == null) return 0;
	return 1 + parent.depth();
    }

    /**
     * Method to perform a right rotation of tree about this node
     * Node must have a left child.  Relation between left child and node
     * are reversed
     *
     * @pre This node has a left subtree
     * @post Rotates local portion of tree so left child is root
     */
    protected void rotateRight()
    {
	// all of this information must be grabbed before
	// any of the references are set.  Draw a diagram for help
	RedBlackTree parent = parent();
	RedBlackTree newRoot = left();
	// is the this node a child; if so, a right child?
	boolean wasChild = !isRoot();
	boolean wasLeftChild = isLeftChild();

	// hook in new root (sets newRoot's parent, as well)
        setLeft(newRoot.right());

	// puts pivot below it (sets this's parent, as well)
        newRoot.setRight(this);
	/**
	 */

	if (wasChild) {
	    if (wasLeftChild) parent.setLeft(newRoot);
	    else              parent.setRight(newRoot);
	} else Assert.post(newRoot.isRoot(),"Rotate at root preserves root.");
    }

    /**
     * Method to perform a left rotation of tree about this node
     * Node must have a right child.  Relation between right child and node
     * are reversed
     *
     * @pre This node has a right subtree
     * @post Rotates local portion of tree so right child is root
     */
    protected void rotateLeft()
    {
	// all of this information must be grabbed before
	// any of the references are set.  Draw a diagram for help
	RedBlackTree parent = parent();  // could be null
	RedBlackTree newRoot = right();
	// is the this node a child; if so, a left child?
	boolean wasChild = !isRoot();
	boolean wasRightChild = isRightChild();

	// hook in new root (sets newRoot's parent, as well)
        setRight(newRoot.left());

	// put pivot below it (sets this's parent, as well)
        newRoot.setLeft(this);

	if (wasChild) {
	    if (wasRightChild) parent.setRight(newRoot);
	    else               parent.setLeft(newRoot);
	} else Assert.post(newRoot.isRoot(),"Left rotate at root preserves root.");
    }

    /**
     * Add a value to the red black tree, performing neccisary rotations
     * and adjustments. 
     *
     * @param c The value to be added to the tree.
     * @return The new value of the root.
     * @pre c is a non-null Comparable value
     * @post adds a comparable value to the red-black tree;
     *       returns the modified tree
     */
    public RedBlackTree add(Comparable c)
    {
        RedBlackTree tree = insert(c);  // first, do a plain insert
	tree.setRed();  // we insert nodes as red nodes - a first guess
	tree.redFixup();  // now, rebalance the tree
	return tree.root();  // return new root
    }

    /**
     * Insert a (possibly duplicate) value to red-black search tree
     *
     * @param c The value to be inserted into the tree.
     * @pre c is a non-null Comparable value
     * @post c is inserted into search tree rooted at this
     */
    protected RedBlackTree insert(Comparable c)
    {
	// trivial case - tree was empty:
	if (isEmpty()) return new RedBlackTree(c);

	// decide to insert value to left or right of root:
	if (c.compareTo(value()) < 0) {

	    // if to left and no left child, we insert value as leaf 
	    if (left().isEmpty()) {
		RedBlackTree result = new RedBlackTree(c);
		setLeft(result);
		return result;
	    } else {
		// recursively insert to left
		return left().insert(c);
	    }
	} else {

	    // if to right and no left child, we insert value as leaf
	    if (right().isEmpty()) {
		RedBlackTree result = new RedBlackTree(c);
		setRight(result);
		return result;
	    } else {
		// recursively insert to right
		return right().insert(c);
	    }
	}
    }

    /**
     * Takes a red node and, restores the red nodes of the tree  
     * to maintain red-black properties if this node has a red parent.
     *
     * @pre this node is a red node; if parent is red, violates property
     * @post red nodes of the tree are adjusted to maintain properties
     */
    public void redFixup()
    {
	if (isRoot() || !parent().isRed()) {
	    // ensure that root is black (might have been insertion pt)
	    root().setBlack();
	} else {
	    RedBlackTree parent = parent();  // we know parent exists
	    // since parent is red, it is not root; grandParent exists & black
	    RedBlackTree grandParent = parent.parent();
	    RedBlackTree aunt;  // sibling of parent (may exist)

	    if (parent.isLeftChild())
	    {
		aunt = grandParent.right();
		if (aunt.isRed()) {
		    // this:red, parent:red, grand:black, aunt:red
		    // push black down from gp to parent-aunt, but
		    // coloring gp red may introduce problems higher up
		    grandParent.setRed();
		    aunt.setBlack();
		    parent.setBlack();
		    grandParent.redFixup();
		} else {
		    if (isRightChild()) {
			// this:red, parent:red, grand:black, aunt:black
			// ensure that this is on outside for later rotate
			parent.rotateLeft();
			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.rotateRight();
			grandParent.setRed();
			parent.setBlack();
		    }
		}
	    } else // parent.isRightChild()
	    {
		aunt = grandParent.left();
		if (aunt.isRed()) {
		    // this:red, parent:red, grand:black, aunt:red
		    // push black down from gp to parent-aunt, but