|
||||||||||
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.BTree<E>
public class BTree<E>
A B-tree is a balanced binary search tree in which each node can hold between t-1 and 2t-1 elements, where integer t > 1 is provided as a parameter to the constructor. Our implementation of the B-tree uses bottom-up insertion and deletion. The B-tree is designed for collections that are so large that secondary storage must be used. The larger node size (chosen with knowledge of the page size) helps minimize the number of disk pages that must be read to locate an element.
Nested Class Summary | |
---|---|
protected class |
BTree.Marker
|
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.AbstractSearchTree |
---|
root |
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
BTree()
|
|
BTree(Comparator<? super E> comp,
int t)
|
|
BTree(int t)
|
Method Summary | |
---|---|
void |
clear()
Removes all elements from the collection |
protected void |
createRoot()
Creates and initializes a new empty root node |
protected goldman.collection.ordered.BTree.BTreeNode |
find(E target)
This method sets the global variable curIndex to hold the
index for an occurrence of the target (if it is in the collection),
or otherwise the insert position
for the target in the last non-frontier node on the search path |
protected int |
getLastNodeSearchIndex()
REQUIRES: it is called only after a successful search |
Locator<E> |
getLocator(E x)
Returns a locator that has been initialized to an element equivalent to target . |
protected AbstractSearchTree.TreeNode |
insert(E element)
Inserts it into the collection |
Locator<E> |
iterator()
Creates a new tracker that is at FORE. |
Locator<E> |
iteratorAtEnd()
Creates a new tracker that is at AFT. |
E |
predecessor(E target)
This method does not require that target
be in the collection. |
protected void |
remove(AbstractSearchTree.TreeNode x)
Removes the element at curIndex
of x |
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, 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 |
Constructor Detail |
---|
public BTree()
public BTree(int t)
t
- the order
for the B-treepublic BTree(Comparator<? super E> comp, int t)
comp
- the function used
to compare two elementst
- the order of the B-treeMethod Detail |
---|
protected void createRoot()
protected goldman.collection.ordered.BTree.BTreeNode find(E target)
curIndex
to hold the
index for an occurrence of the target (if it is in the collection),
or otherwise the insert position
for the target in the last non-frontier node on the search path
find
in class AbstractSearchTree<E>
target
- the value to search for
parent
field set to predecessor of the target on the search path.protected int getLastNodeSearchIndex()
getLastNodeSearchIndex
in class AbstractSearchTree<E>
public E predecessor(E target)
target
be in the collection.
predecessor
in interface OrderedCollection<E>
target
- the element for which to find
the predecessor
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 for which to find
the successor
target
NoSuchElementException
- no element in the collection
is greater than target
protected AbstractSearchTree.TreeNode insert(E element)
AbstractSearchTree
insert
in class AbstractSearchTree<E>
element
- the new element
protected void remove(AbstractSearchTree.TreeNode x)
curIndex
of x
remove
in class AbstractSearchTree<E>
x
- a reference to
an existing tree nodepublic 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 element to track
NoSuchElementException
- there is no element equivalent to
x in the collection.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |