All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class DataStructures.SplayTree 

java.lang.Object
    |
    +----DataStructures.SplayTree
public class SplayTree
extends Object
implements SearchTree
Implements a top-down splay tree. Note that all "matching" is based on the compares method.

Constructor Index

o SplayTree()
Construct the tree.

Method Index

o find(Comparable)
Find an item in the tree.
o findMax()
Find the largest item in the tree.
o findMin()
Find the smallest item in the tree.
o getRoot()
Return item stored in the root.
o insert(Comparable)
Insert into the tree.
o isEmpty()
Test if the tree is logically empty.
o main(String[])
o makeEmpty()
Make the tree logically empty.
o printTree()
Print the tree contents in sorted order.
o remove(Comparable)
Remove from the tree.
o removeMin()
Remove the smallest item from the tree.
o splay(Comparable, BinaryNode)
Internal method to perform a top-down splay.

Constructors

o SplayTree 
public SplayTree()
Construct the tree.

Methods

o insert 
public void insert(Comparable x) throws DuplicateItem
Insert into the tree.

Parameters:
x - the item to insert.
Throws: DuplicateItem
if an item that matches x is already in the tree.
o remove 
public void remove(Comparable x) throws ItemNotFound
Remove from the tree.

Parameters:
x - the item to remove.
Throws: ItemNotFound
if no item that matches x can be found in the tree.
o getRoot 
public Comparable getRoot() throws ItemNotFound
Return item stored in the root.

Throws: ItemNotFound
if the tree is empty.
o removeMin 
public void removeMin() throws ItemNotFound
Remove the smallest item from the tree.

Throws: ItemNotFound
if the tree is empty.
o findMin 
public Comparable findMin() throws ItemNotFound
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.
Throws: ItemNotFound
if the tree is empty.
o findMax 
public Comparable findMax() throws ItemNotFound
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.
Throws: ItemNotFound
if the tree is empty.
o find 
public Comparable find(Comparable x) throws ItemNotFound
Find an item in the tree.

Parameters:
x - the item to search for.
Returns:
the matching item.
Throws: ItemNotFound
if no item that matches x can be found in the tree.
o makeEmpty 
public void makeEmpty()
Make the tree logically empty.

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

Returns:
true if empty, false otherwise.
o printTree 
public void printTree()
Print the tree contents in sorted order.

o splay 
protected BinaryNode splay(Comparable x,
                           BinaryNode t)
Internal method to perform a top-down splay. The last accessed node becomes the new root. This method may be overridden to use a different splaying algorithm, however, the splay tree code depends on the accessed item going to the root.

Parameters:
x - the target item to splay around.
t - the root of the subtree to splay.
Returns:
the subtree after the splay.
o main 
public static void main(String[] args)
All Packages  Class Hierarchy  This Package  Previous  Next  Index