goldman.collection.ordered
Class RedBlackTree<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.ordered.AbstractSearchTree<E>
goldman.collection.ordered.BinarySearchTree<E>
goldman.collection.ordered.BalancedBinarySearchTree<E>
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.
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.AbstractCollection |
accept, addAll, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
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.Collection |
accept, add, addAll, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
RedBlackTree
public RedBlackTree()
RedBlackTree
public RedBlackTree(Comparator<? super E> comp)
- Parameters:
comp
- the comparator to use to
order the elements
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>