structure
Class SplayTree

java.lang.Object
  extended by structure.AbstractStructure
      extended by structure.BinarySearchTree
          extended by structure.SplayTree
All Implemented Interfaces:
OrderedStructure, Structure

public class SplayTree
extends BinarySearchTree
implements OrderedStructure

An implementation of binary search trees, based on a splay operation by Tarjan et al. An extension of the binary search tree class.


Field Summary
 
Fields inherited from class structure.BinarySearchTree
count, ordering, root
 
Constructor Summary
SplayTree()
          Construct an empty search tree.
SplayTree(java.util.Comparator alternateOrder)
          Construct an empty search tree.
 
Method Summary
 void add(java.lang.Object val)
          Add a value to the splay tree.
 boolean contains(java.lang.Object val)
          Determine if a particular value is within the search tree.
 java.lang.Object get(java.lang.Object val)
          Fetch a reference to the comparable value in the tree.
 java.util.Iterator iterator()
          Construct an inorder traversal of the elements in the splay tree.
 java.lang.Object remove(java.lang.Object val)
          Remove a comparable value from the tree.
protected  void splay(BinaryTree splayedNode)
           
 java.lang.String toString()
          Construct a string that represents the splay tree.
 
Methods inherited from class structure.BinarySearchTree
clear, isEmpty, locate, predecessor, removeTop, size, successor
 
Methods inherited from class structure.AbstractStructure
elements, hashCode, values
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface structure.Structure
clear, elements, isEmpty, size, values
 

Constructor Detail

SplayTree

public SplayTree()
Construct an empty search tree.

Postcondition:
construct a new splay tree

SplayTree

public SplayTree(java.util.Comparator alternateOrder)
Construct an empty search tree.

Parameters:
alternateOrder - the ordering imposed on the values inserted
Postcondition:
construct a new splay tree
Method Detail

add

public void add(java.lang.Object val)
Add a value to the splay tree.

Specified by:
add in interface Structure
Overrides:
add in class BinarySearchTree
Parameters:
val - The value to be added.
Postcondition:
adds a value to the binary search tree

contains

public boolean contains(java.lang.Object val)
Determine if a particular value is within the search tree.

Specified by:
contains in interface Structure
Overrides:
contains in class BinarySearchTree
Parameters:
val - The comparable value to be found.
Returns:
True iff the comparable value is within the tree.
Postcondition:
returns true iff val is a value found within the tree

get

public java.lang.Object get(java.lang.Object val)
Fetch a reference to the comparable value in the tree. Resulting value may be inspected, but should not be modified in a way that might change its position within tree.

Overrides:
get in class BinarySearchTree
Parameters:
val - The value to be sought in tree.
Returns:
A reference to the value within the tree.
Postcondition:
returns object found in tree, or null

remove

public java.lang.Object remove(java.lang.Object val)
Remove a comparable value from the tree.

Specified by:
remove in interface Structure
Overrides:
remove in class BinarySearchTree
Parameters:
val - The value to be removed.
Returns:
The actual value removed.
Postcondition:
removes one instance of val, if found

splay

protected void splay(BinaryTree splayedNode)

iterator

public java.util.Iterator iterator()
Construct an inorder traversal of the elements in the splay tree.

Specified by:
iterator in interface Structure
Overrides:
iterator in class BinarySearchTree
Returns:
An iterator to traverse the tree.
See Also:
AbstractIterator, Iterator, Enumeration, Structure.elements()
Postcondition:
returns iterator that traverses tree nodes in order

toString

public java.lang.String toString()
Construct a string that represents the splay tree.

Overrides:
toString in class BinarySearchTree
Returns:
A string representing the tree.
Postcondition:
returns string representation