AVL Tree (Balanced Tree)

An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference in heights between the left and right sub-trees (called the Balance Factor) of any node is at most 1.

It is named after its inventors Adelson-Velsky and Landis.

Balance factor = Height of left sub tree - Height of right sub tree

Terminology

• Height of Node: Number of edges on the longest path from that node to a leaf.
• Balance Factor: Height difference of left and right child (BF = hl - hr)
• Rotations: Operations used to re-balance the tree (explained below).

AVL Tree Properties

• Follows all rules of BST (Left < Root < Right).
• Automatically balances itself after insertion or deletion.
• For any node Balance Factor = height(left subtree) - height(right subtree)
• Valid balance factors: –1, 0, +1

Example:

AVL Tree Operations

1. Insertion

In AVL Tree, insertion follows the same logic as Binary Search Tree (BST). A new node is added in the correct position based on its value.

After inserting the node, we check the balance factor of each ancestor node from bottom to top.

If any node becomes unbalanced (balance factor becomes less than –1 or more than +1), we restore the balance by applying appropriate rotation.

Steps for Insertion:

• Insert the node as in BST.
• Traverse upward and update the height of ancestors.
• Check balance factor for each node.
• Apply rotation (LL, RR, LR, RL) to restore balance if necessary.

2. Deletion

Deletion in an AVL Tree also begins like BST deletion. Once a node is deleted (depending on whether it’s a leaf, has one child, or two children), we need to check and fix balance starting from the node’s parent up to the root.

The re-balancing may require one or more rotations to maintain AVL properties.

Steps for Deletion:

• Perform standard BST deletion.
• Traverse back up and update the heights of affected nodes.
• Check balance factor after deletion.
• Apply suitable rotations (if balance factor becomes < –1 or > +1).

3. Searching

Searching in AVL Tree is identical to a regular BST. It starts from the root and moves left or right depending on the value being searched.

AVL Tree guarantees balanced height, so search operations remain efficient.

Steps for Searching:

• Compare the target value with the current node.
• If equal, return the node.
• If smaller, move to the left sub-tree.
• If larger, move to the right sub-tree.
• Repeat until the value is found or NULL is reached.

AVL Rotations

AVL Tree uses four types of rotations to restore balance when the tree becomes unbalanced after insertion or deletion.

The choice of rotation depends on where the imbalance occurs and the structure of the sub-tree.

1. Left to Left Rotation
2. Right to Right Rotation
3. Left to Right Rotation
4. Right to Left Rotation

1. Left Left (LL) Rotation

This rotation is used when a node is inserted into the left sub-tree of the left child, causing an imbalance. A single right rotation is performed to restore balance.

When to apply:

• Balance factor of a node becomes +2, and
• Balance factor of its left child is +1 or 0.

Steps:

• Make the left child the new root of the sub-tree.
• Move the original root to the right of the new root.

Example before rotation:

    z
   /
  y
 /
x

After LL Rotation:

  y
 / \
x   z

2. Right-Right (RR) Rotation

This is the mirror of LL Rotation. It is used when a node is inserted into the right sub-tree of the right child, making the tree unbalanced. A single left rotation is used.

When to apply:

• Balance factor becomes –2, and
• Balance factor of right child is –1 or 0.

Steps:

• Make the right child the new root of the sub-tree.
• Move the original root to the left of the new root.

Example: Before Rotation

  z
   \
    y
     \
      x

After RR Rotation

     y
   /   \
  z     x

3. Left-Right (LR) Rotation

This rotation is applied when a node is inserted into the right sub-tree of the left child, causing imbalance.

It requires two rotations, first a left rotation on the left child, then a right rotation on the node.

When to apply:

• Balance factor becomes +2, and
• Left child has balance factor –1.

Steps:

• Perform a left rotation on the left child.
• Perform a right rotation on the node.

Example: Before Rotation

     z
   /
  x
   \
     y

After LR Rotation

     y
   /   \
  x     z

4. Right-Left (RL) Rotation

Used when a node is inserted into the left sub-tree of the right child.

This rotation also involves two steps: first a right rotation on the right child, then a left rotation on the node.

When to apply:

• Balance factor becomes –2, and
• Right child has balance factor +1.

Steps:

• Perform a right rotation on the right child.
• Perform a left rotation on the node.

Example: Before Rotation

  z
   \
    x
   /
  y

After RL Rotation

     y
   /   \
  z     x

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.