goldman.collection.ordered
Class RedBlackTree<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>
                  extended by goldman.collection.ordered.RedBlackTree<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>

public class RedBlackTree<E>
extends BalancedBinarySearchTree<E>
implements OrderedCollection<E>, Tracked<E>

The red-black tree is a balanced binary search tree in which a single bit (a color of red or black) associated with each tree node is used to ensure that the number of comparisons made when searching for any element is at most 2 log2 n. Through partial analysis and simulations, it has been shown that a search in a red-black tree constructed from n elements, inserted in a random order, uses about 1.002 log2 n comparisons, on average. The red-black tree is the best general-purpose ordered collection data structure since it has guaranteed worst-case logarithmic bounds on the tree height and has very fast search time. If it is important to have constant time methods to reach the previous or next elements in the collection, additional structure can be added for this purpose at the expense of increased execution time and space usage.


Nested Class Summary
 class RedBlackTree.RBNode
           
 
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
RedBlackTree()
           
RedBlackTree(Comparator<? super E> comp)
           
 
Method Summary
 void checkRep()
          This method is used for testing the invariants.
protected  BinarySearchTree.BSTNode createFrontierNode()
           
protected  BinarySearchTree.BSTNode createTreeNode(E data)
           
protected  BinarySearchTree.BSTNode insert(E element)
          Inserts it into the collection
 
Methods inherited from class goldman.collection.ordered.BinarySearchTree
addTracked, clear, clearNodes, find, findLastInsertPosition, getLocator, 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, 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, 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, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

RedBlackTree

public RedBlackTree()

RedBlackTree

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

createFrontierNode

protected BinarySearchTree.BSTNode createFrontierNode()
Overrides:
createFrontierNode in class BinarySearchTree<E>
Returns:
a reference to a new black frontier node

createTreeNode

protected BinarySearchTree.BSTNode createTreeNode(E data)
Overrides:
createTreeNode in class BinarySearchTree<E>
Parameters:
data - the element to hold in the tree node
Returns:
a reference to a new red tree node

insert

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

Overrides:
insert in class BinarySearchTree<E>
Parameters:
element - the new element
Returns:
a reference to the newly added node

checkRep

public void checkRep()
This method is used for testing the invariants.

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