structure5
Class BinarySearchTree<E extends java.lang.Comparable<E>>

java.lang.Object
  extended by structure5.AbstractStructure<E>
      extended by structure5.BinarySearchTree<E>
All Implemented Interfaces:
java.lang.Iterable<E>, OrderedStructure<E>, Structure<E>
Direct Known Subclasses:
SplayTree

public class BinarySearchTree<E extends java.lang.Comparable<E>>
extends AbstractStructure<E>
implements OrderedStructure<E>

A binary search tree structure. This structure maintains data in an ordered tree. It does not keep the tree balanced, so performance may degrade if the tree height is not optimal.

Example usage:

To create a Binary search tree containing the months of the year and to print out this tree as it grows we could use the following.

 public static void main(String[] argv){
     BinarySearchTree test = new BinarySearchTree();
       
     //declare an array of months
     String[] months = new String[]{"March", "May", "November", "August", 
                                    "April", "January", "December", "July",
                                    "February", "June", "October", "September"};
      
     //add the months to the tree and print out the tree as it grows
     for(int i=0; i < months.length; i++){
        test.add(months[i]);
        System.out.println("Adding: " + months[i] + "\n" +test.treeString());
      }
  }
 

See Also:
SplayTree, BinaryTree

Field Summary
protected  int count
          The number of nodes in the tree
protected  BinaryTree<E> EMPTY
          The node used as all leaves, in this implementation.
protected  java.util.Comparator<E> ordering
          The ordering used on this search tree.
protected  BinaryTree<E> root
          A reference to the root of the tree
 
Constructor Summary
BinarySearchTree()
          Constructs a binary search tree with no data
BinarySearchTree(java.util.Comparator<E> alternateOrder)
          Constructs a binary search tree with no data
 
Method Summary
 void add(E value)
          Add a (possibly duplicate) value to binary search tree
 void clear()
          Removes all data from the binary search tree
 boolean contains(E value)
          Determines if the binary search tree contains a value
 E get(E value)
          Returns reference to value found within three.
 int hashCode()
          Returns the hashCode of the value stored by this object.
 boolean isEmpty()
          Checks for an empty binary search tree
 java.util.Iterator<E> iterator()
          Returns an iterator over the binary search tree.
protected  BinaryTree<E> locate(BinaryTree<E> root, E value)
           
protected  BinaryTree<E> predecessor(BinaryTree<E> root)
           
 E remove(E value)
          Remove an value "equals to" the indicated value.
protected  BinaryTree<E> removeTop(BinaryTree<E> topNode)
          Removes the top node of the tree rooted, performs the necissary rotations to reconnect the tree.
 int size()
          Determines the number of data values within the tree
protected  BinaryTree<E> successor(BinaryTree<E> root)
           
 java.lang.String toString()
          Returns a string representing tree
 java.lang.String treeString()
          Returns a (possibly long) string representing tree.
 
Methods inherited from class structure5.AbstractStructure
elements, values
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface structure5.Structure
elements, values
 

Field Detail

root

protected BinaryTree<E extends java.lang.Comparable<E>> root
A reference to the root of the tree


EMPTY

protected final BinaryTree<E extends java.lang.Comparable<E>> EMPTY
The node used as all leaves, in this implementation.


count

protected int count
The number of nodes in the tree


ordering

protected java.util.Comparator<E extends java.lang.Comparable<E>> ordering
The ordering used on this search tree.

Constructor Detail

BinarySearchTree

public BinarySearchTree()
Constructs a binary search tree with no data

Postcondition:
Constructs an empty binary search tree

BinarySearchTree

public BinarySearchTree(java.util.Comparator<E> alternateOrder)
Constructs a binary search tree with no data

Postcondition:
Constructs an empty binary search tree
Method Detail

isEmpty

public boolean isEmpty()
Checks for an empty binary search tree

Specified by:
isEmpty in interface Structure<E extends java.lang.Comparable<E>>
Overrides:
isEmpty in class AbstractStructure<E extends java.lang.Comparable<E>>
Returns:
True iff the tree contains no data
Postcondition:
Returns true iff the binary search tree is empty

clear

public void clear()
Removes all data from the binary search tree

Specified by:
clear in interface Structure<E extends java.lang.Comparable<E>>
Postcondition:
Removes all elements from binary search tree

size

public int size()
Determines the number of data values within the tree

Specified by:
size in interface Structure<E extends java.lang.Comparable<E>>
Returns:
The number of nodes in the binary search tree
Postcondition:
Returns the number of elements in binary search tree

locate

protected BinaryTree<E> locate(BinaryTree<E> root,
                               E value)
Precondition:
root and value are non-null
Postcondition:
returned: 1 - existing tree node with the desired value, or 2 - the node to which value should be added

predecessor

protected BinaryTree<E> predecessor(BinaryTree<E> root)

successor

protected BinaryTree<E> successor(BinaryTree<E> root)

add

public void add(E value)
Add a (possibly duplicate) value to binary search tree

Specified by:
add in interface Structure<E extends java.lang.Comparable<E>>
Parameters:
val - A reference to non-null object
Postcondition:
Adds a value to binary search tree

contains

public boolean contains(E value)
Determines if the binary search tree contains a value

Specified by:
contains in interface Structure<E extends java.lang.Comparable<E>>
Overrides:
contains in class AbstractStructure<E extends java.lang.Comparable<E>>
Parameters:
val - The value sought. Should be non-null
Returns:
True iff the tree contains a value "equals to" sought value
Postcondition:
Returns true iff val is a value found within the tree

get

public E get(E value)
Returns reference to value found within three. This method can be potentially dangerous if returned value is modified: if modification would change the relation of value to others within the tree, the consistency of the structure is lost Don't modify returned value

Parameters:
val - Value sought from within tree
Returns:
A value "equals to" value sought; otherwise null
Postcondition:
Returns object found in tree, or null

remove

public E remove(E value)
Remove an value "equals to" the indicated value. Only one value is removed, and no guarantee is made concerning which of duplicate values are removed. Value returned is no longer part of the structure

Specified by:
remove in interface Structure<E extends java.lang.Comparable<E>>
Parameters:
val - Value sought to be removed from tree
Returns:
Actual value removed from tree
Postcondition:
Removes one instance of val, if found

removeTop

protected BinaryTree<E> removeTop(BinaryTree<E> topNode)
Removes the top node of the tree rooted, performs the necissary rotations to reconnect the tree.

Parameters:
topNode - Contains the value we want to remove
Returns:
The root of a new binary tree containing all of topNodes descendents and rooted at topNode's predecessor
Precondition:
topNode contains the value we want to remove
Postcondition:
We return an binary tree rooted with the predecessor of topnode.

iterator

public java.util.Iterator<E> iterator()
Returns an iterator over the binary search tree. Iterator should not be used if tree is modified, as behavior may be unpredicatable Traverses elements using in-order traversal order

Specified by:
iterator in interface java.lang.Iterable<E extends java.lang.Comparable<E>>
Specified by:
iterator in interface Structure<E extends java.lang.Comparable<E>>
Returns:
An iterator over binary search tree
See Also:
AbstractIterator, Iterator, Enumeration, Structure.elements()
Postcondition:
Returns iterator to traverse BST

hashCode

public int hashCode()
Returns the hashCode of the value stored by this object.

Overrides:
hashCode in class AbstractStructure<E extends java.lang.Comparable<E>>
Returns:
The hashCode of the value stored by this object.

treeString

public java.lang.String treeString()
Returns a (possibly long) string representing tree. Differs from toString() in that toString() outputs a single line representation of the contents of the tree. treeString, however, prints out a graphical representations of the tree's structure.

Returns:
String representation of tree
Postcondition:
Generates a string representation of the AVLST

toString

public java.lang.String toString()
Returns a string representing tree

Overrides:
toString in class java.lang.Object
Returns:
String representation of tree
Postcondition:
Generates a string representation of the BST