AVL
Class AVLTree<Key,Data>

java.lang.Object
  AVL.AVLTree<Key,Data>

public class AVLTree<Key,Data>
extends java.lang.Object

Implementation of a generic AVL Tree. The data stored in the tree are of the type Data and the associated keys are of the type Key. A Comparator is used to compare keys. Code has been taken from the course textbook: Cormen, Leiserson, Rivest, Stein: Introduction to Algorithm (2nd edition). McGraw-Hill (2001), ISBN: 0070131511

Field Summary

protected java.util.Comparator<Key>	c A comparator of Key objects
protected Node<Key,Data>	root Root of the AVL tree.
protected int	size Number of items in the tree

Constructor Summary

AVLTree(java.util.Comparator<Key> comparator)
The constructor.

Method Summary

protected void	delete(Node<Key,Data> node) Removes a node from the tree.
void	deleteKey(Key k) Removes a node with the given key from the tree.
void	insert(Key key, Data data) Inserts a key and a data item into the tree, creating a new node for this key and data pair.
void	print() Prints the whole tree
Data	search(Key k) Searches the tree for a node with a given key.
protected Node<Key,Data>	search(Node<Key,Data> node, Key k) Searches the subtree rooted at a given node for a node with a given key.
int	size() The number of elements in the tree.
protected Node<Key,Data>	successor(Node<Key,Data> node) Returns the successor of a given node in an inorder walk of the tree.
protected void	treeInsert(Node<Key,Data> z) Inserts a node into the tree.
protected Node<Key,Data>	treeMinimum(Node<Key,Data> x) Returns the node with the minimum key in the subtree rooted at a node.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected Node<Key,Data> root

Root of the AVL tree.

size

protected int size

Number of items in the tree

c

protected java.util.Comparator<Key> c

A comparator of Key objects

Constructor Detail

AVLTree

public AVLTree(java.util.Comparator<Key> comparator)

The constructor. An empty binary search tree is created.

Parameters:

comparator - A comparator of Key objects.

Method Detail

size

public int size()

The number of elements in the tree.

Returns:

The number of elements in the tree.

search

public Data search(Key k)

Searches the tree for a node with a given key. If such a node exists, its key is returned.

Parameters:

k - The key being searched for.

Returns:

The data under the key An exception NoSuchElementException is thrown if no node exists.

search

protected Node<Key,Data> search(Node<Key,Data> node,
                                Key k)

Searches the subtree rooted at a given node for a node with a given key.

Parameters:

node - Root of the subtree.

k - The key being searched for.

Returns:

A reference to a Node object with key k if such a node exists. An exception NoSuchElementException is thrown if no node exists.

treeMinimum

protected Node<Key,Data> treeMinimum(Node<Key,Data> x)

Returns the node with the minimum key in the subtree rooted at a node.

Parameters:

x - Root of the subtree.

Returns:

A Node object with the minimum key in the tree, or the sentinel nil if the tree is empty.

successor

protected Node<Key,Data> successor(Node<Key,Data> node)

Returns the successor of a given node in an inorder walk of the tree.

Parameters:

node - The node whose successor is returned.

Returns:

If node has a successor, it is returned. Otherwise, return the sentinel null.

insert

public void insert(Key key,
                   Data data)

Inserts a key and a data item into the tree, creating a new node for this key and data pair. It increases the size by one

Parameters:

key - Key to be inserted into the tree.

data - Data to be inserted into the tree.

treeInsert

protected void treeInsert(Node<Key,Data> z)

Inserts a node into the tree. Does not alter size.

Parameters:

z - The node to insert.

deleteKey

public void deleteKey(Key k)

Removes a node with the given key from the tree. Decreases the size by one if the key is deleted sucessfully. A NoSuchElementException is thrown if the key does not exist.

Parameters:

k - The key to be removed.

delete

protected void delete(Node<Key,Data> node)

Removes a node from the tree. It does not alter the tree size.

Parameters:

node - The node to be removed. do nothing when deleting a null node null.

print

public void print()

Prints the whole tree