AVL TREE -The Self Balancing Binary Tree

        AVL Tree is a self balancing binary tree. When an insertion or deletion occurs, it re-balances the tree by checking the height of two child subtrees. Balancing factor of a node is equal to height of the left subtree minus height of the right subtree. If the balancing factor is equal to -1, 0 or 1 then the tree is considered balanced else the tree is rebalanced by calling one or more tree rotations. A simple example for AVL tree is given below.

          Insert a node with data 3 (node 3), which is inserted to the tree as a simple binary tree. Then insert node 2 which is inserted to the left of node 3. Here the function balance() is called  and height of the subtrees are checked. Since the height is not > 1 or < -1 tree rotations are not done here. next the node 1 is inserted. Now the tree becomes unbalanced and rotations are called.

        Now insert node 4 and 5. The balancing factor gives a difference of -2 that is right side the node is not balanced. So again a single rotation is applied.

        Inserting node 6 makes the balanced tree unbalanced. Here node 2 is unbalanced. So a single rotation is called which makes node 4 as the child of parent of node 2, if any element present in the left of node 4, then it is passed to the right child of node 2 and node 2 is passed to the left of node 4. Next node 7 is inserted. At this point the root is balanced. But when we go through each node checking whether it is balanced or not we found that the node 5 is not balanced and single rotation is applied here. Then inserting node 16 then node 15 which makes the tree again unbalanced.

 
        Now the tree is unbalanced and to become balanced we have to apply double rotation. First rotating child and grandchild of the unbalanced node 7 and then rotating the node 7and the new child (node 15) which makes the tree again balanced.

        Insert node 14 which comes to the right of node 7 and the tree becomes unbalanced at node 6. Again a double rotation is called, first rotation is with the child(node 7) and grandchild(node 15) of node 6. Then rotation is with node 6 and with the new child(node 7)

You can find my codes: http://github.com/omalbastin/avl_tree