|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--weiss.nonstandard.BinarySearchTree
Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.
Field Summary | |
protected weiss.nonstandard.BinaryNode |
root
The tree root. |
Constructor Summary | |
BinarySearchTree()
Construct the tree. |
Method Summary | |
java.lang.Comparable |
find(java.lang.Comparable x)
Find an item in the tree. |
java.lang.Comparable |
findMax()
Find the largest item in the tree. |
java.lang.Comparable |
findMin()
Find the smallest item in the tree. |
protected weiss.nonstandard.BinaryNode |
findMin(weiss.nonstandard.BinaryNode t)
Internal method to find the smallest item in a subtree. |
void |
insert(java.lang.Comparable x)
Insert into the tree. |
protected weiss.nonstandard.BinaryNode |
insert(java.lang.Comparable x,
weiss.nonstandard.BinaryNode t)
Internal method to insert into a subtree. |
boolean |
isEmpty()
Test if the tree is logically empty. |
static void |
main(java.lang.String[] args)
|
void |
makeEmpty()
Make the tree logically empty. |
void |
remove(java.lang.Comparable x)
Remove from the tree.. |
protected weiss.nonstandard.BinaryNode |
remove(java.lang.Comparable x,
weiss.nonstandard.BinaryNode t)
Internal method to remove from a subtree. |
void |
removeMin()
Remove minimum item from the tree. |
protected weiss.nonstandard.BinaryNode |
removeMin(weiss.nonstandard.BinaryNode t)
Internal method to remove minimum item from a subtree. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
protected weiss.nonstandard.BinaryNode root
Constructor Detail |
public BinarySearchTree()
Method Detail |
public void insert(java.lang.Comparable x)
x
- the item to insert.DuplicateItemException
- if x is already present.public void remove(java.lang.Comparable x)
x
- the item to remove.ItemNotFoundException
- if x is not found.public void removeMin()
ItemNotFoundException
- if tree is empty.public java.lang.Comparable findMin()
public java.lang.Comparable findMax()
public java.lang.Comparable find(java.lang.Comparable x)
x
- the item to search for.public void makeEmpty()
public boolean isEmpty()
protected weiss.nonstandard.BinaryNode insert(java.lang.Comparable x, weiss.nonstandard.BinaryNode t)
x
- the item to insert.t
- the node that roots the tree.DuplicateItemException
- if x is already present.protected weiss.nonstandard.BinaryNode remove(java.lang.Comparable x, weiss.nonstandard.BinaryNode t)
x
- the item to remove.t
- the node that roots the tree.ItemNotFoundException
- if x is not found.protected weiss.nonstandard.BinaryNode removeMin(weiss.nonstandard.BinaryNode t)
t
- the node that roots the tree.ItemNotFoundException
- if x is not found.protected weiss.nonstandard.BinaryNode findMin(weiss.nonstandard.BinaryNode t)
t
- the node that roots the tree.public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |