AVL Tree (Height Balanced Binary Search Tree)

A Binary Search Tree (BST) is one of the most commonly used tree data structures for storing and searching data efficiently. In a BST, elements are arranged in such a way that searching, insertion, and deletion operations can be performed faster than linear data structures.

However, the efficiency of a Binary Search Tree depends on the height and structure of the tree. If the tree remains balanced, operations can be performed in O(log n) time. But in some situations, a BST can become completely unbalanced, causing its performance to degrade to O(n).

To overcome this problem, a special type of self-balancing Binary Search Tree called an AVL Tree was introduced.

An AVL Tree automatically maintains its height balance after insertion and deletion operations by performing rotations whenever required.

What is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree in which the difference between the heights of the left subtree and right subtree of every node is at most one.

The name AVL comes from the initials of its inventors:

• Adelson-Velsky
• Landis

AVL Tree was the first dynamically balanced binary search tree introduced in 1962.

An AVL Tree follows all the properties of a normal Binary Search Tree:

• Values smaller than a node are stored in its left subtree.
• Values greater than a node are stored in its right subtree.

In addition to BST properties, AVL Tree maintains an extra condition called the balance factor.

Why Do We Need AVL Trees?

To understand the need for AVL Trees, first consider the problem with normal Binary Search Trees.

A normal BST provides efficient operations when the tree is balanced.

Example of a balanced BST:

                 50
               /    \
             30      70
            /  \    /  \
          20   40 60   80

The height of this tree is small, so searching requires fewer comparisons.

For example, searching for 80:

50 → 70 → 80

Only three comparisons are required.

Time complexity: O(log n)

Problem with Normal Binary Search Tree

The problem occurs when elements are inserted in sorted order.

Consider inserting these values:

10, 20, 30, 40, 50

The resulting BST becomes:

10
 \
  20
    \
     30
       \
        40
          \
           50

This tree is called a skewed Binary Search Tree.

Although it is technically a BST, it behaves like a linked list.

Searching for 50 requires checking every node:

10 → 20 → 30 → 40 → 50

• Number of comparisons: 5
• For n nodes: Searching = O(n)

This removes the main advantage of using a BST.

Need for Self-Balancing Trees

To solve the problem of skewed BSTs, we need a tree structure that automatically maintains balance.

A self-balancing tree is a tree that automatically adjusts its structure after insertion and deletion operations to keep its height minimum.

The main objectives of a self-balancing tree are:

• Maintain small height
• Reduce searching time
• Improve insertion and deletion efficiency
• Avoid skewed tree formation

AVL Tree is one of the most popular self-balancing Binary Search Trees.

Example:

Instead of allowing:

10
 \
  20
    \
     30
       \
        40

AVL Tree performs rotations and converts it into:

          20
        /    \
      10      30
                 \
                  40

The height is reduced, and searching becomes faster.

Definition of AVL Tree

An AVL Tree can be defined as:

An AVL Tree is a height-balanced Binary Search Tree where the difference between the height of the left subtree and right subtree of every node is not more than one.

Mathematically:

Balance Factor = Height of Left Subtree - Height of Right Subtree

For every node:

Balance Factor = -1, 0, or +1

If the balance factor becomes:

Less than -1
or
Greater than +1

the tree becomes unbalanced and rotations are performed.

Properties of AVL Tree

An AVL Tree has the following properties:

1. It is a Binary Search Tree

AVL Tree follows all BST rules.

Example:

              50
            /    \
          30      70

Here: 30 < 50 < 70

2. Height Balanced

The difference between the heights of left and right subtrees is limited to one.

Example:

                 50
               /    \
             30      70

• Left subtree height: 1
• Right subtree height: 1
• Balance factor: 1 - 1 = 0
• The node is balanced.

3. Balance Factor is Maintained

Each node stores information about its balance.

Possible balance factors: +1, 0, -1

Example:

Left Heavy Tree

          50
         /
       30

• Height difference: 1 - 0 = +1
• Balanced.

Balanced Node

          50
        /    \
      30      70

• Balance factor: 1 - 1 = 0
• Balanced.

Right Heavy Tree

      50
        \
         70

• Balance factor: 0 - 1 = -1
• Balanced.

Balance Factor in AVL Tree

The balance factor is the key concept that makes AVL Tree different from a normal BST.

It tells whether a node is balanced or requires rotation.

Formula:

Balance Factor =
Height of Left Subtree - Height of Right Subtree

Example:

Consider:

              50
             /  \
           30    70

• Left subtree height: 1
• Right subtree height: 1

Therefore:

Balance Factor = 1 - 1

Balance Factor = 0

The node is balanced.

Example of Unbalanced AVL Node

Consider:

              50
             /
           30
          /
        20

• Height of left subtree: 2
• Height of right subtree: 0
• Balance factor: 2 - 0 = +2
• Since the balance factor is greater than +1, the tree is unbalanced.

AVL Tree performs rotation to fix it:

Before rotation:

              50
             /
           30
          /
        20

After right rotation:

             30
            /  \
          20    50

Now, Balance Factor = 0

The tree becomes balanced.

Rotations in AVL Tree

When an insertion or deletion operation is performed, the balance factor of some nodes may become invalid.

A node becomes unbalanced when:

Balance Factor > +1

or

Balance Factor < -1

To restore balance, AVL Tree performs a special operation called rotation.

A rotation changes the structure of the tree while maintaining the Binary Search Tree property.

The main purpose of rotation is:

• Reduce tree height
• Restore balance
• Maintain BST ordering

There are four types of rotations:

1. LL Rotation (Left Left Case)
2. RR Rotation (Right Right Case)
3. LR Rotation (Left Right Case)
4. RL Rotation (Right Left Case)

1. LL Rotation (Left Left Case)

When does LL Rotation occur?

LL rotation occurs when:

• A node becomes unbalanced.
• A new node is inserted into the left subtree of the left child.

In this situation, a right rotation is performed.

Example

Insert the following values:

30, 20, 10

Step 1: Insert 30

30

Step 2: Insert 20

20 is smaller than 30, so it goes to the left.

        30
       /
     20

Step 3: Insert 10

• 10 is smaller than 30.
• Move left.
• 10 is smaller than 20.
• Move left.

Final tree:

            30
           /
         20
        /
      10

Check Balance Factor

• For node 30:
• Left subtree height: 2
• Right subtree height: 0

Balance factor:

BF = 2 - 0

BF = +2

The node is unbalanced.

This is an LL case.

Apply Right Rotation

Before rotation:

            30
           /
         20
        /
      10

After right rotation:

             20
            /  \
          10    30

Now:

BF of every node = -1,0,+1

The AVL Tree becomes balanced.

2. RR Rotation (Right Right Case)

When does RR Rotation occur?

RR rotation occurs when:

• A node becomes unbalanced.
• A new node is inserted into the right subtree of the right child.

In this case, a left rotation is performed.

Example

Insert:

10, 20, 30

Step 1

Insert 10:

10

Step 2

Insert 20:

20 is greater than 10.

10
  \
   20

Step 3

Insert 30:

30 is greater than 10 and 20.

10
  \
   20
     \
      30

Balance Factor

For node 10:

Left height:

0

Right height:

2

Balance factor:

BF = 0 - 2

BF = -2

The node is unbalanced.

This is an RR case.

Apply Left Rotation

Before rotation:

        10
          \
           20
             \
              30

After left rotation:

             20
            /  \
          10    30

The AVL Tree becomes balanced.

3. LR Rotation (Left Right Case)

When does LR Rotation occur?

LR rotation occurs when:

• A node becomes unbalanced.
• The insertion happens in the right subtree of the left child.

LR rotation requires two rotations:

1. Left rotation
2. Right rotation

Example

Insert:

30, 10, 20

After inserting:

          30
         /
       10
         \
          20

Calculate balance factor of 30:

• Left height: 2
• Right height: 0
• Balance factor: +2
• The tree is unbalanced.
• Since the new node is in the right subtree of the left child:
• This is an LR case.

Step 1: Left Rotation

Rotate node 10:

Before:

        30
       /
     10
       \
        20

After left rotation:

          30
         /
       20
      /
    10

Step 2: Right Rotation

Rotate node 30:

Before:

          30
         /
       20
      /
    10

After right rotation:

          20
        /    \
      10      30

The tree becomes balanced.

4. RL Rotation (Right Left Case)

When does RL Rotation occur?

RL rotation occurs when:

• A node becomes unbalanced.
• The insertion happens in the left subtree of the right child.

RL rotation also requires two rotations:

1. Right rotation
2. Left rotation

Example

Insert:

10, 30, 20

After insertion:

        10
          \
           30
          /
        20

Balance factor of 10:

BF = -2

The tree is unbalanced.

This is an RL case.

Step 1: Right Rotation

Rotate node 30:

Before:

        10
          \
           30
          /
        20

After right rotation:

        10
          \
           20
             \
              30

Step 2: Left Rotation

Rotate node 10:

Before:

        10
          \
           20
             \
              30

After left rotation:

             20
            /  \
          10    30

The AVL Tree is balanced.

Summary of AVL Rotations

Creating a AVL Tree

Let’s now go step-by-step and clearly construct an AVL Tree using the data: 50, 40, 35, 58, 48, 60, 30, 33, 25

Step 1: Insert 50

• Tree is empty. Insert 50 as the root.

50

Step 2: Insert 40

• 40 < 50 → insert to the left of 50.

   50
  /
40

• Balance is okay (balance factor of 50 is +1). No rotation needed.

Step 3: Insert 35

• 35 < 50 → go left
• 35 < 40 → insert to left of 40

     50
    /
  40
  /
35

• Balance factor of 50 = +2 → Unbalanced
• Left-Left (LL) case → Right Rotation on 50
• After Rotation

    40
  /   \
35     50

Step 4: Insert 58

• 58 > 40 → go right
• 58 > 50 → insert to right of 50

   40
  /  \
35    50
        \
         58

• Balanced → No rotation needed.

Step 5: Insert 48

• 48 > 40 → go right
• 48 < 50 → insert to left of 50

    40
  /   \
35    50
     /   \
   48     58

• Balanced → No rotation needed.

Step 6: Insert 60

• 60 > 40 → go right
• 60 > 50 → go right
• 60 > 58 → insert to right of 58

    40
  /   \
35     50
     /   \
   48     58
            \
             60

• Balance factor of 20 = -2 → Unbalanced
• Right-Right (RR) case → Left Rotation on 40
• After Rotation

       50
      /  \
    40    58
   /  \     \
  35  48    60

Step 7: Insert 30

• 30 < 40 → go left
• 30 < 35 → insert to left of 35

	     50
        /  \
      40    58
     /  \     \
    35  48    60
   /
 30

• Balanced → No rotation needed.

Step 8: Insert 33

• 33 < 40 → left
• 33 < 35 → right of 30

	     50
        /  \
      40    58
     /  \     \
    35  48    60
   /
 30
   \          
    33

• Balance factor of 25 = 2 → Unbalanced
• Left-Right (LR) case → Left Rotation on 30 and Right Rotation on 35
• After Rotation

	     50
        /  \
      40    58
     /  \     \
    33  48    60
   /  \
 30    35

Step 9: Insert 25

• 25 < 40 → left
• 25 < 35 → left
• 25 < 30 → insert to left of 30

	      50
         /  \
       40    58
      /  \     \
     33  48    60
    /  \
  30    35
  /
 25 

Now, check balance of 40:

• Balance factor of 40 = 2 → Unbalanced
• Left-Left (LL) case → Right Rotation on 40
• After Rotation

          50
        /    \
      33       58
     /  \        \
   30    40       60
  /     /  \       
 25    35   48      

• Now all nodes have balance factor –1, 0, or +1.

Final AVL Tree:

          50
        /    \
      33       58
     /  \        \
   30    40       60
  /     /  \       
 25    35   48 

Deletions from an AVL Tree

Delete the node as in a binary search tree.

• Traverse up the tree from the deleted node checking the balance of each node.
• Make necessary adjustments to maintaining property of Binary Search Tree and balance factor.

Current AVL Tree (before deletion):

          50
        /    \
      33       58
     /  \        \
   30    40       60
  /     /  \       
 25    35   48 

Step 1: Delete 33

• Node 33 has two children → Replace it with inorder predecessor (largest node in left subtree) or inorder successor (smallest in right subtree).
• Let's choose inorder predecessor = 35
• Replace 33 with 35

          50
        /    \
      35       58
     /  \        \
   30    40       60
  /     /  \       
 25    33   48

• Remove 33 from its original position
• After Deletion of 33 tree became

          50
        /    \
      35       58
     /  \        \
   30    40       60
  /        \       
 25         48

Step 2: Check for Balance and Rotate if Needed

• Now all nodes have balance factor –1, 0, or +1.
• Balanced → No rotation needed.

          50
        /    \
      35       58
     /  \        \
   30    40       60
  /        \       
 25         48

Now the tree is balanced again (all balance factors are in –1, 0, +1).

Time and Space Complexity of AVL Tree

Time Complexity

Because AVL Trees are balanced Binary Search Trees, the height is always log(n) in the worst case.

Space Complexity

• Height is always O(log n), making all basic operations efficient.
• Insertion/Deletion might involve rotations, but those are done in constant time per node.
• AVL Trees are excellent for scenarios where search, insert, and delete all need to be fast and balanced.

Numerical Questions on AVL Tree

1. Insert the following nodes one by one into an empty AVL Tree: 45, 30, 60, 25, 40, 50, 70
   • Show the AVL Tree after each insertion.
   • Write the balance factor of each node at every step.
   • Indicate the rotation type when re-balancing is required.
2. Construct an AVL Tree by inserting numbers from 1 to 9.
3. Insert the following into an AVL Tree: 100, 90, 80
   • Identify and explain which rotation is required to balance the tree.
4. Start with AVL Tree built from: 50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48
   • Now delete 20 and
   • Show the updated AVL Tree
   • Show the affected sub-tree height changes
   • Show the rotations needed (if any)
   • Perform Preorder, Inorder and Postorder Traversal
5. Insert the values: 21, 26, 30, 9, 4, 14, 28, 18,15,10, 2, 3, 7
   • After all insertions, draw the final AVL Tree.
   • Annotate with balance factors and height of each node.
6. Given the same input sequence: 10, 20, 30, 40, 50, 60, 70
   • Construct a regular Binary Search Tree (BST).
   • Construct an AVL Tree.
   • Compare the height of both trees.
   • Discuss why AVL Tree is more efficient for search.