Past exam question: 2077 Chaitra (Regular), Q6
Open in the Padhaiko appQuestion
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):
- Insert
5, 10, 15: RR (Left) Rotation at5: root10, children5, 15. - Insert
30, 25:30right of15,25left of30.- RL Rotation at
15(right-rotate30, left-rotate15):
- RL Rotation at
10 (-1)
/ \
5 (0) 25 (0)
/ \
15 (0) 30 (0)Insert 20 (RL Rotation at 10):
- Insert
20: right child of15.- , , .
- Node
10has and right child25has RL Rotation at10:- Right-rotate
25:15moves up,20becomes left child of25. - Left-rotate
10:15becomes new root!
- Right-rotate
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):
- Insert
4: left child of5. LL (Right) Rotation at10:5replaces10, with4left and10right. - Insert
2: left child of4. . - Insert
1: left child of2. LL (Right) Rotation at4:2becomes parent of1and4.
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).