com.mhhe.clrs2e
Class RedBlackTree

java.lang.Object
  |
  +--com.mhhe.clrs2e.BinarySearchTree
        |
        +--com.mhhe.clrs2e.RedBlackTree

All Implemented Interfaces:

Dictionary

Direct Known Subclasses:

IntervalTree, OrderStatisticTree

public class RedBlackTree

extends BinarySearchTree

Implements the Dictionary interface as a red-black tree from Chapter 13 of Introduction to Algorithms, Second edition. Objects inserted into a red-black tree must implement the Comparable interface.

Nested Class Summary

static class	RedBlackTree.BlackHeightException Exception thrown by blackHeight(com.mhhe.clrs2e.RedBlackTree.Node) if the black-height of a node is ill-defined.
protected class	RedBlackTree.Node Inner class for a red-black tree node.

Nested classes inherited from class com.mhhe.clrs2e.BinarySearchTree

BinarySearchTree.Visitor

Field Summary

protected static java.awt.Color	BLACK Color for a black node.
protected static java.awt.Color	RED Color for a red node.

Fields inherited from class com.mhhe.clrs2e.BinarySearchTree

nil, root

Constructor Summary

RedBlackTree()
Creates a red-black tree with just a nil, which is the root.

Method Summary

int	blackHeight() Returns the number of black nodes from the root down to any leaf.
int	blackHeight(RedBlackTree.Node z) Returns the number of black nodes from a given node down to any leaf.
void	delete(java.lang.Object handle) Removes a node from the tree.
protected void	deleteFixup(RedBlackTree.Node x) Restores the red-black properties of the tree after a deletion.
java.lang.Object	insert(java.lang.Comparable data) Inserts data into the tree, creating a new node for this data.
protected void	insertFixup(RedBlackTree.Node z) Restores the red-black conditions of the tree after inserting a node.
protected void	leftRotate(RedBlackTree.Node x) Performs a left rotation on a node, making the node's right child its parent.
protected void	rightRotate(RedBlackTree.Node x) Performs a right rotation on a node, making the node's left child its parent.
protected void	setNil(RedBlackTree.Node node) Set the sentinel nil to a given node, and make the sentinel black.
protected void	treeInsert(RedBlackTree.Node z) Inserts a node into the tree.

Methods inherited from class com.mhhe.clrs2e.BinarySearchTree

dereference, inorderWalk, inorderWalk, isNil, iterativeSearch, maximum, minimum, postorderWalk, postorderWalk, predecessor, preorderWalk, preorderWalk, search, search, setNil, successor, toString, treeInsert, treeMaximum, treeMinimum

Methods inherited from class java.lang.Object

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

Field Detail

RED

protected static final java.awt.Color RED

Color for a red node.

BLACK

protected static final java.awt.Color BLACK

Color for a black node.

Constructor Detail

RedBlackTree

public RedBlackTree()

Creates a red-black tree with just a nil, which is the root.

Method Detail

setNil

protected void setNil(RedBlackTree.Node node)

Set the sentinel nil to a given node, and make the sentinel black.

Parameters:

node - The node that nil is set to.

leftRotate

protected void leftRotate(RedBlackTree.Node x)

Performs a left rotation on a node, making the node's right child its parent.

Parameters:

x - The node.

rightRotate

protected void rightRotate(RedBlackTree.Node x)

Performs a right rotation on a node, making the node's left child its parent.

Parameters:

x - The node.

insert

public java.lang.Object insert(java.lang.Comparable data)

Inserts data into the tree, creating a new node for this data.

Specified by:

insert in interface Dictionary

Overrides:

insert in class BinarySearchTree

Parameters:

data - Data to be inserted into the tree.

Returns:

A reference to the Node object created. The Node class is opaque to methods outside this class.

treeInsert

protected void treeInsert(RedBlackTree.Node z)

Inserts a node into the tree.

Parameters:

z - The node to insert.

insertFixup

protected void insertFixup(RedBlackTree.Node z)

Restores the red-black conditions of the tree after inserting a node.

Parameters:

z - The node inserted.

delete

public void delete(java.lang.Object handle)

Removes a node from the tree.

Specified by:

delete in interface Dictionary

Overrides:

delete in class BinarySearchTree

Parameters:

handle - The node to be removed.

Throws:

DeleteSentinelException - if there is an attempt to delete the sentinel nil.

java.lang.ClassCastException - if node does not reference a Node object.

deleteFixup

protected void deleteFixup(RedBlackTree.Node x)

Restores the red-black properties of the tree after a deletion.

Parameters:

x - Node at which there may be a violation.

blackHeight

public int blackHeight(RedBlackTree.Node z)

Returns the number of black nodes from a given node down to any leaf. The value should be the same for all paths.

Parameters:

z - The node.

Throws:

RedBlackTree.BlackHeightException - if the number of black nodes on a path from the left child down to a leaf differs from the number of black nodes on a path from the right child down to a leaf.

blackHeight

public int blackHeight()

Returns the number of black nodes from the root down to any leaf. The value should be the same for all paths.

Throws:

RedBlackTree.BlackHeightException - if the number of black nodes on a path from the left child down to a leaf differs from the number of black nodes on a path from the right child down to a leaf.