|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object structure5.AbstractStructure<E> structure5.BinarySearchTree<E>
public class BinarySearchTree<E extends java.lang.Comparable<E>>
A binary search tree structure. This structure maintains data in an ordered tree. It does not keep the tree balanced, so performance may degrade if the tree height is not optimal.
Example usage:
To create a Binary search 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){ BinarySearchTree test = newBinarySearchTree()
; //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.treeString()
); } }
SplayTree
,
BinaryTree
Field Summary | |
---|---|
protected int |
count
The number of nodes in the tree |
protected BinaryTree<E> |
EMPTY
The node used as all leaves, in this implementation. |
protected java.util.Comparator<E> |
ordering
The ordering used on this search tree. |
protected BinaryTree<E> |
root
A reference to the root of the tree |
Constructor Summary | |
---|---|
BinarySearchTree()
Constructs a binary search tree with no data |
|
BinarySearchTree(java.util.Comparator<E> alternateOrder)
Constructs a binary search tree with no data |
Method Summary | |
---|---|
void |
add(E value)
Add a (possibly duplicate) value to binary search tree |
void |
clear()
Removes all data from the binary search tree |
boolean |
contains(E value)
Determines if the binary search tree contains a value |
E |
get(E value)
Returns reference to value found within three. |
int |
hashCode()
Returns the hashCode of the value stored by this object. |
boolean |
isEmpty()
Checks for an empty binary search tree |
java.util.Iterator<E> |
iterator()
Returns an iterator over the binary search tree. |
protected BinaryTree<E> |
locate(BinaryTree<E> root,
E value)
|
protected BinaryTree<E> |
predecessor(BinaryTree<E> root)
|
E |
remove(E value)
Remove an value "equals to" the indicated value. |
protected BinaryTree<E> |
removeTop(BinaryTree<E> topNode)
Removes the top node of the tree rooted, performs the necissary rotations to reconnect the tree. |
int |
size()
Determines the number of data values within the tree |
protected BinaryTree<E> |
successor(BinaryTree<E> root)
|
java.lang.String |
toString()
Returns a string representing tree |
java.lang.String |
treeString()
Returns a (possibly long) string representing tree. |
Methods inherited from class structure5.AbstractStructure |
---|
elements, values |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface structure5.Structure |
---|
elements, values |
Field Detail |
---|
protected BinaryTree<E extends java.lang.Comparable<E>> root
protected final BinaryTree<E extends java.lang.Comparable<E>> EMPTY
protected int count
protected java.util.Comparator<E extends java.lang.Comparable<E>> ordering
Constructor Detail |
---|
public BinarySearchTree()
public BinarySearchTree(java.util.Comparator<E> alternateOrder)
Method Detail |
---|
public boolean isEmpty()
isEmpty
in interface Structure<E extends java.lang.Comparable<E>>
isEmpty
in class AbstractStructure<E extends java.lang.Comparable<E>>
public void clear()
clear
in interface Structure<E extends java.lang.Comparable<E>>
public int size()
size
in interface Structure<E extends java.lang.Comparable<E>>
protected BinaryTree<E> locate(BinaryTree<E> root, E value)
protected BinaryTree<E> predecessor(BinaryTree<E> root)
protected BinaryTree<E> successor(BinaryTree<E> root)
public void add(E value)
add
in interface Structure<E extends java.lang.Comparable<E>>
val
- A reference to non-null objectpublic boolean contains(E value)
contains
in interface Structure<E extends java.lang.Comparable<E>>
contains
in class AbstractStructure<E extends java.lang.Comparable<E>>
val
- The value sought. Should be non-null
public E get(E value)
val
- Value sought from within tree
public E remove(E value)
remove
in interface Structure<E extends java.lang.Comparable<E>>
val
- Value sought to be removed from tree
protected BinaryTree<E> removeTop(BinaryTree<E> topNode)
topNode
- Contains the value we want to remove
public java.util.Iterator<E> iterator()
iterator
in interface java.lang.Iterable<E extends java.lang.Comparable<E>>
iterator
in interface Structure<E extends java.lang.Comparable<E>>
AbstractIterator
,
Iterator
,
Enumeration
,
Structure.elements()
public int hashCode()
hashCode
in class AbstractStructure<E extends java.lang.Comparable<E>>
public java.lang.String treeString()
toString()
in that toString()
outputs
a single line representation of the contents of the tree.
treeString
, however, prints out a graphical
representations of the tree's structure.
public java.lang.String toString()
toString
in class java.lang.Object
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |