All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class structure.SplayTree 

java.lang.Object
    |
    +----structure.BinarySearchTree
            |
            +----structure.SplayTree
public class SplayTree
extends BinarySearchTree
An implementation of binary search trees, based on a splay operation by Tarjan et al. An extension of the binary search tree class.

Constructor Index

o SplayTree()
Construct an empty search tree.

Method Index

o add(Object)
Add a value to the splay tree.
o contains(Object)
Determine if a particular comparable value is within the search tree.
o elements()
Construct an inorder traversal of the elements in the splay tree.
o get(Object)
Fetch a reference to the comparable value in the tree.
o remove(Object)
Remove a comparable value from the tree.
o toString()
Construct a string that represents the splay tree.

Constructors

o SplayTree 
public SplayTree()
Construct an empty search tree.

Postcondition:
construct a new splay tree

Methods

o add 
public void add(Object val)
Add a value to the splay tree.

Postcondition:
adds a value to the binary search tree.

Parameters:
val - The value to be added.
Overrides:
add in class BinarySearchTree
o contains 
public boolean contains(Object val)
Determine if a particular comparable value is within the search tree.

Postcondition:
returns true iff val is a value found within the tree

Parameters:
val - The comparable value to be found.
Returns:
True iff the comparable value is within the tree.
Overrides:
contains in class BinarySearchTree
o get 
public Object get(Object 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.

Postcondition:
returns object found in tree, or null

Parameters:
val - The value to be sought in tree.
Returns:
A reference to the value within the tree.
Overrides:
get in class BinarySearchTree
o remove 
public Object remove(Object val)
Remove a comparable value from the tree.

Postcondition:
removes one instance of val, if found

Parameters:
val - The value to be removed.
Returns:
The actual value removed.
Overrides:
remove in class BinarySearchTree
o elements 
public Iterator elements()
Construct an inorder traversal of the elements in the splay tree.

Postcondition:
returns iterator that traverses tree nodes in order

Returns:
An iterator to traverse the tree.
Overrides:
elements in class BinarySearchTree
o toString 
public String toString()
Construct a string that represents the splay tree.

Postcondition:
returns string representation

Returns:
A string representing the tree.
Overrides:
toString in class BinarySearchTree
All Packages  Class Hierarchy  This Package  Previous  Next  Index