PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q6

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

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

Question

Create an AVL balanced tree for following sequence of elements:

Solution

AVL Tree Definition and Balance Factor: An AVL tree is a self-balancing binary search tree where the Balance Factor (BF) of every node is defined as:

When an insertion causes , balance is restored using one of four rotations:

Step-by-Step Insertions of 5, 18, 35, 65, 25:

  1. Insert 5: Tree is (5). Balanced ().
  2. Insert 18: (5) with right child (18). . Balanced.
  3. Insert 35: Inserted as right child of 18. (RR unbalance at node 5).
    • Perform RR (Single Left) rotation on node 5:
            18 (0)
           /  \
        5 (0)  35 (0)
  4. Insert 65: Inserted as right child of 35. . Balanced.
  5. Insert 25: Inserted as left child of 35. . Balanced.
            18
           /  \
          5    35
              /  \
             25   65

Insertions of 15 and 10:

  1. Insert 15: Inserted as right child of 5. . Balanced.
  2. Insert 10: Inserted as left child of 15.
    • Balance factors: , .
    • Node 5 is right-heavy (), and its right child 15 is left-heavy ().
    • This requires an RL rotation at node 5:
      • Right rotate on 15: 10 becomes parent of 15.
      • Left rotate on 5: 10 becomes parent of 5. All nodes currently have .
                18
               /  \
             10    35
            /  \  /  \
           5   15 25 65

Insertions of 12 and 14:

  1. Insert 12: Inserted as left child of 15. . Balanced.
  2. Insert 14: Inserted as right child of 12.
    • Balance factors: , .
    • Node 15 has with left child 12 having LR rotation at node 15:
      • Left rotate on 12: 14 becomes parent of 12.
      • Right rotate on 15: 14 becomes parent of 15. Subtree at 10 becomes: Entire tree is balanced (, ).
                10
               /  \
              5    14
                  /  \
                 12   15

Insertions of 3 and 2:

  1. Insert 3: Inserted as left child of 5. . Balanced.
  2. Insert 2: Inserted as left child of 3.
    • Balance factors: , .
    • Node 5 has and left child 3 has LL (Single Right) rotation at node 5:
      • Right rotate on 5: 3 becomes the parent of 2 (left) and 5 (right).
    • Subtree at 10 becomes:
              10
             /  \
            3    14
           / \  /  \
          2   5 12 15

Final Balanced AVL Tree Architecture: The final balanced tree containing all 11 keys:

                  18 (BF = +1)
                /             \
         10 (BF = 0)        35 (BF = 0)
        /          \        /         \
     3 (0)        14 (0)  25 (0)     65 (0)
    /    \        /    \
  2 (0)  5 (0)  12 (0) 15 (0)

Verification: In-order traversal yields the strictly sorted sequence:

Every node's balance factor is strictly within .

Answer:

The resulting AVL balanced tree has root 18:

Total height is 4, and every node satisfies .

All past exam questions for Data Structure and Algorithms