structure5
Class RedBlackTree<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.RedBlackTree<E>

public class RedBlackTree<E extends java.lang.Comparable<E>>
extends java.lang.Object

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.

See Also:

structure.AVLTree, structure.BinaryTree, structure.BinarySearchTree

Field Summary

static RedBlackTree	EMPTY the unique empty node; used as children on leaf trees and as empty search trees.
protected boolean	isRed The color of this node - red or black (not red)
protected RedBlackTree<E>	left The left child of this node, or EMPTY
protected RedBlackTree<E>	parent The parent of this node, or null
protected RedBlackTree<E>	right The right child of this node, or EMPTY
protected E	value The value stored in this node

Constructor Summary

RedBlackTree()
A one-time constructor, for constructing empty trees.

RedBlackTree(E v)
Constructs a red-black tree with no children, value of the node is provided by the user

Method Summary

RedBlackTree<E>	add(E c) Add a value to the red black tree, performing neccisary rotations and adjustments.
protected boolean	blackConsistency() Returns true if black properties of tree are correct
protected void	blackFixup() 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.
protected int	blackHeight() Returns the black height of this subtree.
boolean	consistency() Returns true if this node is consistently structured
protected boolean	consistentlyBlackHeight(int height) Checks to make sure that the black height of tree is height
boolean	contains(E c) Determines if the red black search tree contains a value
int	depth() Compute the depth of a node.
E	get(E c) Returns a c-equivalent value from tree, or null.
int	hashCode() Computes hash code associated with values of tree.
protected RedBlackTree<E>	insert(E c) Insert a (possibly duplicate) value to red-black search tree
protected boolean	isBlack() Determines if this tree is black.
boolean	isEmpty() Returns true if tree is empty.
boolean	isLeftChild() Determine if this node is a left child
protected boolean	isRed() Determines if this tree is red.
boolean	isRightChild() Determine if this node is a right child
protected boolean	isRoot() Determine if this node is a root.
java.util.Iterator<E>	iterator() Returns an in-order iterator over the subtree rooted at this node.
protected RedBlackTree<E>	left() Get left subtree of current node
protected RedBlackTree<E>	locate(E c) Locates a value in the search tree or returns the largest value less than value.
protected RedBlackTree<E>	parent() Get reference to parent of this node
void	print()
protected boolean	redConsistency() Returns true if no red node in subtree has red children
void	redFixup() Takes a red node and, restores the red nodes of the tree to maintain red-black properties if this node has a red parent.
RedBlackTree<E>	remove(E c) Remove an value "equals to" the indicated value.
protected RedBlackTree<E>	right() Get right subtree of current node
protected RedBlackTree<E>	root() Returns reference to root of tree containing n
protected void	rotateLeft() Method to perform a left rotation of tree about this node Node must have a right child.
protected void	rotateRight() Method to perform a right rotation of tree about this node Node must have a left child.
protected void	setBlack() Set this node to be black
protected void	setLeft(RedBlackTree<E> newLeft) Update the left subtree of this node.
protected void	setParent(RedBlackTree<E> newParent) Update the parent of this node
protected void	setRed() Set this node to be a red node
protected void	setRed(boolean isRed) Set this node to be a red or black node, depending on value of isRed.
protected void	setRight(RedBlackTree<E> newRight) Update the right subtree of this node.
java.lang.String	toString() Returns string representation of red-black tree.
java.lang.String	treeString() Returns a string representing the tree rooted at this node.
protected E	value() Returns value associated with this node

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

left

protected RedBlackTree<E extends java.lang.Comparable<E>> left

The left child of this node, or EMPTY

right

protected RedBlackTree<E extends java.lang.Comparable<E>> right

The right child of this node, or EMPTY

parent

protected RedBlackTree<E extends java.lang.Comparable<E>> parent

The parent of this node, or null

value

protected E extends java.lang.Comparable<E> value

The value stored in this node

isRed

protected boolean isRed

The color of this node - red or black (not red)

EMPTY

public static final RedBlackTree EMPTY

the unique empty node; used as children on leaf trees and as empty search trees.

Constructor Detail

RedBlackTree

public RedBlackTree()

A one-time constructor, for constructing empty trees.

Postcondition:

Private constructor that generates the EMPTY node

RedBlackTree

public RedBlackTree(E v)

Constructs a red-black tree with no children, value of the node is provided by the user

Parameters:

value - A (possibly null) value to be referenced by node

Precondition:

v is a non-null Comparable

Postcondition:

constructs a single node red-black tree

Method Detail

isRed

protected boolean isRed()

Determines if this tree is red.

Returns:

Whether or not this node is red

Postcondition:

returns whether or not this node is red

isBlack

protected boolean isBlack()

Determines if this tree is black.

Returns:

Whether or not this node is black

Postcondition:

returns whether or not this node is black

setRed

protected void setRed()

Set this node to be a red node

Postcondition:

sets this node red

setRed

protected void setRed(boolean isRed)

Set this node to be a red or black node, depending on value of isRed.

Postcondition:

sets this node red or black, depending on boolean isRed

setBlack

protected void setBlack()

Set this node to be black

Postcondition:

sets this node black

value

protected E value()

Returns value associated with this node

Returns:

The node's value

Postcondition:

Returns value associated with this node

left

protected RedBlackTree<E> left()

Get left subtree of current node

Returns:

The left subtree of this node

Postcondition:

Returns reference to left subtree, or null

right

protected RedBlackTree<E> right()

Get right subtree of current node

Returns:

The right subtree of this node

Postcondition:

Returns reference to right subtree, or null

parent

protected RedBlackTree<E> parent()

Get reference to parent of this node

Returns:

Reference to parent of this node

Postcondition:

Returns reference to parent node, or null

setParent

protected void setParent(RedBlackTree<E> newParent)

Update the parent of this node

Parameters:

newParent - A reference to the new parent of this node

Postcondition:

Re-parents this node to parent reference, or null

setLeft

protected void setLeft(RedBlackTree<E> newLeft)

Update the left subtree of this node. Parent of the left subtree is updated consistently. Existing subtree is detached

Precondition:

newLeft is a non-null RedBlackTree node, possibly EMPTY

Postcondition:

does nothing to the EMPTY node; else makes newLeft a left child of this, and this newLeft's parent

setRight

protected void setRight(RedBlackTree<E> newRight)

Update the right subtree of this node. Parent of the right subtree is updated consistently. Existing subtree is detached

Precondition:

newRight is a non-null RedBlackTree node, possibly EMPTY

Postcondition:

does nothing to the EMPTY node; else makes newRight a right child of this, and this newRight's parent

isLeftChild

public boolean isLeftChild()

Determine if this node is a left child

Returns:

True iff this node is a left child of parent

Postcondition:

Returns true if this is a left child of parent

isRightChild

public boolean isRightChild()

Determine if this node is a right child

Returns:

True iff this node is a right child of parent

Postcondition:

Returns true if this is a right child of parent

isEmpty

public boolean isEmpty()

Returns true if tree is empty.

Returns:

True iff tree is empty

Postcondition:

Returns true iff the tree rooted at node is empty

isRoot

protected boolean isRoot()

Determine if this node is a root.

Returns:

true iff this is a root node

Postcondition:

Returns true if this is a root node

root

protected RedBlackTree<E> root()

Returns reference to root of tree containing n

Returns:

Root of tree

Precondition:

this node not EMPTY

Postcondition:

Returns the root of the tree node n

depth

public int depth()

Compute the depth of a node. The depth is the path length from node to root

Returns:

The path length to root of tree

Postcondition:

Returns the depth of a node in the tree

rotateRight

protected void rotateRight()

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

Precondition:

This node has a left subtree

Postcondition:

Rotates local portion of tree so left child is root

rotateLeft

protected void rotateLeft()

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

Precondition:

This node has a right subtree

Postcondition:

Rotates local portion of tree so right child is root

add

public RedBlackTree<E> add(E c)

Add a value to the red black tree, performing neccisary rotations and adjustments.

Parameters:

c - The value to be added to the tree.

Returns:

The new value of the root.

Precondition:

c is a non-null Comparable value

Postcondition:

adds a comparable value to the red-black tree; returns the modified tree

insert

protected RedBlackTree<E> insert(E c)

Insert a (possibly duplicate) value to red-black search tree

Parameters:

c - The value to be inserted into the tree.

Precondition:

c is a non-null Comparable value

Postcondition:

c is inserted into search tree rooted at this

redFixup

public void redFixup()

Takes a red node and, restores the red nodes of the tree to maintain red-black properties if this node has a red parent.

Precondition:

this node is a red node; if parent is red, violates property

Postcondition:

red nodes of the tree are adjusted to maintain properties

remove

public RedBlackTree<E> remove(E c)

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

Parameters:

val - Value sought to be removed from tree

Returns:

Actual value removed from tree

Precondition:

c is non-null

Postcondition:

the value is removed; resulting tree is returned

blackFixup

protected void blackFixup()

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.

Precondition:

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

Postcondition:

the tree is black-height balanced

contains

public boolean contains(E c)

Determines if the red black search tree contains a value

Parameters:

val - The value sought. Should be non-null

Returns:

True iff the tree contains a value "equals to" sought value

Precondition:

c is non-null

Postcondition:

returns true iff c is contained within the tree

locate

protected RedBlackTree<E> locate(E c)

Locates a value in the search tree or returns the largest value less than value.

Precondition:

c is non-null

Postcondition:

returns a node of this tree that contains c, or null

get

public E get(E c)

Returns a c-equivalent value from tree, or null.

Parameters:

c - The c-equivalent value we are looking for in the tree.

Precondition:

c is non-null

Postcondition:

returns a c-equivalent value from tree, or null

consistency

public boolean consistency()

Returns true if this node is consistently structured

Postcondition:

returns true if this node is consistently structured

blackHeight

protected int blackHeight()

Returns the black height of this subtree.

Precondition:

tree is black-height balanced

Postcondition:

returns the black height of this subtree

redConsistency

protected boolean redConsistency()

Returns true if no red node in subtree has red children

Postcondition:

returns true if no red node in subtree has red children

blackConsistency

protected boolean blackConsistency()

Returns true if black properties of tree are correct

Postcondition:

returns true if black properties of tree are correct

consistentlyBlackHeight

protected boolean consistentlyBlackHeight(int height)

Checks to make sure that the black height of tree is height

Postcondition:

checks to make sure that the black height of tree is height

print

public void print()

iterator

public java.util.Iterator<E> iterator()

Returns an in-order iterator over the subtree rooted at this node.

Returns:

An in-order iterator over the subtree rooted at this node.

hashCode

public int hashCode()

Computes hash code associated with values of tree.

Overrides:

hashCode in class java.lang.Object

Postcondition:

computes hash code associated with values of tree

treeString

public java.lang.String treeString()

Returns a string representing the tree rooted at this node. WARNING this can be a very long string.

Returns:

A string representing the tree rooted at this node.

toString

public java.lang.String toString()

Returns string representation of red-black tree.

Overrides:

toString in class java.lang.Object

Precondition:

returns string representation of red-black tree