We are familiar with binary search tree , an efficient datastructure contain data as nodes. Avl tree is also binary search tree. What is difference between binary search tree and avl tree ? The answer is avl tree is self balanced , and it was first data structure which is self balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. In avl tree height of two child subtrees of any node differ by atmost one .The balance factor of a node is the height of left subtree minus height of right subtree and a node with balance factor 1,0,-1 considered as balanced. Below an avl tree with 9 nodes and each node have a balance factor of 1 ,-1 or 0.
When inserting a new node or deleting en existing node , the resulting tree will disturb the balance of tree. An unbalanced state is defind as a state in which any subtree have a balance factor greater than 1 or less than one . Tree rotations are necessary to retain the balanced state. A tree rotation move one node up and one node down in the tree.
Insertion
Every time inserting a node in tree ,it is necessary to check each of the nodes ancestors for consistency with the rules of avl. If the balance factor of each node remains -1,0 ,+1 then no rotations are necessary . In my program a function named balance(p) return the balance factor of the node p in the tree . The following code will check the balance condition.If a node in tree violate avl rule ,then rotation will necessary then we get a balanced tree.
There are four cases to be considered in which two are symmetric to the other two. Let p be the root and we can observe different cases.
Right right case and right left case
- If the balance factor of p is less than or equal to -2 then right subtree of p overweight the left subtree ,then balance factor of right child of p will be checked.
- If the balance factor of right child is -1 then single left rotation needed.
Left rotation can be done in following steps. Select a new node called pivot it will be the new root. Set right child of p as root and p takes the ownership of pivot’s left child , then p will be the left child of new root pivot.
Here a tree with 3 as root node and it is right heavy. Its balance factor is -2 so and balance factor of its right child is -1 then a single left rotation is takes place and the resulting tree must be balanced.
- If the balance factor of right child is +1 then two rotations are needed .Sometimes single rotation not sufficient to balance a unbalanced tree .Such cases two rotations necessory. First is right rotation with p’s right child as root and second is left rotation with p as root. After right rotations we get a unbalanced tree with right subtree left heavy .Then a left rotation is necessory to balance the tree. The tree below need two rotations ( double right rotations ) because balance factor of root’s right child is +1 ,after two rotation resulting tree will balanced.
- If the balance factor of left child is +1 ,a single right rotations is needed.
Right rotation is just opposite of left rotation. Here set p’s left child to pivot and it will be the new root . p takes ownership of the pivot’s right child as its left child . Pivot take ownership of p as its right child .The code as follows
- If the balance factor of p’s left child is -1 ,then two rotations are necessory , First is left rotation with p’s left child as root and second is right rotation with p as root . The following tree is left heavy with root as 5 and its left child is right heavy. So two rotations are needed to balance the tree.
neethutv 
