goldman.collection.ordered
Class BinarySearchTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.AbstractSearchTree<E>
          extended by goldman.collection.ordered.BinarySearchTree<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>
Direct Known Subclasses:
BalancedBinarySearchTree

public class BinarySearchTree<E>
extends AbstractSearchTree<E>
implements OrderedCollection<E>, Tracked<E>

This class implements a standard binary search tree. When elements are inserted into a binary search tree in a random order, then it has the desirable property of having logarithmic height, where the height is the maximum length of a path from the root to a leaf. The height is important since the cost of most methods is proportional to the height of the tree. In the best case, a binary search tree has height log2 (n+1). If the elements are inserted in a random order then the expected height is roughly 1.386 log2 n. However, the binary search tree can degenerate to a sorted list (which has a height of n). To avoid this situation, most implementations that build upon a binary search tree (red-black tree, B-Tree, B+-Tree) are balanced, meaning that they include methods that reorganize the tree so that the worst-case height is logarithmic.


Nested Class Summary
protected  class BinarySearchTree.BSTNode
           
protected  class BinarySearchTree.Tracker
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.AbstractSearchTree
AbstractSearchTree.TreeNode
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
protected  BinarySearchTree.BSTNode FRONTIER_L
           
protected  BinarySearchTree.BSTNode FRONTIER_R
           
 
Fields inherited from class goldman.collection.ordered.AbstractSearchTree
root
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version
 
Constructor Summary
BinarySearchTree()
           
BinarySearchTree(Comparator<? super E> comp)
           
 
Method Summary
 Locator<E> addTracked(E element)
          Inserts element into the collection.
 void clear()
          Removes all elements from the collection
 void clearNodes(BinarySearchTree.BSTNode x)
           
protected  BinarySearchTree.BSTNode createFrontierNode()
           
protected  BinarySearchTree.BSTNode createTreeNode(E data)
           
protected  BinarySearchTree.BSTNode find(E element)
           
protected  BinarySearchTree.BSTNode findLastInsertPosition(E element)
           
 Locator<E> getLocator(E x)
          Returns a locator that has been initialized to an element equivalent to target.
protected  BinarySearchTree.BSTNode insert(E element)
          Inserts it into the collection
 Locator<E> iterator()
          Creates a new tracker at FORE.
 Locator<E> iteratorAtEnd()
          Creates a new tracker that is at AFT.
 E predecessor(E target)
          The target need not be in the collection.
protected  void remove(AbstractSearchTree.TreeNode x)
          Removes the given node.
 E successor(E target)
          This method does not require that target be in the collection.
 
Methods inherited from class goldman.collection.ordered.AbstractSearchTree
add, contains, get, getEquivalentElement, getLastNodeSearchIndex, max, min, remove, traverseForVisitor, writeElements
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.ordered.OrderedCollection
get, getEquivalentElement, max, min
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 

Field Detail

FRONTIER_L

protected final BinarySearchTree.BSTNode FRONTIER_L

FRONTIER_R

protected final BinarySearchTree.BSTNode FRONTIER_R
Constructor Detail

BinarySearchTree

public BinarySearchTree()

BinarySearchTree

public BinarySearchTree(Comparator<? super E> comp)
Parameters:
comp - the comparator to use to order the elements
Method Detail

createFrontierNode

protected BinarySearchTree.BSTNode createFrontierNode()
Returns:
a reference to a newly created frontier node

createTreeNode

protected BinarySearchTree.BSTNode createTreeNode(E data)
Parameters:
data - the element to be held
Returns:
a reference to a new tree node holding data.

find

protected BinarySearchTree.BSTNode find(E element)
Specified by:
find in class AbstractSearchTree<E>
Parameters:
element - the target
Returns:
a reference to a node holding an equivalent element, if one exists. Otherwise it returns a reference to a frontier node at the insert position for element with its parent set to the node that preceded it on the search path.

findLastInsertPosition

protected BinarySearchTree.BSTNode findLastInsertPosition(E element)
Parameters:
element - the target
Returns:
a reference to the frontier node that is the last insert position for element. The parent field of the returned frontier node is set to the node that preceded it on the search path.

predecessor

public E predecessor(E target)
The target need not be in the collection.

Specified by:
predecessor in interface OrderedCollection<E>
Parameters:
target - the element to search for
Returns:
the maximum element in this collection that is less than target
Throws:
NoSuchElementException - no element in the collection is less than target

successor

public E successor(E target)
This method does not require that target be in the collection.

Specified by:
successor in interface OrderedCollection<E>
Parameters:
target - the element to search for
Returns:
the smallest element in this collection that is greater than target
Throws:
NoSuchElementException - no element in the collection is greater than target

insert

protected BinarySearchTree.BSTNode insert(E element)
Description copied from class: AbstractSearchTree
Inserts it into the collection

Specified by:
insert in class AbstractSearchTree<E>
Parameters:
element - the new element
Returns:
a reference to the newly added node

addTracked

public Locator<E> addTracked(E element)
Inserts element into the collection.

Specified by:
addTracked in interface Tracked<E>
Parameters:
element - the new element
Returns:
a tracker that tracks the new element

remove

protected void remove(AbstractSearchTree.TreeNode x)
Description copied from class: AbstractSearchTree
Removes the given node.

Specified by:
remove in class AbstractSearchTree<E>
Parameters:
x - a reference to the node to remove
Throws:
NoSuchElementException - node x is no longer in the collection (i.e., x is not in use)

clearNodes

public void clearNodes(BinarySearchTree.BSTNode x)

clear

public void clear()
Removes all elements from the collection

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

iterator

public Locator<E> iterator()
Creates a new tracker at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public Locator<E> iteratorAtEnd()
Creates a new tracker that is at AFT.

Specified by:
iteratorAtEnd in interface OrderedCollection<E>

getLocator

public Locator<E> getLocator(E x)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to target. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no equivalent element in the collection.

Specified by:
getLocator in interface Collection<E>
Parameters:
x - the target
Returns:
a tracker initialized to an element equivalent to x
Throws:
NoSuchElementException - there is no equivalent element in the collection