Explain how to balance AVL Tree?

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1.

 

The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N)) // BalanceFactor(N) belongs to the set {-1,0,1}

If the balance factor of a tree doesn’t equal -1,0, or 1 then our tree is unbalanced:

BalanceFactor = height(left_sutree) − height(right_sutree) // BalanceFactor not in {-1,0,1} => UNBALANCED

and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations:

• Single Rotations:
• Left Left Rotation

• Right-Right Rotation,

• Double Rotation:
• Left Right Rotation or Double Left,

• Right Left Rotation or Double Right.

 

Now, we say that a sub-tree is:

• left-heavy if the balance factor is greater than zero (> 0)
• right-heavy if the balance factor is lesser than zero (< 0)

How we determine which rotation to use follows a few basic rules. See psuedo code:

IF tree is left heavy {    IF tree 's left subtree is right heavy {        Perform Double Right rotation/*  c                b /                / \a     == 2R ==>  a   c \  b*/    }    ELSE { // Left Left case        Perform Single Right rotation/*    c               b   /               / \  b   == 1R ==>   a   c /a */    }}IF tree is right heavy {    IF tree 's right subtree is left heavy {        Perform Double Left rotation/*a                  b \                / \  c   == 2L ==>  a   c /b*/    }    ELSE { // Right Right Case        Perform Single Left rotation/*a                   b \                 / \  b   == 1L ==>   a   c   \    c*/    }}