goldman.collection.ordered
Class SplayTree<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.SplayTree<E>
- All Implemented Interfaces:
- Collection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>
public class SplayTree<E>
- extends BalancedBinarySearchTree<E>
- implements OrderedCollection<E>, Tracked<E>
A splay tree is a form of a balanced binary search tree in which
the nodes store no explicit information to enforce a balancing condition. Instead,
a sequence of rotations is used to restructure the search tree so that the
element accessed in the last method call is brought to the root of the tree. It can be shown that
if a random sequence of elements is accessed, then this restructuring leads to trees
with expected logarithmic height. Thus, recently accessed elements are near the
root and can be located very efficiently. The amortized complexity for
all splay tree methods is logarithmic. However, as with a binary search tree, a splay tree can
degenerate into a sorted list. The splay tree should be used if
the goal is to minimize the expected access time, provided that the access
pattern is stable and not uniform (i.e., some elements are accessed much more frequently than others),
and provided that elements recently accessed are more
likely to be accessed again soon.
Method Summary |
void |
add(E element)
Inserts element into the ordered collection and then uses
splay to bring the new element to the root of the tree. |
Locator<E> |
addTracked(E element)
Inserts element into the collection. |
boolean |
contains(E element)
If element is in the collection, it is brought
to the root using the splay method. |
Locator<E> |
getLocator(E x)
As with the other accessors, this method uses splay to bring x to the root. |
E |
max()
It uses splay to bring the maximum element to the root. |
E |
min()
It uses splay to bring the minimum element to the root. |
E |
predecessor(E element)
It uses splay to bring the predecessor to the root. |
protected void |
remove(AbstractSearchTree.TreeNode x)
Uses splay to both bring the successor of x (if
x has two children) to be a child of x , and then also uses splay to
bring x 's parent to the root. |
E |
successor(E element)
It uses splay to bring the successor to the root. |
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, addAll, checkRep, clear, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
accept, addAll, checkRep, clear, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
SplayTree
public SplayTree()
SplayTree
public SplayTree(Comparator<? super E> comp)
- Parameters:
comp
- the comparator to use to
order the elements
contains
public boolean contains(E element)
- If
element
is in the collection, it is brought
to the root using the splay method. Otherwise, the last element
accessed on the search path for element
is brought to the root
with the splay method
- Specified by:
contains
in interface Collection<E>
- Overrides:
contains
in class AbstractSearchTree<E>
- Parameters:
element
- the target
- Returns:
- true if and only if an equivalent value exists in the collection
min
public E min()
- It uses splay to bring the minimum element to the root.
- Specified by:
min
in interface OrderedCollection<E>
- Overrides:
min
in class AbstractSearchTree<E>
- Returns:
- the smallest element in the collection.
- Throws:
NoSuchElementException
- the collection is empty.
max
public E max()
- It uses splay to bring the maximum element to the root.
- Specified by:
max
in interface OrderedCollection<E>
- Overrides:
max
in class AbstractSearchTree<E>
- Returns:
- the largest element in the collection.
- Throws:
NoSuchElementException
- the collection is empty.
predecessor
public E predecessor(E element)
- It uses splay to bring the predecessor to the root.
- Specified by:
predecessor
in interface OrderedCollection<E>
- Overrides:
predecessor
in class BinarySearchTree<E>
- Parameters:
element
- the element for which to find
the predecessor
- Returns:
- the maximum value held in the collection that is less
than
element
- Throws:
NoSuchElementException
- no element in the collection
is less than element
successor
public E successor(E element)
- It uses splay to bring the successor to the root.
- Specified by:
successor
in interface OrderedCollection<E>
- Overrides:
successor
in class BinarySearchTree<E>
- Parameters:
element
- the element for which to find
the successor
- Returns:
- the minimum value held in the collection that is less
than
element
- Throws:
NoSuchElementException
- no element in the collection
is larger than element
add
public void add(E element)
- Inserts
element
into the ordered collection and then uses
splay
to bring the new element to the root of the tree.
- Specified by:
add
in interface Collection<E>
- Overrides:
add
in class AbstractSearchTree<E>
- Parameters:
element
- the new element
addTracked
public Locator<E> addTracked(E element)
- Inserts
element
into the collection.
- Specified by:
addTracked
in interface Tracked<E>
- Overrides:
addTracked
in class BinarySearchTree<E>
- Parameters:
element
- the new element
- Returns:
- a tracker that tracks the new element
remove
protected void remove(AbstractSearchTree.TreeNode x)
- Uses splay to both bring the successor of
x
(if
x
has two children) to be a child of x
, and then also uses splay to
bring x
's parent to the root.
- Overrides:
remove
in class BinarySearchTree<E>
- Parameters:
x
- the tree node to remove
- Throws:
NoSuchElementException
- node x
has already been removed
getLocator
public Locator<E> getLocator(E x)
- As with the other accessors, this method uses splay to bring
x
to the root.
- Specified by:
getLocator
in interface Collection<E>
- Overrides:
getLocator
in class BinarySearchTree<E>
- Parameters:
x
- the element to track
- Returns:
- a locator that has been initialized
at the given element.
- Throws:
NoSuchElementException
- the given element is not in the collection.