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

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

Direct Known Subclasses:

BinarySearchTreeWithRank

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

Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.

Field Summary

protected weiss.nonstandard.BinaryNode<AnyType>

root The tree root.

Constructor Summary

BinarySearchTree()
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 in the tree.
protected weiss.nonstandard.BinaryNode<AnyType>	findMin(weiss.nonstandard.BinaryNode<AnyType> t) Internal method to find the smallest item in a subtree.
void	insert(AnyType x) Insert into the tree.
protected weiss.nonstandard.BinaryNode<AnyType>	insert(AnyType x, weiss.nonstandard.BinaryNode<AnyType> t) Internal method to insert into a subtree.
boolean	isEmpty() Test if the tree is logically empty.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the tree logically empty.
void	remove(AnyType x) Remove from the tree..
protected weiss.nonstandard.BinaryNode<AnyType>	remove(AnyType x, weiss.nonstandard.BinaryNode<AnyType> t) Internal method to remove from a subtree.
void	removeMin() Remove minimum item from the tree.
protected weiss.nonstandard.BinaryNode<AnyType>	removeMin(weiss.nonstandard.BinaryNode<AnyType> t) Internal method to remove minimum item from a subtree.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected weiss.nonstandard.BinaryNode<AnyType extends java.lang.Comparable<? super AnyType>> root

The tree root.

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Construct the tree.

Method Detail

insert

public void insert(AnyType x)

Insert into the tree.

Parameters:

x - the item to insert.

Throws:

DuplicateItemException - if x is already present.

remove

public void remove(AnyType x)

Remove from the tree..

Parameters:

x - the item to remove.

Throws:

ItemNotFoundException - if x is not found.

removeMin

public void removeMin()

Remove minimum item from the tree.

Throws:

ItemNotFoundException - if tree is empty.

findMin

public AnyType findMin()

Find the smallest item in the tree.

Returns:

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.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

insert

protected weiss.nonstandard.BinaryNode<AnyType> insert(AnyType x,
                                                       weiss.nonstandard.BinaryNode<AnyType> t)

Internal method to insert into a subtree.

Parameters:

x - the item to insert.

t - the node that roots the tree.

Returns:

the new root.

Throws:

DuplicateItemException - if x is already present.

remove

protected weiss.nonstandard.BinaryNode<AnyType> remove(AnyType x,
                                                       weiss.nonstandard.BinaryNode<AnyType> t)

Internal method to remove from a subtree.

Parameters:

x - the item to remove.

t - the node that roots the tree.

Returns:

the new root.

Throws:

ItemNotFoundException - if x is not found.

removeMin

protected weiss.nonstandard.BinaryNode<AnyType> removeMin(weiss.nonstandard.BinaryNode<AnyType> t)

Internal method to remove minimum item from a subtree.

Parameters:

t - the node that roots the tree.

Returns:

the new root.

Throws:

ItemNotFoundException - if t is empty.

findMin

protected weiss.nonstandard.BinaryNode<AnyType> findMin(weiss.nonstandard.BinaryNode<AnyType> t)

Internal method to find the smallest item in a subtree.

Parameters:

t - the node that roots the tree.

Returns:

node containing the smallest item.

main

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