AVL Tree

By | January 5, 2020
AVL Tree

AVL tree stands for Adelson-Velsky and Landis Tree and it is a self-balancing Binary Search tree. AVL tree is the extension of Binary Search tree Data Structure. It reduces the time complexity of the many operations of Binary Search Tree.

The name of this tree Data Structure AVL is named after its inventor Adelson-Velsky and Landis and they publish this algorithm in 1962.

Vamware

In a Binary Search tree, the searching and inserting can have the complexity of O(n) where n represent the number of nodes, but with AVL tree we can do it with a time complexity of O(log n) which make the AVL more efficient and faster than Binary Search Tree.

AS we said the ALV tree is a Self-Balancing Tree what does it mean? Self-Balancing is a property that helps the tree to form a balanced tree, and a tree would be considered as a balanced tree if the difference of its right subtree and left subtree is between -1 to 1. The height difference of two subtrees is also known as the Balance Factor.

With every Insertion and Deletion operation, the AVL tree performs the self-balancing property which makes the tree structure into a balanced tree.

As AVL tree is an extension of Binary search Tree so it satisfies the Binary Search Tree Properties, which are the key value of the left child should be smaller than Parent and the key value of the Right Child should be greater than the parent.

Self-balancing AVL tree Vs Binary Search Tree

AVL Tree Binary Search Tree
Insert Root Node 10
               10
              /  \
             /    \
               10
              /  \
             /    \
Insert 30
                10
               /  \
              /    \
                    30
               10
              /  \
             /    \
                   30
Insert 40
    10
      \
       \
        30 
          \
           40

Self-balance by rotation, because the height of the right child is 2 and the height of the left child is 0 so the difference is not in between -1 to 1.

            30 
           /   \
          /     \
         10     40
     10
       \
        \
         30 
          \
           40

Balancing Factor

Balancing Factor determine whether the tree is balanced or not If the balancing factor value in between -1 to 1 then the tree would be considered as a balanced tree or else it considered as an unbalanced tree.

If after the insertion or deletion in AVL tree the Balancing Factor becomes more than 1 or less than 1, so the algorithm for self-balancing balance the tree.

A balancing factor shows the difference between the height of the left subtree and the right sub-tree.

Balance Factor = height(Right Sub-Tree) – height(left sub-tree).

Balance Factor Values Description
Balance Factor <= -1 It means the height of left subtree is larger than right subtree
Balancing Factor == 0 The height of the left subtree is equal to the height of right subtree
Balancing Factor >=1 The right subtree height is larger than the left subtree.

Complexities

AVL reduce the time complexity of BST for Search, Insert and Delete operations.

Algorithm Average case Worst case
Space o(n) o(n)
Search o(log n) o(log n)
Insert o(log n) o(log n)
Delete o(log n) o(log n)

AVL tree Rotation

In AVL after insertion and Deletion operation, we check for balance factor if the balance factor in between -1 to 1 then we leave the tree, if not we have to balance the tree. To balance the tree we need to rotate the nodes positioning after the insertion and deletion operation so the tree remains balance.

We move the nodes either left or right in order to make the tree balance, in AVL we have a total of four types of rotation which are classified into two types:

  • Single Rotation
  • Double Rotation

Types of Single Rotation

  • Left Rotation
  • Right Rotation

Types of Double Rotation

  • Left-Right Rotation
  • Right-Left Rotation 

Single Left Rotation

In Left rotation, each node move position to its left from the current position

     10                           20
       \                         /  \
        20      ---->          10    30
          \
           30

Single Right Rotation:

In this rotation, each node moves to its right from the current position.

          30                           
        /
      20     ------------>                  20
     /                                    /    \
   10                                   10      30

Double: Left Right Rotation

In this, we first rotate the node left then right to the current position.

       30                        30
      /                         /
    10              ---->     20   -------->    20
      \                      /                 /  \
       20                  10                10    30

Double: Right Left Rotation

In this rotation, the node moves to right then follow by left rotation.

       10                                  1
         \                                  \
          30   --------->                    2    ----------------->   20
         /                                    \                       /   \ 
       20                                      3                    10     30

You may be also interested in:

Leave a Reply

Your email address will not be published. Required fields are marked *