AVL Tree

An AVL tree is a special type of binary tree that is always partially balanced. The criteria that is used to determine the level of balanced-ness is the difference between the heights of subtrees of a root in the tree. The height of tree is the number of levels in the tree. Or to be more formal, the height of a tree is defined as follows:

1. The height of a tree with no elements is 0
2. The height of a tree with 1 element is 1
3. The height of a tree with > 1 element is equal to 1 + the height of its tallest subtree.

Height of a node

• The height of a leaf is 1. The height of a null pointer is zero.
• The height of an internal node is the maximum height of its children plus 1

 AVL trees are height-balanced binary search trees

Balance factor of a node

height(left subtree) - height(right subtree)

An AVL tree has balance factor calculated at every node

For every node, heights of left and right subtree can differ by no more than 1

Store current heights in each node

Animated AVL Tree

http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

Notes on AVL Trees

http://pages.cs.wisc.edu/~siff/CS367/Notes/AVLs/

AVL Tree Rotations Tutorial

http://fortheloot.com/public/AVLTreeTutorial.rtf

AVL Tree C Program

http://www.freecprograms.com/AVL.htm

---------------------------------------------------------------------------------------