|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectweiss.nonstandard.BinarySearchTree<AnyType>
public class BinarySearchTree<AnyType extends java.lang.Comparable<? super AnyType>>
Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.
| Field Summary | |
|---|---|
protected weiss.nonstandard.BinaryNode<AnyType> |
root
The tree root. |
| Constructor Summary | |
|---|---|
BinarySearchTree()
Construct the tree. |
|
| Method Summary | |
|---|---|
AnyType |
find(AnyType x)
Find an item in the tree. |
AnyType |
findMax()
Find the largest item in the tree. |
AnyType |
findMin()
Find the smallest item in the tree. |
protected weiss.nonstandard.BinaryNode<AnyType> |
findMin(weiss.nonstandard.BinaryNode<AnyType> t)
Internal method to find the smallest item in a subtree. |
void |
insert(AnyType x)
Insert into the tree. |
protected weiss.nonstandard.BinaryNode<AnyType> |
insert(AnyType x,
weiss.nonstandard.BinaryNode<AnyType> 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(AnyType x)
Remove from the tree.. |
protected weiss.nonstandard.BinaryNode<AnyType> |
remove(AnyType x,
weiss.nonstandard.BinaryNode<AnyType> t)
Internal method to remove from a subtree. |
void |
removeMin()
Remove minimum item from the tree. |
protected weiss.nonstandard.BinaryNode<AnyType> |
removeMin(weiss.nonstandard.BinaryNode<AnyType> 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<AnyType extends java.lang.Comparable<? super AnyType>> root
| Constructor Detail |
|---|
public BinarySearchTree()
| Method Detail |
|---|
public void insert(AnyType x)
x - the item to insert.
DuplicateItemException - if x is already present.public void remove(AnyType x)
x - the item to remove.
ItemNotFoundException - if x is not found.public void removeMin()
ItemNotFoundException - if tree is empty.public AnyType findMin()
public AnyType findMax()
public AnyType find(AnyType x)
x - the item to search for.
public void makeEmpty()
public boolean isEmpty()
protected weiss.nonstandard.BinaryNode<AnyType> insert(AnyType x,
weiss.nonstandard.BinaryNode<AnyType> t)
x - the item to insert.t - the node that roots the tree.
DuplicateItemException - if x is already present.
protected weiss.nonstandard.BinaryNode<AnyType> remove(AnyType x,
weiss.nonstandard.BinaryNode<AnyType> t)
x - the item to remove.t - the node that roots the tree.
ItemNotFoundException - if x is not found.protected weiss.nonstandard.BinaryNode<AnyType> removeMin(weiss.nonstandard.BinaryNode<AnyType> t)
t - the node that roots the tree.
ItemNotFoundException - if t is empty.protected weiss.nonstandard.BinaryNode<AnyType> findMin(weiss.nonstandard.BinaryNode<AnyType> t)
t - the node that roots the tree.
public static void main(java.lang.String[] args)
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||