weiss.nonstandard
Class SplayTree<AnyType extends java.lang.Comparable<? super AnyType>>

java.lang.Object
  extended by weiss.nonstandard.SplayTree<AnyType>

public class SplayTree<AnyType extends java.lang.Comparable<? super AnyType>>
extends java.lang.Object

Implements a top-down splay tree. Note that all "matching" is based on the compareTo method.


Constructor Summary
SplayTree()
          Construct the tree.
 
Method Summary
 AnyType find(AnyType x)
          Find an item in the tree.
 AnyType findMax()
          Find the largest item in the tree.
 AnyType findMin()
          Find the smallest item in the tree.
 void insert(AnyType x)
          Insert into the tree.
 boolean isEmpty()
          Test if the tree is logically empty.
static void main(java.lang.String[] args)
           
 void makeEmpty()
          Make the tree logically empty.
 void remove(AnyType x)
          Remove from the tree.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SplayTree

public SplayTree()
Construct the tree.

Method Detail

insert

public void insert(AnyType x)
Insert into the tree.

Parameters:
x - the item to insert.
Throws:
DuplicateItemException - if x is already present.

remove

public void remove(AnyType x)
Remove from the tree.

Parameters:
x - the item to remove.
Throws:
ItemNotFoundException - if x is not found.

findMin

public AnyType findMin()
Find the smallest item in the tree. Not the most efficient implementation (uses two passes), but has correct amortized behavior. A good alternative is to first call find with parameter smaller than any item in the tree, then call findMin.

Returns:
the smallest item or null if empty.

findMax

public AnyType findMax()
Find the largest item in the tree. Not the most efficient implementation (uses two passes), but has correct amortized behavior. A good alternative is to first call find with parameter larger than any item in the tree, then call findMax.

Returns:
the largest item or null if empty.

find

public AnyType find(AnyType x)
Find an item in the tree.

Parameters:
x - the item to search for.
Returns:
the matching item or null if not found.

makeEmpty

public void makeEmpty()
Make the tree logically empty.


isEmpty

public boolean isEmpty()
Test if the tree is logically empty.

Returns:
true if empty, false otherwise.

main

public static void main(java.lang.String[] args)