PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Describe an AVL tree. Construct AVL tree for following sequence of elements: 5, 10, 15, 30, 25, 20, 4, 2, 1

Solution

Description of AVL Tree: An AVL tree (Adelson-Velsky and Landis) is a self-balancing Binary Search Tree in which the balance factor of every node satisfies . When an insertion violates this invariant (), LL, RR, LR, or RL rotations restore height.

Insert 5, 10, 15 (RR Rotation at 5) and 30, 25 (RL Rotation at 15):

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

Insert 20 (RL Rotation at 10):

              15 (0)
            /        \
         10 (+1)     25 (0)
         /          /     \
       5 (0)     20 (0)   30 (0)

Insert 4, 2 (LL Rotation at 10) and 1 (LL Rotation at 4):

                  15 (+1)
                /         \
             5 (+1)       25 (0)
            /      \      /     \
         2 (0)    10 (0) 20 (0) 30 (0)
         /    \
       1 (0)  4 (0)
Answer:

An AVL tree maintains at every node via single/double rotations. The final AVL tree has root 15, left subtree 5 (left 2 with children 1, 4; right 10), and right subtree 25 (children 20, 30).

All past exam questions for Data Structure and Algorithms