AVL Trees

The biggest challenge in BST is,

What if the binary search tree insert element comes in a sorted (Ascending or Descending) manner? 

It looks like below:

From the above figure, it is observed that, BST’s worst case performance is similar to linear search algorithms which is O(n). In real time, we cannot predict the incoming of data; it may be of any order. To optimize the search operation in BST, we need to balance out the existing BST.

The AVL trees are named after their inventors, Adelson, Velski & Landis. The AVL trees are height balancing binary search tree. AVL trees checks the height of the left and right subtrees, and assures that the difference is not more than 1. This difference is called the Balance Factor.

The following first tree is balanced and the other two trees are not balanced.

In the above example, the first tree is a balanced tree. The height difference between the left and right subtree is 0. The second tree is a not balanced tree, the left subtree of C has height 2, the right subtree of C has height 0 and the difference between the left and right subtree is 2. AVL tree permits difference (balance factor) to be only 1. The third tree also has difference of 2.

Balance Factor = height (left subtree) – height (right subtree)

If the difference in the height of left and right subtrees is more than 1, the tree is balanced using the rotating techniques.

AVL Rotations

To balance an unbalanced tree, we follow the four basic rotation rules such as:

• Left Rotation
• Right Rotation
• Left-Right rotation
• Right-Left rotation

• The above first two rotation are single rotation and the next two rotations are double rotation. The unbalanced tree atleast have a balance factor of 2. With simple tree example, lets understand the above rotations one by one.

  Left Rotation

  If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform single left rotation as shown below:

                                  

  In the above example, the node A is unbalanced as the right subtree is loaded. To make this above tree balanced, we have to perform left rotation by making A the left subtree of B.

  Right Rotation

  If a tree becomes unbalanced, when a node is inserted into the left subtree of the left subtree, then we perform single right rotation as shown below:

                          

  In the above example, the node C is unbalanced as the left subtree is loaded. To make the above tree balanced, we have to perform right rotation by making C as the right subtree of B.

  Left-Right Rotation

  Double rotations are slightly complex version of already explained versions of rotations. To understand this better, we need to perform certain action while rotation. In left-right rotation, we perform left rotation and followed by right rotation.

                                  
  

  From the above figure,

  1. A node has been inserted to the right subtree of the left subtree. This makes C an unbalanced node which has the balance factor of 2. This scenario cause to perform left-right rotation.
  2. We first perform left rotation on the left subtree of C. This makes the B left subtree of C and A as the left subtree of B.
  3. Node C is still unbalanced as it still holds the balance factor of 2. 
  4. We shall now perform right rotation, making B as the new root node and C be the right subtree of B, and A remains the left subtree of B.
  5. Finally, the tree looks balanced now with the balance factor of 0.

Right-Left rotation

The second type of double rotation is Right-Left rotation. It is a right rotation followed by left rotation.

From the above figure,

1. A node B has been inserted to the left subtree of right subtree C. This makes a root node A unbalanced with the balance factor 2.
2. We first perform right rotation along C node, making C the right subtree of B and B which is the right subtree of A.
3. The tree is still unbalanced as the root node A has the balance factor 2.
4. A left rotation is performed on the right subtree B and B has become the root node with the left subtree A and the right subtree C.
5. The tree is now balanced with the balance factor 0.

Time Complexity in AVL trees

Most of the BST operations such as insertion, search, delete, max , min, etc take O(h) time where h is the height of the BST. In the worst case, the skewed trees takes O(n) time complexity. If we make sure that the height of the tree remains O(Log n) after every insertion and deletion, then it is sure that an upper bound of O(Log n) for all these operations. The height of the AVL tree is always O(Log n) where n is the number of nodes in the tree.