Class BinarySearchTree

java.lang.Object
  BinarySearchTree

All Implemented Interfaces:

java.lang.Cloneable, DictionaryADT

public class BinarySearchTree

extends java.lang.Object

implements DictionaryADT, java.lang.Cloneable

The BinarySearchTree class maps keys to values (duplicated keys are not allowed). This class implements the DictionaryADT interface and the cloneable interface. The clone method does *not* clone the key and value objects stored in the tree. These objects are considered immutable. If their value is changed after they have been inserted into the tree, the results are undefined.

Nested Class Summary

protected class	BinarySearchTree.BSTEntry An extension of Map.Entry in the java.util package used for exporting a list view, or an iterator of the contents of this tree.
protected static class	BinarySearchTree.BSTNode Contains the data for each node in the BinarySearchTree as well as a set of functions that performs some important calculations on nodes to analyze and manipulate the tree structure.

Field Summary

protected java.util.Comparator	comparator The comparator used to order these key/value pairs.
protected int	numElements The number of elements in the BST
protected BinarySearchTree.BSTNode	root The root of the BST.

Constructor Summary

BinarySearchTree(java.util.Comparator c)
Constructs a new empty binary search tree ordered by the the given comparator

Method Summary

boolean	changeValue(java.lang.Object oldKey, java.lang.Object newValue) Associates a new value with an existing key in the tree.
java.lang.Object	clone() Makes a copy of this tree.
protected BinarySearchTree.BSTNode	cloneTree(BinarySearchTree.BSTNode otherRoot) Recursively copy the tree rooted at otherRoot, returning a reference to the newly copied subtree.
java.lang.Object	find(java.lang.Object key) Finds the value associated with the given key in this BST.
protected BinarySearchTree.BSTNode	findNode(java.lang.Object key) Tries to finds the node associated with a given key.
java.util.Comparator	getComparator() Returns the comparator used to order this Dictionary.
java.util.List	getEntryList() Gets a List view of the data in the BST.
int	getSize() Retrieves the number of elements in the tree
boolean	insert(java.lang.Object newKey, java.lang.Object newValue) Inserts a new key/value pair into the BST.
void	print(java.io.PrintWriter writer) Pretty-print the tree for debugging purposes.
protected int	recursiveGetEntryList(java.util.ArrayList entries, BinarySearchTree.BSTNode cur) Recursively copies the key/value pairs in the tree into the list entries.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected BinarySearchTree.BSTNode root

The root of the BST.

numElements

protected int numElements

The number of elements in the BST

comparator

protected final java.util.Comparator comparator

The comparator used to order these key/value pairs. This variable is final because it would not make to change the comparator after creation (imagine the havoc that would be wrought the BST!).

Constructor Detail

BinarySearchTree

public BinarySearchTree(java.util.Comparator c)

Constructs a new empty binary search tree ordered by the the given comparator

Parameters:

c - The comparator used to order the tree

Method Detail

clone

public java.lang.Object clone()

Makes a copy of this tree. This clone mehtod does not clone the keys and values stored in the tree.

Returns:

a copy of the current tree.

getComparator

public java.util.Comparator getComparator()

Returns the comparator used to order this Dictionary.

Specified by:

getComparator in interface DictionaryADT

Returns:

The comparator used to order this Dictionary

getSize

public int getSize()

Retrieves the number of elements in the tree

Specified by:

getSize in interface DictionaryADT

Returns:

the the number of elements in the tree.

find

public java.lang.Object find(java.lang.Object key)

Finds the value associated with the given key in this BST.

Specified by:

find in interface DictionaryADT

Parameters:

key - The key to search for.

Returns:

The value object associated with the key or null if key is not in the BST.

getEntryList

public java.util.List getEntryList()

Gets a List view of the data in the BST. The items in this list will be of type BSTEntry which is an implementaiton of the Map.Entry interface in the java.util package. The values in this list are immutable.

Specified by:

getEntryList in interface DictionaryADT

Returns:

A list view of the data in this BST.

print

public void print(java.io.PrintWriter writer)

Pretty-print the tree for debugging purposes.

Specified by:

print in interface DictionaryADT

Parameters:

writer - The print writer to output the tree onto.

insert

public boolean insert(java.lang.Object newKey,
                      java.lang.Object newValue)

Inserts a new key/value pair into the BST. If the key previously existed in the tree, this will overwrite the old value with the new value.

Specified by:

insert in interface DictionaryADT

Parameters:

newKey - key with which newValue will be associated.

newValue - the value to be associated with newKeyh

Returns:

true if this key did not previously exist in the tree, false otherwise.

changeValue

public boolean changeValue(java.lang.Object oldKey,
                           java.lang.Object newValue)

Associates a new value with an existing key in the tree. This function assumes that the key is already in the tree.

Specified by:

changeValue in interface DictionaryADT

Parameters:

oldKey - The key whose value will be changed.

newValue - The new value to associated with oldKey

Returns:

true if the data was changed. False otherwise.

findNode

protected BinarySearchTree.BSTNode findNode(java.lang.Object key)

Tries to finds the node associated with a given key.

Parameters:

key - the key value to search for.

Returns:

null if the tree is empty; otherwise it returns the node associated with the key, or the parent of where 'key' should if the key is in the tree.

recursiveGetEntryList

protected int recursiveGetEntryList(java.util.ArrayList entries,
                                    BinarySearchTree.BSTNode cur)

Recursively copies the key/value pairs in the tree into the list entries. The copying is done via an in-order traversal of the subtrees rooted at cur (thus, the data in the arrays will be ordered by key value because of the BST property). Does nothing if cur == null.

Parameters:

entries - The list to populate with the key/value pairs

cur - The current node in the recusive traversal.

Returns:

The number of valid items in the list.

cloneTree

protected BinarySearchTree.BSTNode cloneTree(BinarySearchTree.BSTNode otherRoot)

Recursively copy the tree rooted at otherRoot, returning a reference to the newly copied subtree.

Parameters:

otherRoot - The root of the tree to clone.

Returns:

a new copy of the tree rooted at otherRoot.