weiss.nonstandard
Class RedBlackTree<AnyType extends java.lang.Comparable<? super AnyType>>

java.lang.Object
  weiss.nonstandard.RedBlackTree<AnyType>

public class RedBlackTree<AnyType extends java.lang.Comparable<? super AnyType>>
extends java.lang.Object

Implements a red-black tree. Note that all "matching" is based on the compareTo method.

Constructor Summary

RedBlackTree()
Construct the tree.

Method Summary

AnyType	find(AnyType x) Find an item in the tree.
AnyType	findMax() Find the largest item in the tree.
AnyType	findMin() Find the smallest item the tree.
void	insert(AnyType item) Insert into the tree.
boolean	isEmpty() Test if the tree is logically empty.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the tree logically empty.
void	printTree() Print all items.
void	remove(AnyType x) Remove from the tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

RedBlackTree

public RedBlackTree()

Construct the tree.

Method Detail

insert

public void insert(AnyType item)

Insert into the tree.

Parameters:

item - the item to insert.

Throws:

DuplicateItemException - if item is already present.

remove

public void remove(AnyType x)

Remove from the tree.

Parameters:

x - the item to remove.

Throws:

java.lang.UnsupportedOperationException - if called.

findMin

public AnyType findMin()

Find the smallest item the tree.

Returns:

the smallest item or null if empty.

findMax

public AnyType findMax()

Find the largest item in the tree.

Returns:

the largest item or null if empty.

find

public AnyType find(AnyType x)

Find an item in the tree.

Parameters:

x - the item to search for.

Returns:

the matching item or null if not found.

makeEmpty

public void makeEmpty()

Make the tree logically empty.

printTree

public void printTree()

Print all items.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

main

public static void main(java.lang.String[] args)