Class AVLTree<T extends Comparable<? super T>>

java.lang.Object

com.thomas.trees.BinarySearchTree<T>

com.thomas.trees.AVLTree<T>

Type Parameters:

T - The type of the Node

public class AVLTree<T extends Comparable<? super T>>
extends BinarySearchTree<T>

A simple implenation of a AVL Tree

See Also:

• BinarySearchTree
• AVLNode

Constructor Summary

Constructors

Constructor	Description
AVLTree()	Initializes an Empty AVL
AVLTree(AVLNode<T> node)	Initializes an AVL with a root node

Method Summary

Modifier and Type	Method	Description
AVLNode<T>	balance(AVLNode<T> node)	Balances the node such that the balance factor is -1, 0, or 1
int	balanceFactor(AVLNode<T> node)	Calculates the balance factor of the node
AVLNode<T>	delete(AVLNode<T> node, T value)	Deletes a value from a subtree
void	delete(T value)	Deletes a value from the tree
AVLNode<T>	findMin(AVLNode<T> node)	Finds the minimum node in the tree
void	fixHeight(AVLNode<T> node)	Fixes the height of a node
int	height(AVLNode<T> node)	Gets the height of a node
AVLNode<T>	insert(AVLNode<T> node, T value)	Inserts a new value into a subtree
void	insert(T value)	Inserts a new value into the Tree
AVLNode<T>	rotateLeft(AVLNode<T> node)	Rotates the node left
AVLNode<T>	rotateRight(AVLNode<T> node)	Rotates the node right

Methods inherited from class BinarySearchTree

delete, find, find, findMin, getHeight, getRoot, getSize, in_order, in_order, insert, level_order, level_order, post_order, post_order, pre_order, pre_order, recursiveHeight, recursiveSize, removeMin, setRoot

Methods inherited from class Object

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

Constructor Details

AVLTree

public AVLTree()

Initializes an Empty AVL

AVLTree

public AVLTree(AVLNode<T> node)

Initializes an AVL with a root node

Parameters:

node - The root node

Method Details

balanceFactor

public int balanceFactor(AVLNode<T> node)

Calculates the balance factor of the node

Parameters:

node - The node

Returns:

The balance factor

height

public int height(AVLNode<T> node)

Gets the height of a node

Parameters:

node - The node

Returns:

The height

fixHeight

public void fixHeight(AVLNode<T> node)

Fixes the height of a node

Parameters:

node - The node that needs its height fixed

findMin

public AVLNode<T> findMin(AVLNode<T> node)

Finds the minimum node in the tree

Parameters:

node - The subtree being inspected

Returns:

The minimum node

rotateRight

public AVLNode<T> rotateRight(AVLNode<T> node)

Rotates the node right

Parameters:

node - The node to be rotated

Returns:

The rotated node

rotateLeft

public AVLNode<T> rotateLeft(AVLNode<T> node)

Rotates the node left

Parameters:

node - The node that needs to be rotated

Returns:

The rotated node

balance

public AVLNode<T> balance(AVLNode<T> node)

Balances the node such that the balance factor is -1, 0, or 1

Parameters:

node - The node being balanced

Returns:

A balanced Node

See Also:

• balanceFactor(AVLNode)
• rotateLeft(AVLNode)
• rotateRight(AVLNode)

insert

public void insert(T value)

Inserts a new value into the Tree

Overrides:

insert in class BinarySearchTree<T extends Comparable<? super T>>

Parameters:

value - The new data

See Also:

• BinarySearchTree.insert(BTNode, Comparable)

insert

public AVLNode<T> insert(AVLNode<T> node,
 T value)

Inserts a new value into a subtree

Parameters:

node - The current node

value - The new data

Returns:

A balanced Tree

delete

public void delete(T value)

Deletes a value from the tree

Overrides:

delete in class BinarySearchTree<T extends Comparable<? super T>>

Parameters:

value - The value to be deleted

See Also:

• BinarySearchTree.delete(BTNode, Comparable)

delete

public AVLNode<T> delete(AVLNode<T> node,
 T value)

Deletes a value from a subtree

Parameters:

node - The current node

value - The calue to be deleted

Returns:

A balanced subtree