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