Class BinarySearchTree<T extends KeyedItem<KT>,KT extends java.lang.Comparable<? super KT>>

java.lang.Object
  BinaryTreeBasis<T>
      BinarySearchTree<T,KT>

public class BinarySearchTree<T extends KeyedItem<KT>,KT extends java.lang.Comparable<? super KT>>
extends BinaryTreeBasis<T>

Constructor Summary

BinarySearchTree()
The default constructor for BinarySearchTree initializes the BinaryTree to be empty.

BinarySearchTree(T rootItem)
This constructor for BinarySearchTree initializes the BinarySearchTree to have a root containing the specified data item.

Method Summary

void	balance() This method is used to balance the BinarySearchTree.
TreeNode<T>	balance(java.lang.Object[] arr, int first, int last) This method is the recursive method to balance the BinarySearchTree.
void	delete(KT searchKey) This is the public method used to delete a data item from the BinarySearchTree based on the specified searchKey.
void	delete(T item) This is the public method used to delete a data item from the BinarySearchTree based on the specified data item.
int	height() This is the method the user calls to find the height of the BinarySearchTree.
int	height(TreeNode<T> root) This method is used to obtain the height of the BinarySearchTree.
void	insert(T newItem) This is the public method used to insert a new data item into the BinarySearchTree.
boolean	isBalanced() This is the method the user calls to find out if the BinarySearchTree is balanced.
boolean	isBalanced(TreeNode<T> root) This method is used to check if the BinarySearchTree rooted at the specified node is balanced.
T	retrieve(KT searchKey) This is the public method used to retrieve a data item from the BinarySearchTree based on the specified searchKey.
void	setRootItem(T newItem) This method will override the inherited method from BinaryTree and disable its operation

Methods inherited from class BinaryTreeBasis

getRoot, getRootItem, isEmpty, makeEmpty, setRoot

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BinarySearchTree

public BinarySearchTree()

The default constructor for BinarySearchTree initializes the BinaryTree to be empty.

BinarySearchTree

public BinarySearchTree(T rootItem)

This constructor for BinarySearchTree initializes the BinarySearchTree to have a root containing the specified data item.

Parameters:

rootItem - The data item that will be contained by the root of this BinaryTree

Method Detail

setRootItem

public void setRootItem(T newItem)
                 throws java.lang.UnsupportedOperationException

This method will override the inherited method from BinaryTree and disable its operation

Specified by:

setRootItem in class BinaryTreeBasis<T extends KeyedItem<KT>>

Parameters:

newItem - the data item to be contained in the root node.

Throws:

This - method always throws the UnsupportedOperationException

java.lang.UnsupportedOperationException

insert

public void insert(T newItem)

This is the public method used to insert a new data item into the BinarySearchTree.

Parameters:

newItem - The data item to be inserted into the BinarySearchTree.

retrieve

public T retrieve(KT searchKey)

This is the public method used to retrieve a data item from the BinarySearchTree based on the specified searchKey.

Parameters:

searchKey - The searchKey of the data item the user wishes to retrieve from the BinarySearchTree.

delete

public void delete(KT searchKey)
            throws TreeException

This is the public method used to delete a data item from the BinarySearchTree based on the specified searchKey.

Parameters:

searchKey - The searchKey of the data item the user wishes to delete from the BinarySearchTree.

Throws:

TreeException

delete

public void delete(T item)
            throws TreeException

This is the public method used to delete a data item from the BinarySearchTree based on the specified data item.

Parameters:

item - The data item the user wishes to delete from the BinarySearchTree.

Throws:

TreeException

isBalanced

public boolean isBalanced()

This is the method the user calls to find out if the BinarySearchTree is balanced.

This method will call the recursive method public boolean isBalanced(TreeNode root) to find the answer.

Returns:

Returns true if the BinarySearchTree is balanced, false otherwise.

height

public int height()

This is the method the user calls to find the height of the BinarySearchTree.

This method will call the recursive method public int height(TreeNode root) to calculate the height.

Returns:

Returns the height of the BinarySearchTree.

balance

public void balance()

This method is used to balance the BinarySearchTree.

This method will call the recursive method public TreeNode balance(Object[] arr, int first, int last) to balance the tree.

isBalanced

public boolean isBalanced(TreeNode<T> root)

This method is used to check if the BinarySearchTree rooted at the specified node is balanced.

Parameters:

root - The root node of the BinarySearchTree that is being checked for balance.

Returns:

Returns true if the BinarySearchTree is balanced, false otherwise.

height

public int height(TreeNode<T> root)

This method is used to obtain the height of the BinarySearchTree.

Parameters:

root - The root node of the BinarySearchTree for which we are measuring the height.

Returns:

Returns the height of the BinarySearchTree.

balance

public TreeNode<T> balance(java.lang.Object[] arr,
                           int first,
                           int last)

This method is the recursive method to balance the BinarySearchTree.

Parameters:

arr - An array containing all the data items for the BinarySearchTree in sorted order.

first - The first index of the array.

last - The last index of the array.

Returns:

The root node for this level of the balanced tree.