// 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
* isRed
.
* @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
// 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 value
.
*
* @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.
* WARNING 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() +"]";
}
}