structure
Class SplayTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

java.lang.Object
  structure.AbstractStructure<ELTTYPE>
      structure.BinarySearchTree<ELTTYPE>
          structure.SplayTree<ELTTYPE>

All Implemented Interfaces:

java.lang.Iterable<ELTTYPE>, OrderedStructure<ELTTYPE>, Structure<ELTTYPE>

public class SplayTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>
extends BinarySearchTree<ELTTYPE>
implements OrderedStructure<ELTTYPE>

An implementation of binary search trees, based on a splay operation by Tarjan et al. An extension of the binary search tree class that decreases the likelyhood of a binary tree becomming degenerate. Example usage:

To create a splay tree containing the months of the year and to print out this tree as it grows we could use the following.

 public static void main(String[] argv){
     SplayTree test = new SplayTree();
       
     //declare an array of months
     String[] months = new String[]{"March", "May", "November", "August", 
                              "April", "January", "December", "July",
                                      "February", "June", "October", "September"};
      
     //add the months to the tree and print out the tree as it grows
     for(int i=0; i < months.length; i++){
        test.add(months[i]);
        System.out.println("Adding: " + months[i] + "\n" +test.BinarySearchTree.treeString());
      }
  }
 

Constructor Summary

SplayTree()
Construct an empty search tree.

SplayTree(java.util.Comparator<ELTTYPE> alternateOrder)
Construct an empty search tree.

Method Summary

void	add(ELTTYPE val) Add a value to the splay tree.
boolean	contains(ELTTYPE val) Determine if a particular value is within the search tree.
ELTTYPE	get(ELTTYPE val) Fetch a reference to the comparable value in the tree.
java.util.Iterator<ELTTYPE>	iterator() Construct an inorder traversal of the elements in the splay tree.
ELTTYPE	remove(ELTTYPE val) Remove a comparable value from the tree.
java.lang.String	toString() Construct a string that represents the splay tree.

Methods inherited from class structure.BinarySearchTree

clear, hashCode, isEmpty, size, treeString

Methods inherited from class structure.AbstractStructure

elements, values

Methods inherited from class java.lang.Object

equals, 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.

Post:

construct a new splay tree

SplayTree

public SplayTree(java.util.Comparator<ELTTYPE> alternateOrder)

Construct an empty search tree.

Parameters:

alternateOrder - the ordering imposed on the values inserted

Post:

construct a new splay tree

Method Detail

add

public void add(ELTTYPE val)

Add a value to the splay tree.

Specified by:

add in interface Structure<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Overrides:

add in class BinarySearchTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Parameters:

val - The value to be xadded.

Post:

adds a value to the binary search tree

contains

public boolean contains(ELTTYPE val)

Determine if a particular value is within the search tree.

Specified by:

contains in interface Structure<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Overrides:

contains in class BinarySearchTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Parameters:

val - The comparable value to be found.

Returns:

True iff the comparable value is within the tree.

Post:

returns true iff val is a value found within the tree

get

public ELTTYPE get(ELTTYPE 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<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Parameters:

val - The value to be sought in tree.

Returns:

A reference to the value within the tree.

Post:

returns object found in tree, or null

remove

public ELTTYPE remove(ELTTYPE val)

Remove a comparable value from the tree.

Specified by:

remove in interface Structure<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Overrides:

remove in class BinarySearchTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Parameters:

val - The value to be removed.

Returns:

The actual value removed.

Post:

removes one instance of val, if found

iterator

public java.util.Iterator<ELTTYPE> iterator()

Construct an inorder traversal of the elements in the splay tree.

Specified by:

iterator in interface java.lang.Iterable<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Specified by:

iterator in interface Structure<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Overrides:

iterator in class BinarySearchTree<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Returns:

An iterator to traverse the tree.

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Post:

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<ELTTYPE extends java.lang.Comparable<ELTTYPE>>

Returns:

A string representing the tree.

Post:

returns string representation