|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--structure.AbstractStructure | +--structure.BinarySearchTree | +--structure.SplayTree
An implementation of binary search trees, based on a splay operation by Tarjan et al. An extension of the binary search tree class that decreases the likelyhood of a binary tree becomming degenerate. Example usage:
To create a splay tree containing the months of the year and to print out this tree as it grows we could use the following.
public static void main(String[] argv){ SplayTree test = newSplayTree()
; //declare an array of months String[] months = new String[]{"March", "May", "November", "August", "April", "January", "December", "July", "February", "June", "October", "September"}; //add the months to the tree and print out the tree as it grows for(int i=0; i < months.length; i++){ test.add(months[i])
; System.out.println("Adding: " + months[i] + "\n" +test.BinarySearchTree.treeString()
); } }
Field Summary |
Fields inherited from class structure.BinarySearchTree |
count, ordering, root |
Constructor Summary | |
SplayTree()
Construct an empty search tree. |
|
SplayTree(java.util.Comparator alternateOrder)
Construct an empty search tree. |
Method Summary | |
void |
add(java.lang.Object val)
Add a value to the splay tree. |
boolean |
contains(java.lang.Object val)
Determine if a particular value is within the search tree. |
java.lang.Object |
get(java.lang.Object val)
Fetch a reference to the comparable value in the tree. |
java.util.Iterator |
iterator()
Construct an inorder traversal of the elements in the splay tree. |
java.lang.Object |
remove(java.lang.Object val)
Remove a comparable value from the tree. |
protected void |
splay(BinaryTree splayedNode)
|
java.lang.String |
toString()
Construct a string that represents the splay tree. |
Methods inherited from class structure.BinarySearchTree |
clear, hashCode, isEmpty, locate, predecessor, removeTop, size, successor, treeString |
Methods inherited from class structure.AbstractStructure |
elements, values |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface structure.Structure |
clear, elements, isEmpty, size, values |
Constructor Detail |
public SplayTree()
public SplayTree(java.util.Comparator alternateOrder)
alternateOrder
- the ordering imposed on the values insertedMethod Detail |
public void add(java.lang.Object val)
add
in interface Structure
add
in class BinarySearchTree
val
- The value to be xadded.public boolean contains(java.lang.Object val)
contains
in interface Structure
contains
in class BinarySearchTree
val
- The comparable value to be found.
public java.lang.Object get(java.lang.Object val)
get
in class BinarySearchTree
val
- The value to be sought in tree.
public java.lang.Object remove(java.lang.Object val)
remove
in interface Structure
remove
in class BinarySearchTree
val
- The value to be removed.
protected void splay(BinaryTree splayedNode)
public java.util.Iterator iterator()
iterator
in interface Structure
iterator
in class BinarySearchTree
AbstractIterator
,
Iterator
,
Enumeration
,
Structure.elements()
public java.lang.String toString()
toString
in class BinarySearchTree
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |