PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q8(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

Construct an AVL tree for following data: 36, 12, 42, 23, 65, 96, 37, 79, 19, 24, 33 and 44.

Solution

Insert 36, 12, 42, 23, 65, 96 (RR Rotation at 42):

           36 (0)
          /      \
       12 (-1)   65 (0)
          \      /    \
         23 (0) 42 (0) 96 (0)

Insert 37, 79, 19 (RL Rotation at 12):

                 36 (-1)
               /         \
           19 (0)        65 (0)
           /    \        /     \
        12 (0) 23 (0)  42 (+1) 96 (+1)
                       /       /
                     37 (0)  79 (0)

Insert 24, 33 (RR Rotation at 23) and 44:

                    36 (0)
                 /          \
            19 (-1)          65 (0)
            /     \          /     \
         12 (0)  24 (0)   42 (0)   96 (+1)
                 /   \    /   \    /
               23(0) 33(0) 37(0) 44(0) 79(0)
Answer:

Final AVL tree has root 36, left subtree 19 (left 12, right 24 with children 23, 33), and right subtree 65 (left 42 with children 37, 44; right 96 with left child 79).

All past exam questions for Data Structure and Algorithms