PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q6(b)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

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

Question

Construct an AVL balanced tree with given set of data: 15, 20, 24, 10, 13, 7, 30, 36, 25

Solution

Insert 15, 20, 24 (RR Rotation at 15): Balance factor is .

       20 (0)
      /      \
   15 (0)   24 (0)

Insert 10 and 13 (LR Rotation at 15):

         20 (+1)
        /      \
     13 (0)   24 (0)
     /    \
  10 (0)  15 (0)

Insert 7 (LL Rotation at 20):

            13 (0)
          /        \
       10 (+1)     20 (0)
       /          /      \
     7 (0)     15 (0)   24 (0)

Insert 30, 36 (RR Rotation at 24) and 25 (RL Rotation at 20):

                 13 (-1)
               /         \
           10 (+1)        24 (0)
           /             /      \
         7 (0)       20 (+1)    30 (0)
                     /          /    \
                  15 (0)     25 (0) 36 (0)
Answer:

The final balanced AVL tree has root 13, left subtree 10 (left child 7), and right subtree 24 (left child 20 with left child 15; right child 30 with children 25 and 36). In-order traversal: 7, 10, 13, 15, 20, 24, 25, 30, 36.

All past exam questions for Data Structure and Algorithms