Package gaiasky.util

Class BinarySearchTree<T extends Comparable<T>>

java.lang.Object

gaiasky.util.BinarySearchTree<T>

public class BinarySearchTree<T extends Comparable<T>>
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	BinarySearchTree.BinaryNode<T>	Basic node stored in unbalanced binary search trees Note that this class is not accessible outside of this package.

Field Summary

Fields

Modifier and Type	Field	Description
protected BinarySearchTree.BinaryNode<T>	root	The tree root.

Constructor Summary

Constructors

Constructor	Description
BinarySearchTree()	Construct the tree.

Method Summary

Modifier and Type	Method	Description
Comparable<T>	find(Comparable<T> x)	Find an item in the tree.
Comparable<T>	findIntervalStart(Comparable<T> x)	Find the start of the interval where x is in.
Comparable<T>	findMax()	Find the largest item in the tree.
Comparable<T>	findMin()	Find the smallest item in the tree.
protected BinarySearchTree.BinaryNode<T>	findMin(BinarySearchTree.BinaryNode<T> t)	Internal method to find the smallest item in a subtree.
void	insert(T x)	Insert into the tree.
protected BinarySearchTree.BinaryNode<T>	insert(T x, BinarySearchTree.BinaryNode<T> t)	Internal method to insert into a subtree.
boolean	isEmpty()	Test if the tree is logically empty.
static void	main(String[] args)
protected BinarySearchTree.BinaryNode<T>	remove(Comparable<T> x, BinarySearchTree.BinaryNode<T> t)	Internal method to remove from a subtree.
void	remove(T x)	Remove from the tree.
protected BinarySearchTree.BinaryNode<T>	removeMin(BinarySearchTree.BinaryNode<T> 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 Details

root

protected BinarySearchTree.BinaryNode<T extends Comparable<T>> root

The tree root.

Constructor Details

BinarySearchTree

public BinarySearchTree()

Construct the tree.

Method Details

main

public static void main(String[] args)

insert

public void insert(T x)

Insert into the tree.

Parameters:

x - the item to insert.

Throws:

RuntimeException - if x is already present.

remove

public void remove(T x)

Remove from the tree.

Parameters:

x - the item to remove.

Throws:

RuntimeException - if x is not found.

findMin

public Comparable<T> findMin()

Find the smallest item in the tree.

Returns:

smallest item or null if empty.

findMax

public Comparable<T> findMax()

Find the largest item in the tree.

Returns:

the largest item or null if empty.

find

public Comparable<T> find(Comparable<T> 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 Comparable<T> findIntervalStart(Comparable<T> x)

Find the start of the interval where x is in.

Parameters:

x - is the item to search the start for.

Returns:

object contained in the start of the interval where x is in, or null if x is not contained in any interval.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

insert

protected BinarySearchTree.BinaryNode<T> insert(T x,
 BinarySearchTree.BinaryNode<T> 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:

RuntimeException - if x is already present.

remove

protected BinarySearchTree.BinaryNode<T> remove(Comparable<T> x,
 BinarySearchTree.BinaryNode<T> 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:

RuntimeException - if x is not found.

removeMin

protected BinarySearchTree.BinaryNode<T> removeMin(BinarySearchTree.BinaryNode<T> t)

Internal method to remove minimum item from a subtree.

Parameters:

t - the node that roots the tree.

Returns:

the new root.

Throws:

RuntimeException - if x is not found.

findMin

protected BinarySearchTree.BinaryNode<T> findMin(BinarySearchTree.BinaryNode<T> 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.