goldman.collection.ordered
Class SplayTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.AbstractSearchTree<E>
          extended by goldman.collection.ordered.BinarySearchTree<E>
              extended by goldman.collection.ordered.BalancedBinarySearchTree<E>
                  extended by 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.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.ordered.BinarySearchTree
BinarySearchTree.BSTNode, 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
 
Fields inherited from class goldman.collection.ordered.BinarySearchTree
FRONTIER_L, 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
SplayTree()
           
SplayTree(Comparator<? super E> comp)
           
 
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.ordered.BinarySearchTree
clear, clearNodes, createFrontierNode, createTreeNode, find, findLastInsertPosition, insert, iterator, iteratorAtEnd
 
Methods inherited from class goldman.collection.ordered.AbstractSearchTree
get, getEquivalentElement, getLastNodeSearchIndex, 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, iteratorAtEnd
 
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
 

Constructor Detail

SplayTree

public SplayTree()

SplayTree

public SplayTree(Comparator<? super E> comp)
Parameters:
comp - the comparator to use to order the elements
Method Detail

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.