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 topdown splay tree.
Note that all "matching" is based on the compares method.

SplayTree()
 Construct the tree.

find(Comparable)
 Find an item in the tree.

findMax()
 Find the largest item in the tree.

findMin()
 Find the smallest item in the tree.

getRoot()
 Return item stored in the root.

insert(Comparable)
 Insert into the tree.

isEmpty()
 Test if the tree is logically empty.

main(String[])


makeEmpty()
 Make the tree logically empty.

printTree()
 Print the tree contents in sorted order.

remove(Comparable)
 Remove from the tree.

removeMin()
 Remove the smallest item from the tree.

splay(Comparable, BinaryNode)
 Internal method to perform a topdown splay.
SplayTree
public SplayTree()
 Construct the tree.
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.
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.
getRoot
public Comparable getRoot() throws ItemNotFound
 Return item stored in the root.
 Throws:
ItemNotFound
 if the tree is empty.
removeMin
public void removeMin() throws ItemNotFound
 Remove the smallest item from the tree.
 Throws:
ItemNotFound
 if the tree is empty.
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.
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.
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.
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.
printTree
public void printTree()
 Print the tree contents in sorted order.
splay
protected BinaryNode splay(Comparable x,
BinaryNode t)
 Internal method to perform a topdown 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.
main
public static void main(String[] args)
All Packages Class Hierarchy This Package Previous Next Index