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.

root
 The tree root.

BinarySearchTree()
 Construct the tree.

find(Comparable)
 Find an item in the tree.

find(Comparable, BinaryNode)
 Internal method to find an item in a subtree.

findMax()
 Find the largest item in the tree.

findMax(BinaryNode)
 Internal method to find the largest item in a subtree.

findMin()
 Find the smallest item in the tree.

findMin(BinaryNode)
 Internal method to find the smallest item in a subtree.

insert(Comparable)
 Insert into the tree.

insert(Comparable, BinaryNode)
 Internal method to insert into a subtree.

isEmpty()
 Test if the tree is logically empty.

main(String[])


makeEmpty()
 Make the tree logically empty.

printTree()
 Print the tree contents in sorted order.

printTree(BinaryNode)
 Internal method to print a subtree in sorted order.

remove(Comparable)
 Remove from the tree.

remove(Comparable, BinaryNode)
 Internal method to remove from a subtree.

removeMin()
 Remove the smallest item from the tree.

removeMin(BinaryNode)
 Internal method to remove the smallest item from a subtree.
root
protected BinaryNode root
 The tree root.
BinarySearchTree
public BinarySearchTree()
 Construct the tree.
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.
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.
removeMin
public void removeMin() throws ItemNotFound
 Remove the smallest item from the tree.
 Throws:
ItemNotFound
 if the tree is empty.
findMin
public Comparable findMin() throws ItemNotFound
 Find the smallest item in the tree.
 Returns:
 smallest item.
 Throws:
ItemNotFound
 if the tree is empty.
findMax
public Comparable findMax() throws ItemNotFound
 Find the largest item in the tree.
 Returns:
 the largest item.
 Throws:
ItemNotFound
 if tree is empty.
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.
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.
printTree
public void printTree()
 Print the tree contents in sorted order.
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.
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.
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.
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.
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.
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.
printTree
protected void printTree(BinaryNode t)
 Internal method to print a subtree in sorted order.
 Parameters:
 t  the node that roots the tree.
main
public static void main(String[] args)
All Packages Class Hierarchy This Package Previous Next Index