All Packages  Class Hierarchy  This Package  Previous  Next  Index  

Class DataStructures.BinarySearchTree

java.lang.Object
    |
    +----DataStructures.BinarySearchTree

public class BinarySearchTree
extends Object
implements SearchTree
Implements an unbalanced binary search tree. Note that all "matching" is based on the compares method.


Variable Index

 o root
The tree root.

Constructor Index

 o BinarySearchTree()
Construct the tree.

Method Index

 o find(Comparable)
Find an item in the tree.
 o find(Comparable, BinaryNode)
Internal method to find an item in a subtree.
 o findMax()
Find the largest item in the tree.
 o findMax(BinaryNode)
Internal method to find the largest item in a subtree.
 o findMin()
Find the smallest item in the tree.
 o findMin(BinaryNode)
Internal method to find the smallest item in a subtree.
 o insert(Comparable)
Insert into the tree.
 o insert(Comparable, BinaryNode)
Internal method to insert into a subtree.
 o isEmpty()
Test if the tree is logically empty.
 o main(String[])
 o makeEmpty()
Make the tree logically empty.
 o printTree()
Print the tree contents in sorted order.
 o printTree(BinaryNode)
Internal method to print a subtree in sorted order.
 o remove(Comparable)
Remove from the tree.
 o remove(Comparable, BinaryNode)
Internal method to remove from a subtree.
 o removeMin()
Remove the smallest item from the tree.
 o removeMin(BinaryNode)
Internal method to remove the smallest item from a subtree.

Variables

 o root
protected BinaryNode root
The tree root.

Constructors

 o BinarySearchTree
public BinarySearchTree()
Construct the tree.

Methods

 o insert
public void insert(Comparable x) throws DuplicateItem
Insert into the tree.

Parameters:
x - the item to insert.
Throws: DuplicateItem
if an item that matches x is already in the tree.
 o remove
public void remove(Comparable x) throws ItemNotFound
Remove from the tree.

Parameters:
x - the item to remove.
Throws: ItemNotFound
if no item that matches x can be found in the tree.
 o removeMin
public void removeMin() throws ItemNotFound
Remove the smallest item from the tree.

Throws: ItemNotFound
if the tree is empty.
 o findMin
public Comparable findMin() throws ItemNotFound
Find the smallest item in the tree.

Returns:
smallest item.
Throws: ItemNotFound
if the tree is empty.
 o findMax
public Comparable findMax() throws ItemNotFound
Find the largest item in the tree.

Returns:
the largest item.
Throws: ItemNotFound
if tree is empty.
 o find
public Comparable find(Comparable x) throws ItemNotFound
Find an item in the tree.

Parameters:
x - the item to search for.
Returns:
the matching item.
Throws: ItemNotFound
if no item that matches x can be found in the tree.
 o makeEmpty
public void makeEmpty()
Make the tree logically empty.

 o isEmpty
public boolean isEmpty()
Test if the tree is logically empty.

Returns:
true if empty, false otherwise.
 o printTree
public void printTree()
Print the tree contents in sorted order.

 o insert
protected BinaryNode insert(Comparable x,
                            BinaryNode t) throws DuplicateItem
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: DuplicateItem
if item that matches x is already in the subtree rooted at t.
 o remove
protected BinaryNode remove(Comparable x,
                            BinaryNode t) throws ItemNotFound
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: ItemNotFound
no item that matches x is in the subtree rooted at t.
 o removeMin
protected BinaryNode removeMin(BinaryNode t) throws ItemNotFound
Internal method to remove the smallest item from a subtree.

Parameters:
t - the node that roots the tree.
Returns:
the new root.
Throws: ItemNotFound
the subtree is empty.
 o findMin
protected BinaryNode findMin(BinaryNode t) throws ItemNotFound
Internal method to find the smallest item in a subtree.

Parameters:
t - the node that roots the tree.
Returns:
node containing the smallest item.
Throws: ItemNotFound
the subtree is empty.
 o findMax
protected BinaryNode findMax(BinaryNode t) throws ItemNotFound
Internal method to find the largest item in a subtree.

Parameters:
t - the node that roots the tree.
Returns:
node containing the largest item.
Throws: ItemNotFound
the subtree is empty.
 o find
protected BinaryNode find(Comparable x,
                          BinaryNode t) throws ItemNotFound
Internal method to find an item in a subtree.

Parameters:
x - is item to search for.
t - the node that roots the tree.
Returns:
node containing the matched item.
Throws: ItemNotFound
the item is not in the subtree.
 o printTree
protected void printTree(BinaryNode t)
Internal method to print a subtree in sorted order.

Parameters:
t - the node that roots the tree.
 o main
public static void main(String[] args)

All Packages  Class Hierarchy  This Package  Previous  Next  Index