goldman.collection.ordered
Class BalancedBinarySearchTree<E>

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

public abstract class BalancedBinarySearchTree<E>
extends BinarySearchTree<E>
implements OrderedCollection<E>, Tracked<E>

A balanced binary search tree uses rotations to maintain balance when one path to a leaf becomes "to much longer" than another. An interesting property of rotations is that no comparisons are needed, and the relative order for equivalent elements is not changed by a rotation.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.ordered.BinarySearchTree
BinarySearchTree.BSTNode, 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
 
Fields inherited from class goldman.collection.ordered.BinarySearchTree
FRONTIER_L, 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
BalancedBinarySearchTree()
           
BalancedBinarySearchTree(Comparator<? super E> comp)
           
 
Method Summary
 
Methods inherited from class goldman.collection.ordered.BinarySearchTree
addTracked, clear, clearNodes, createFrontierNode, createTreeNode, find, findLastInsertPosition, getLocator, insert, iterator, iteratorAtEnd, predecessor, remove, successor
 
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, iteratorAtEnd, max, min, predecessor, successor
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from interface goldman.collection.Tracked
addTracked
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

BalancedBinarySearchTree

public BalancedBinarySearchTree()

BalancedBinarySearchTree

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