    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.

##

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 top-down 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 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.

main

    public static void main(String[] args)

    All Packages  Class Hierarchy  This Package  Previous  Next  Index