    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