AVL Tree

an AVL tree is a self-balancing binary search tree.
Lookup, insertion, and deletion all take O(log n).
The balance factor of a node is the height of its left subtree minus the height of its right subtree.
A node with balance factor 1, 0, or −1 is considered balanced.

a. Right rotation:

                  -2                             -1
                  80                             80
              /        \                     /        \
           -2            -1                0            -1
           30            100              15            100
         /   \         /                 /   \         /
       -1     0       0                -1     0       0
       15     40     90      ==>       10     30     90 
      /  \                            /      /  \
    -1    0                          0      0    0
    10    20                         5     20    40
   /                        
  0                         
  5                         

b. Double Rotation:

i. Left Rotaion at 30:

               -2                               -2
               80                               80
           /        \                       /        \
        +1             0                 -1             0
        30            100                50            100
      /   \         /     \            /   \         /     \
    -1     +1      0       0        -1      -1      0       0
    20     50     90      120       30      60     90      120
   /      /  \                     /  \    /
  0      0    -1                  -1   0  0 
 10     40    60                  20  40  55 
             /                   /          
            0                   0
            55                  10

ii. Right Rotation at 80:

                -2                            0
                80                           50
            /        \                   /        \
         -1             0             -1             0
         50            100            30            80 
       /   \         /     \        /   \         /     \
    -1      -1      0       0     -1     0      -1       0
    30      60     90      120    20     40     60      100
   /  \    /                     /             /       /   \
  -1   0  0                     0             0       0     0
  20  40  55                   10             55      90   120
 /
0
10

ALV Implemention File - avltree.c
AVL Tree Header File - avltree.h
Macro for Fatal Error - fatal.h
Test Program for AVL Tree - testavl.c
Makefile - Makefile

Reference:
www.cs.virginia.edu/~cs216/Fall2005/notes/avl_handout.pdf
http://cis.stvincent.edu/carlsond/swdesign/avltrees/avltrees.html
http://www.cs.uiuc.edu/class/fa05/cs400/_resources/_practice/avlsoln.html
http://cprogramminglanguage.net/avl-tree.aspx