|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.ordered.AbstractSearchTree<E>
goldman.collection.ordered.BinarySearchTree<E>
public class BinarySearchTree<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 |
---|
protected final BinarySearchTree.BSTNode FRONTIER_L
protected final BinarySearchTree.BSTNode FRONTIER_R
Constructor Detail |
---|
public BinarySearchTree()
public BinarySearchTree(Comparator<? super E> comp)
comp
- the comparator to use to
order the elementsMethod Detail |
---|
protected BinarySearchTree.BSTNode createFrontierNode()
protected BinarySearchTree.BSTNode createTreeNode(E data)
data
- the element to
be held
data
.protected BinarySearchTree.BSTNode find(E element)
find
in class AbstractSearchTree<E>
element
- the target
element
with its parent set to the node
that preceded it on the search path.protected BinarySearchTree.BSTNode findLastInsertPosition(E element)
element
- the
target
element
. The
parent
field of the returned frontier node is
set to the node that preceded it on the search path.public E predecessor(E target)
predecessor
in interface OrderedCollection<E>
target
- the element to search for
target
NoSuchElementException
- no element in the collection
is less than target
public E successor(E target)
target
be in the collection.
successor
in interface OrderedCollection<E>
target
- the element to search for
target
NoSuchElementException
- no element in the collection
is greater than target
protected BinarySearchTree.BSTNode insert(E element)
AbstractSearchTree
insert
in class AbstractSearchTree<E>
element
- the new element
public Locator<E> addTracked(E element)
element
into the collection.
addTracked
in interface Tracked<E>
element
- the new element
protected void remove(AbstractSearchTree.TreeNode x)
AbstractSearchTree
remove
in class AbstractSearchTree<E>
x
- a reference to the node to remove
NoSuchElementException
- node x
is no longer in the collection (i.e.,
x is not in use)public void clearNodes(BinarySearchTree.BSTNode x)
public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> iteratorAtEnd()
iteratorAtEnd
in interface OrderedCollection<E>
public Locator<E> getLocator(E x)
Collection
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.
getLocator
in interface Collection<E>
x
- the target
NoSuchElementException
- there is no equivalent element in the collection
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |