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 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());
      }
  }
 

Fields inherited from class structure.BinarySearchTree

count, ordering, root

Constructor Summary

SplayTree()
Construct an empty search tree.

SplayTree(Comparator alternateOrder)
Construct an empty search tree.

Method Summary

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

Methods inherited from class structure.BinarySearchTree

clear, hashCode, isEmpty, locate, predecessor, removeTop, size, successor, treeString

Methods inherited from class structure.AbstractStructure

elements, values

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, notify, notifyAll, registerNatives, wait, wait, wait

Methods inherited from interface structure.Structure

clear, elements, isEmpty, size, values

Constructor Detail

SplayTree

public SplayTree()

Construct an empty search tree.

SplayTree

public SplayTree(Comparator alternateOrder)

Construct an empty search tree.

Parameters:

alternateOrder - the ordering imposed on the values inserted

Method Detail

add

public void add(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 xadded.

Postcondition:

adds a value to the binary search tree

contains

public boolean contains(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.

Postcondition:

returns true iff val is a value found within the tree

Returns:

True iff the comparable value is within the tree.

get

public Object get(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.

Postcondition:

returns object found in tree, or null

Returns:

A reference to the value within the tree.

remove

public Object remove(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.

Postcondition:

removes one instance of val, if found

Returns:

The actual value removed.

splay

protected void splay(BinaryTree splayedNode)

iterator

public Iterator iterator()

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

Specified by:

iterator in interface Structure

Overrides:

iterator in class BinarySearchTree

Postcondition:

returns iterator that traverses tree nodes in order

Returns:

An iterator to traverse the tree.

toString

public String toString()

Construct a string that represents the splay tree.

Overrides:

toString in class BinarySearchTree

Postcondition:

returns string representation

Returns:

A string representing the tree.