PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q6(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

Insert the following sequence of data into an AVL tree. 89, 35, 15, 87, 67, 76, 37, 14, 22, 25

Solution

Insert 89, 35, 15 (LL Rotation at 89) and 87, 67 (LL Rotation at 89):

           35 (-1)
          /       \
       15 (0)     87 (0)
                 /     \
              67 (0)   89 (0)

Insert 76 (RL Rotation at 35), 37, 14, 22, and 25 (LR Rotation at 35):

              67 (0)
            /        \
         35 (0)      87 (0)
         /    \      /    \
      15 (0) 37?  ... (Wait: 35 gets right=NULL, wait no: 67's left child NULL goes to 35's right!)

Actually: 67 had no left child, so 35 has left 15, right NULL; 67 had right 76, which becomes left child of 87!

                  67 (+1)
                /         \
            22 (0)        87 (0)
            /    \        /     \
        15 (+1)  35 (0) 76 (0)  89 (0)
        /        /    \
     14 (0)   25 (0)  37 (0)
Answer:

Final AVL tree has root 67, left subtree 22 (left 15 with left 14; right 35 with children 25, 37), and right subtree 87 (children 76, 89).

All past exam questions for Data Structure and Algorithms