Class BinarySearchTree<K extends java.lang.Comparable<? super K>,V>

java.lang.Object

BinarySearchTree<K,V>

public class BinarySearchTree<K extends java.lang.Comparable<? super K>,V>
extends java.lang.Object

Field Summary

Fields

Modifier and Type	Field and Description
private TreeNode<K,V>	root

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree() Default constructor for BinarySearchTree.
BinarySearchTree(TreeNode<K,V> root) This constructor instantiates a BinarySearchTree with the given root

Method Summary

Modifier and Type	Method and Description
void	balance() This method is used to balance the BinarySearchTree.
private TreeNode<K,V>	balanceTree(java.lang.Object[] arr, int first, int last) The private recursive method to balance the BinarySearchTree.
void	delete(K key) This is the public method used to delete a TreeItem from the BinarySearchTree based on the specified key.
private TreeNode<K,V>	deleteItem(TreeNode<K,V> node, K key) The private recursive method to delete the TreeItem with the specified key from BinarySearchTree.
private TreeNode<K,V>	deleteLeftmost(TreeNode<K,V> node) The private recursive method to deleted the left-most child of a subtree This method is initially called by the deleteNode method
private TreeNode<K,V>	deleteNode(TreeNode<K,V> node) The private recursive method to delete the specified TreeNode.
TreeItem<K,V>	find(K key) Method to find and retrieve the TreeItem with the given key if it is in the BinarySearchTree.
private TreeItem<K,V>	findItem(TreeNode<K,V> node, K key) The private recursive method to find and retrieve the TreeItem with the given key if it is in the BinarySearchTree.
private TreeNode<K,V>	findLeftmost(TreeNode<K,V> node) The private recursive method to find the left-most child of a subtree This method is initially called by the deleteNode method
TreeNode<K,V>	getRoot() Method to get the current root of this BinarySearchTree
TreeItem<K,V>	getRootItem() Method to get the TreeItem currently in the root of this BinarySearchTree
int	height() This method is used to obtain the height of the BinarySearchTree.
void	insert(TreeItem<K,V> treeItem) Method to insert the given TreeItem into the BinarySearchTree
private TreeNode<K,V>	insertItem(TreeNode<K,V> node, TreeNode<K,V> parent, TreeItem<K,V> treeItem) The private recursive method to insert the TreeItem into the BinarySearchTree.
boolean	isBalanced() This is the method the user calls to find out if the BinarySearchTree is balanced.
private boolean	isBalancedSubtree(TreeNode<K,V> node) The private recursive method to determine if the subtree rooted at the given node is balanced.
boolean	isEmpty() Method to find out if the BinarySearchTree is empty
void	makeEmpty() Method to remove all entries from the BinarySearchTree.
void	setRoot(TreeNode<K,V> root) Method to set set the root of this BinarySearchTree
private int	treeHeight(TreeNode<K,V> node) The private recursive method to calculate the height of a subtree rooted at the specified TreeNode.

Methods inherited from class java.lang.Object

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

Field Detail

root

private TreeNode<K extends java.lang.Comparable<? super K>,V> root

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Default constructor for BinarySearchTree. This constructor instantiates an empty tree

BinarySearchTree

public BinarySearchTree(TreeNode<K,V> root)

This constructor instantiates a BinarySearchTree with the given root

Parameters:

root - The root TreeNode for this BinarySearchTree

Method Detail

getRoot

public TreeNode<K,V> getRoot()

Method to get the current root of this BinarySearchTree

Returns:

The root TreeNode for this BinarySearchTree

setRoot

public void setRoot(TreeNode<K,V> root)

Method to set set the root of this BinarySearchTree

Parameters:

root - The new root of this BinarySearchTree

getRootItem

public TreeItem<K,V> getRootItem()
                          throws TreeException

Method to get the TreeItem currently in the root of this BinarySearchTree

Returns:

Returns the TreeItem currently in the root

Throws:

TreeException - Throws a TreeException if the root of the tree is null

isEmpty

public boolean isEmpty()

Method to find out if the BinarySearchTree is empty

Returns:

Returns true if the root in null, otherwise, returns false

makeEmpty

public void makeEmpty()

Method to remove all entries from the BinarySearchTree.

find

public TreeItem<K,V> find(K key)

Method to find and retrieve the TreeItem with the given key if it is in the BinarySearchTree.

Parameters:

key - The key that the user wishes to search for

Returns:

The TreeItem with the given key if found. Otherwise, returns null

findItem

private TreeItem<K,V> findItem(TreeNode<K,V> node,
                               K key)

The private recursive method to find and retrieve the TreeItem with the given key if it is in the BinarySearchTree. This method is initially called by the find method

Parameters:

node - The current TreeNode being searched

key - The key that the user wishes to search for

Returns:

The TreeItem with the given key if found. Otherwise, returns null

insert

public void insert(TreeItem<K,V> treeItem)

Method to insert the given TreeItem into the BinarySearchTree

Parameters:

treeItem - The TreeItem to insert into the BinarySearchTree

insertItem

private TreeNode<K,V> insertItem(TreeNode<K,V> node,
                                 TreeNode<K,V> parent,
                                 TreeItem<K,V> treeItem)

The private recursive method to insert the TreeItem into the BinarySearchTree. This method is initially called by the insert method

Parameters:

node - The current TreeNode being examined for insertion

parent - The current parent of the TreeNode being examined

treeItem - The TreeItem to insert into the BinarySearchTree

Returns:

The node that existed or was inserted into the BinarySearchTree

delete

public void delete(K key)
            throws TreeException

This is the public method used to delete a TreeItem from the BinarySearchTree based on the specified key.

Parameters:

key - The key of the TreeItem the user wishes to delete from the BinarySearchTree.

Throws:

TreeException

deleteItem

private TreeNode<K,V> deleteItem(TreeNode<K,V> node,
                                 K key)

The private recursive method to delete the TreeItem with the specified key from BinarySearchTree. This method is initially called by the delete method

Parameters:

node - The current TreeNode being examined for deletion

key - The key of the TreeItem to be deleted

Returns:

The TreeNode reference that will replace the deleted TreeNode

deleteNode

private TreeNode<K,V> deleteNode(TreeNode<K,V> node)

The private recursive method to delete the specified TreeNode. There are four cases to consider:

1. The node is a leaf: just remove the node.
2. The node has no left child: replace the node with it's right child
3. The node has no right child: replace the node with it's left child
4. The node has two children: find the in-order successor, swap TreeItems and delete the successor

This method is initally called by the deleteItem method

Parameters:

node - The current TreeNode being examined for deletion

Returns:

The TreeNode reference that will replace the deleted TreeNode

findLeftmost

private TreeNode<K,V> findLeftmost(TreeNode<K,V> node)

The private recursive method to find the left-most child of a subtree This method is initially called by the deleteNode method

Parameters:

node - The current TreeNode being examined for being the left-most child

Returns:

The TreeNode reference that is the left-most child

deleteLeftmost

private TreeNode<K,V> deleteLeftmost(TreeNode<K,V> node)

The private recursive method to deleted the left-most child of a subtree This method is initially called by the deleteNode method

Parameters:

node - The current TreeNode being examined for being the left-most child

Returns:

The TreeNode reference that is the left-most child

height

public int height()

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

Returns:

Returns the height of the BinarySearchTree.

treeHeight

private int treeHeight(TreeNode<K,V> node)

The private recursive method to calculate the height of a subtree rooted at the specified TreeNode. This method is initially called by the height method and isBalancedSubtree

Parameters:

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

Returns:

Returns the height of the BinarySearchTree.

isBalanced

public boolean isBalanced()

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

Returns:

Returns true if the BinarySearchTree is balanced, false otherwise.

isBalancedSubtree

private boolean isBalancedSubtree(TreeNode<K,V> node)

The private recursive method to determine if the subtree rooted at the given node is balanced. This method is initially called by the isBalanced method

Parameters:

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

Returns:

Returns true if the BinarySearchTree is balanced, false otherwise.

balance

public void balance()

This method is used to balance the BinarySearchTree.

balanceTree

private TreeNode<K,V> balanceTree(java.lang.Object[] arr,
                                  int first,
                                  int last)

The private recursive method to balance the BinarySearchTree. This method is initially called by the balance method

Parameters:

arr - An array containing all the TreeItems 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.