Class AATree<T extends java.lang.Comparable<? super T>>

java.lang.Object

AATree<T>

public class AATree<T extends java.lang.Comparable<? super T>>
extends java.lang.Object

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	AATree.BinaryNode

Field Summary

Fields

Modifier and Type	Field and Description
AATree.BinaryNode	root
int	rotationCount

Constructor Summary

Constructors

Constructor and Description
AATree() Constructor for an empty tree.

Method Summary

Modifier and Type	Method and Description
void	find(T e)
int	getRotationCount()
int	height()
boolean	insert(T element) This is the only method that enables the user to add elements to the AA tree.
boolean	remove(T element) This method enables a user to remove an element from the AA tree.
void	resetRotationCount()
int	size() The method returns the number of nodes in the tree.
java.lang.Object[]	toArray() This method returns an array containing all nodes in the tree.
java.util.ArrayList<java.lang.Object>	toArrayList() This method returns an ArrayList containing all nodes in the tree.
java.lang.String	toString() This method produces a string representation of all elements in the tree.

Methods inherited from class java.lang.Object

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

Field Detail

root

public AATree.BinaryNode root

rotationCount

public int rotationCount

Constructor Detail

AATree

public AATree()

Constructor for an empty tree. This is the only constructor

Method Detail

getRotationCount

public int getRotationCount()

resetRotationCount

public void resetRotationCount()

find

public void find(T e)

insert

public boolean insert(T element)

This is the only method that enables the user to add elements to the AA tree. It preserves the ordering as specified for trees. This method runs in log time. The method throws an IllegalArgumentException if null is passed to it.

Parameters:

element - The only parameter is the element to be added to the tree. It has to be of the parameterized type Comparable that was used to create the tree.

Returns:

This method returns true if the element was successfully added and false otherwise.

remove

public boolean remove(T element)

This method enables a user to remove an element from the AA tree. It preserves the ordering as specified for trees. This method runs in log time. The method throws an IllegalArgumentException if null is passed to it. If a node to be removed has two children, then the value of the node is replaced by the value of the largest node in the left subtree.

Parameters:

element - The only parameter is the element to be added to the tree. It has to be of the parameterized type Comparable that was used to create the tree.

Returns:

This method returns true if the element was successfully removed and false otherwise.

toString

public java.lang.String toString()

This method produces a string representation of all elements in the tree. It returns the elements in pre-order, grouping the node and its children into one bracket and adding the level of the node after the brackets. Each node is separated by newline.

Overrides:

toString in class java.lang.Object

Returns:

The method returns the string.

height

public int height()

size

public int size()

The method returns the number of nodes in the tree.

Returns:

Returns the number of nodes in the tree.

toArray

public java.lang.Object[] toArray()

This method returns an array containing all nodes in the tree. The nodes are in the array in PRE-order.

Returns:

The method returns an array of BinaryNodes.

toArrayList

public java.util.ArrayList<java.lang.Object> toArrayList()

This method returns an ArrayList containing all nodes in the tree. The nodes are in the list are in PRE-order.

Returns:

The method returns an ArrayList of BinaryNodes.