structure5
Class SplayTree<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.AbstractStructure<E>
      structure5.BinarySearchTree<E>
          structure5.SplayTree<E>

All Implemented Interfaces:

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

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

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

Field Summary

Fields inherited from class structure5.BinarySearchTree

count, EMPTY, ordering, root

Constructor Summary

SplayTree()
Construct an empty search tree.

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

Method Summary

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

Methods inherited from class structure5.BinarySearchTree

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

Methods inherited from class structure5.AbstractStructure

elements, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure5.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<E> 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(E val)

Add a value to the splay tree.

Specified by:

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

Overrides:

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

Parameters:

val - The value to be xadded.

Postcondition:

adds a value to the binary search tree

contains

public boolean contains(E val)

Determine if a particular value is within the search tree.

Specified by:

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

Overrides:

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

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

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 E remove(E val)

Remove a comparable value from the tree.

Specified by:

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

Overrides:

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

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<E> splayedNode)

iterator

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

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

Specified by:

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

Specified by:

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

Overrides:

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

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

Returns:

A string representing the tree.

Postcondition:

returns string representation