Package gaia.cu9.ari.gaiaorbit.util
Class BinarySearchTree
- java.lang.Object
-
- gaia.cu9.ari.gaiaorbit.util.BinarySearchTree
-
public class BinarySearchTree extends java.lang.Object
Implements an unbalanced binary search tree. Note that all "matching" is based on the compareTo method.
-
-
Field Summary
Fields Modifier and Type Field Description protected gaia.cu9.ari.gaiaorbit.util.BinaryNode
root
The tree root.
-
Constructor Summary
Constructors Constructor Description BinarySearchTree()
Construct the tree.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.Comparable
find(java.lang.Comparable x)
Find an item in the tree.java.lang.Comparable
findIntervalStart(java.lang.Comparable x)
Find the start of the interval where x is in.java.lang.Comparable
findMax()
Find the largest item in the tree.java.lang.Comparable
findMin()
Find the smallest item in the tree.protected gaia.cu9.ari.gaiaorbit.util.BinaryNode
findMin(gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to find the smallest item in a subtree.void
insert(java.lang.Comparable x)
Insert into the tree.protected gaia.cu9.ari.gaiaorbit.util.BinaryNode
insert(java.lang.Comparable x, gaia.cu9.ari.gaiaorbit.util.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 gaia.cu9.ari.gaiaorbit.util.BinaryNode
remove(java.lang.Comparable x, gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to remove from a subtree.void
removeMin()
Remove minimum item from the tree.protected gaia.cu9.ari.gaiaorbit.util.BinaryNode
removeMin(gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to remove minimum item from a subtree.
-
-
-
Method Detail
-
insert
public void insert(java.lang.Comparable x)
Insert into the tree.- Parameters:
x
- the item to insert.- Throws:
java.lang.RuntimeException
- if x is already present.
-
remove
public void remove(java.lang.Comparable x)
Remove from the tree..- Parameters:
x
- the item to remove.- Throws:
java.lang.RuntimeException
- if x is not found.
-
removeMin
public void removeMin()
Remove minimum item from the tree.- Throws:
java.lang.RuntimeException
- if tree is empty.
-
findMin
public java.lang.Comparable findMin()
Find the smallest item in the tree.- Returns:
- smallest item or null if empty.
-
findMax
public java.lang.Comparable findMax()
Find the largest item in the tree.- Returns:
- the largest item or null if empty.
-
find
public java.lang.Comparable find(java.lang.Comparable x)
Find an item in the tree.- Parameters:
x
- the item to search for.- Returns:
- the matching item or null if not found.
-
findIntervalStart
public java.lang.Comparable findIntervalStart(java.lang.Comparable x)
Find the start of the interval where x is in.- Parameters:
x
- is the item to search the start for.- Returns:
- node containing the start of the interval where x is in, or null if x is not contained in any interval.
-
makeEmpty
public void makeEmpty()
Make the tree logically empty.
-
isEmpty
public boolean isEmpty()
Test if the tree is logically empty.- Returns:
- true if empty, false otherwise.
-
insert
protected gaia.cu9.ari.gaiaorbit.util.BinaryNode insert(java.lang.Comparable x, gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to insert into a subtree.- Parameters:
x
- the item to insert.t
- the node that roots the tree.- Returns:
- the new root.
- Throws:
java.lang.RuntimeException
- if x is already present.
-
remove
protected gaia.cu9.ari.gaiaorbit.util.BinaryNode remove(java.lang.Comparable x, gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to remove from a subtree.- Parameters:
x
- the item to remove.t
- the node that roots the tree.- Returns:
- the new root.
- Throws:
java.lang.RuntimeException
- if x is not found.
-
removeMin
protected gaia.cu9.ari.gaiaorbit.util.BinaryNode removeMin(gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to remove minimum item from a subtree.- Parameters:
t
- the node that roots the tree.- Returns:
- the new root.
- Throws:
java.lang.RuntimeException
- if x is not found.
-
findMin
protected gaia.cu9.ari.gaiaorbit.util.BinaryNode findMin(gaia.cu9.ari.gaiaorbit.util.BinaryNode t)
Internal method to find the smallest item in a subtree.- Parameters:
t
- the node that roots the tree.- Returns:
- node containing the smallest item.
-
main
public static void main(java.lang.String[] args)
-
-