structure
Class RedBlackTree

java.lang.Object
  |
  +--structure.RedBlackTree

public class RedBlackTree

extends 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.
protected boolean	isRed The color of this node - red or black (not red)
protected RedBlackTree	left The left child of this node, or EMPTY
protected RedBlackTree	parent The parent of this node, or null
protected RedBlackTree	right The right child of this node, or EMPTY
protected Comparable	value The value stored in this node

Constructor Summary

protected	RedBlackTree() A one-time constructor, for constructing empty trees.
	RedBlackTree(Comparable v) Constructs a red-black tree with no children, value of the node is provided by the user

Method Summary

RedBlackTree	add(Comparable 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(Comparable c) Determines if the red black search tree contains a value
int	depth() Compute the depth of a node.
Comparable	get(Comparable c) Returns a c-equivalent value from tree, or null.
private String	getColor() Support method for toString().
private String	getHand() Support method for toString().
int	hashCode() Computes hash code associated with values of tree.
protected RedBlackTree	insert(Comparable 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.
Iterator	iterator() Returns an in-order iterator over the subtree rooted at this node.
protected RedBlackTree	left() Get left subtree of current node
protected RedBlackTree	locate(Comparable c) Locates a value in the search tree or returns the largest value less than value.
protected RedBlackTree	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	remove(Comparable c) Remove an value "equals to" the indicated value.
protected RedBlackTree	right() Get right subtree of current node
protected RedBlackTree	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 newLeft) Update the left subtree of this node.
protected void	setParent(RedBlackTree 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 newRight) Update the right subtree of this node.
String	toString() Returns string representation of red-black tree.
String	treeString() Returns a string representing the tree rooted at this node.
protected Object	value() Returns value associated with this node
boolean	wellConnected(RedBlackTree expectedParent) Returns true iff this tree is well-connected.

Methods inherited from class java.lang.Object

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

Field Detail

left

protected RedBlackTree left

The left child of this node, or EMPTY

right

protected RedBlackTree right

The right child of this node, or EMPTY

parent

protected RedBlackTree parent

The parent of this node, or null

value

protected Comparable 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

protected RedBlackTree()

A one-time constructor, for constructing empty trees.

RedBlackTree

public RedBlackTree(Comparable 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

Method Detail

isRed

protected boolean isRed()

Determines if this tree is red.

Postcondition:

returns whether or not this node is red

Returns:

Whether or not this node is red

isBlack

protected boolean isBlack()

Determines if this tree is black.

Postcondition:

returns whether or not this node is black

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 Object value()

Returns value associated with this node

Postcondition:

Returns value associated with this node

Returns:

The node's value

left

protected RedBlackTree left()

Get left subtree of current node

Postcondition:

Returns reference to left subtree, or null

Returns:

The left subtree of this node

right

protected RedBlackTree right()

Get right subtree of current node

Postcondition:

Returns reference to right subtree, or null

Returns:

The right subtree of this node

parent

protected RedBlackTree parent()

Get reference to parent of this node

Postcondition:

Returns reference to parent node, or null

Returns:

Reference to parent of this node

setParent

protected void setParent(RedBlackTree 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 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 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

Postcondition:

Returns true if this is a left child of parent

Returns:

True iff this node is a left child of parent

isRightChild

public boolean isRightChild()

Determine if this node is a right child

Postcondition:

Returns true if this is a right child of parent

Returns:

True iff this node is a right child of parent

isEmpty

public boolean isEmpty()

Returns true if tree is empty.

Postcondition:

Returns true iff the tree rooted at node is empty

Returns:

True iff tree is empty

isRoot

protected boolean isRoot()

Determine if this node is a root.

Postcondition:

Returns true if this is a root node

Returns:

true iff this is a root node

root

protected RedBlackTree root()

Returns reference to root of tree containing n

Precondition:

this node not EMPTY

Postcondition:

Returns the root of the tree node n

Returns:

Root of tree

depth

public int depth()

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

Postcondition:

Returns the depth of a node in the tree

Returns:

The path length to root of 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 add(Comparable c)

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

Parameters:

c - The value to be added to the tree.

Precondition:

c is a non-null Comparable value

Postcondition:

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

Returns:

The new value of the root.

insert

protected RedBlackTree insert(Comparable 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 remove(Comparable 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

Precondition:

c is non-null

Postcondition:

the value is removed; resulting tree is returned

Returns:

Actual value removed from tree

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(Comparable c)

Determines if the red black search tree contains a value

Parameters:

val - The value sought. Should be non-null

Precondition:

c is non-null

Postcondition:

returns true iff c is contained within the tree

Returns:

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

locate

protected RedBlackTree locate(Comparable 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 Comparable get(Comparable 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

wellConnected

public boolean wellConnected(RedBlackTree expectedParent)

Returns true iff this tree is well-connected.

print

public void print()

iterator

public Iterator 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 Object

Postcondition:

computes hash code associated with values of tree

treeString

public 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.

getHand

private String getHand()

Support method for 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.

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.

getColor

private String getColor()

Support method for toString(). Returns Red if this is node is a red, and Black if this node is black.

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.

toString

public String toString()

Returns string representation of red-black tree.

Overrides:

toString in class Object

Precondition:

returns string representation of red-black tree