PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q7

Data Structure and Algorithms · 12 marks

Open in the Padhaiko app

Topic: Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Question

Discuss about AVL rotations with suitable examples. Create a AVL balanced tree for data sequence 10 20 30 50 45 40 8 5 3.

Solution

Four AVL Tree Rotations with Examples: When an insertion makes , balance is restored by one of four rotations:

  1. LL Rotation (Single Right): Imbalance , left child (e.g., insert 30, 20, 10 right-rotate 30 root 20).
  2. RR Rotation (Single Left): Imbalance , right child (e.g., insert 10, 20, 30 left-rotate 10 root 20).
  3. LR Rotation (Double Left-Right): Imbalance , left child (e.g., insert 30, 10, 20 left-rotate 10, then right-rotate 30 root 20).
  4. RL Rotation (Double Right-Left): Imbalance , right child (e.g., insert 10, 30, 20 right-rotate 30, then left-rotate 10 root 20).

AVL Construction — Insert 10, 20, 30 (RR) and 50, 45 (RL):

Insert 40 (RL at 20), 8, 5 (LL at 20), and 3 (LL at 8):

             30 (0)
           /        \
        20 (+1)     45 (0)
        /          /     \
     10 (0)     40 (0)   50 (0)
                  30 (+1)
                /         \
            10 (+1)       45 (0)
            /     \       /     \
          5 (0)   20(0) 40(0)  50(0)
         /    \
       3 (0)  8 (0)
Answer:

All past exam questions for Data Structure and Algorithms