structure
Class SplayTree

java.lang.Object
  structure.AbstractStructure
      structure.BinarySearchTree
          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