PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q10(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 tree from following sequence of data: 10, 20, 15, 25, 30, 16, 18, 19.

Solution

Insert 10, 20, 15 (RL Rotation at 10):

        15 (0)
       /      \
    10 (0)   20 (0)

Insert 25, 30 (RR Rotation at 20):

          15 (-1)
         /       \
      10 (0)     25 (0)
                /     \
             20 (0)   30 (0)

Insert 16 (RL Rotation at 15), 18, and 19 (RR Rotation at 16):

            20 (0)
          /        \
       15 (0)      25 (-1)
       /    \          \
    10 (0)  16 (0)     30 (0)
                 20 (+1)
               /         \
            15 (-1)       25 (-1)
            /     \           \
         10 (0)   18 (0)      30 (0)
                 /     \
              16 (0)   19 (0)
Answer:

The final AVL tree has root 20, left subtree 15 (left 10; right 18 with children 16, 19), and right subtree 25 (right 30).

All past exam questions for Data Structure and Algorithms