structure
Class RedBlackTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

java.lang.Object
  structure.RedBlackTree<ELTTYPE>

public class RedBlackTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>
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, BinaryTree, BinarySearchTree

Field Summary

static RedBlackTree

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

Constructor Summary

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

Method Summary

RedBlackTree<ELTTYPE>	add(ELTTYPE c) Add a value to the red black tree, performing neccisary rotations and adjustments.
boolean	consistency() Returns true if this node is consistently structured
boolean	contains(ELTTYPE c) Determines if the red black search tree contains a value
int	depth() Compute the depth of a node.
ELTTYPE	get(ELTTYPE c) Returns a c-equivalent value from tree, or null.
int	hashCode() Computes hash code associated with values of tree.
boolean	isEmpty() Returns true if tree is empty.
boolean	isLeftChild() Determine if this node is a left child
boolean	isRightChild() Determine if this node is a right child
java.util.Iterator<ELTTYPE>	iterator() Returns an in-order iterator over the subtree rooted at this node.
void	print()
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<ELTTYPE>	remove(ELTTYPE c) Remove an value "equals to" the indicated value.
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.

Methods inherited from class java.lang.Object

equals, getClass, notify, notifyAll, wait, wait, wait

Field Detail

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(ELTTYPE 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

Pre:

v is a non-null Comparable

Post:

constructs a single node red-black tree

Method Detail

isLeftChild

public boolean isLeftChild()

Determine if this node is a left child

Returns:

True iff this node is a left child of parent

Post:

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

Post:

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

Post:

Returns true iff the tree rooted at node is empty

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

Post:

Returns the depth of a node in the tree

add

public RedBlackTree<ELTTYPE> add(ELTTYPE 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.

Pre:

c is a non-null Comparable value

Post:

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

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.

Pre:

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

Post:

red nodes of the tree are adjusted to maintain properties

remove

public RedBlackTree<ELTTYPE> remove(ELTTYPE 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

Pre:

c is non-null

Post:

the value is removed; resulting tree is returned

contains

public boolean contains(ELTTYPE 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

Pre:

c is non-null

Post:

returns true iff c is contained within the tree

get

public ELTTYPE get(ELTTYPE c)

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

Parameters:

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

consistency

public boolean consistency()

Returns true if this node is consistently structured

Post:

returns true if this node is consistently structured

print

public void print()

iterator

public java.util.Iterator<ELTTYPE> 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

Post:

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

Pre:

returns string representation of red-black tree