PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q8

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 the set of data 10, 20, 30, 35, 50, 70, 40, 80, 60, 65 by explaining each rotation rules used.

Solution

Insert 10, 20, 30 (RR Rotation at 10) and 35, 50 (RR Rotation at 30):

           20 (-1)
          /       \
       10 (0)     35 (0)
                 /     \
              30 (0)   50 (0)

Insert 70 (RR Rotation at 20):

               35 (0)
             /        \
          20 (0)      50 (-1)
          /    \          \
       10 (0) 30 (0)      70 (0)

Insert 40, 80, 60 and 65 (RL Rotation at 50):

                  35 (-1)
                /         \
            20 (0)        60 (0)
            /    \        /     \
         10 (0) 30 (0)  50 (+1) 70 (0)
                        /       /    \
                     40 (0)   65 (0) 80 (0)
Answer:

Final AVL tree has root 35, left subtree 20 (children 10, 30), and right subtree 60 (left 50 with left 40; right 70 with children 65, 80).

All past exam questions for Data Structure and Algorithms