Past exam question: 2066 Jestha (Back), Q5
Open in the Padhaiko appQuestion
Define AVL balance tree and create AVL tree using AVL balancing algorithm for given sequence of data 3, 15, 21, 2, 7, 5, 13, 10, 8, 4, 19, 24, 1. Show inorder traversal of tree after each rotation clearly.
Solution
Definition of AVL Tree: An AVL tree is a self-balancing Binary Search Tree in which every node's balance factor lies in , maintained via LL, RR, LR, and RL rotations.
Insert 3, 15, 21 (RR Rotation at 3) and 2, 7, 5 (LR Rotation at 15):
- Insert
3, 15, 21: RR Rotation at3.- Tree: root
15(left3, right21). Inorder:3, 15, 21.
- Tree: root
- Insert
2(left of3),7(right of3),5(left of7):- Wait: check
5insertion: , and at15: left height 3 (15->3->7->5), right height 1 (21) , while left child3has ! - Apply LR Rotation at
15(left-rotate3around7, right-rotate15around7):7becomes root! - Tree:
7(left3with left2, right5; right15with right21). - Inorder after LR rotation:
2, 3, 5, 7, 15, 21.
- Wait: check
Insert 13, 10, 8 (LL Rotation at 13) and 4, 19, 24, 1:
- Insert
13(left of15),10(left of13): wait — on inserting10? At13: . Balanced! - Insert
8(left of10): LL (Single Right) Rotation at13:10becomes left child of15with children8and13.- Inorder after LL rotation:
2, 3, 5, 7, 8, 10, 13, 15, 21.
- Inorder after LL rotation:
- Insert
4(left of5),19(left of21),24(right of21),1(left of2):- All balance factors stay within (no further rotations needed).
7 (0)
/ \
3 (0) 15 (0)
/ \ / \
2 (+1) 5 (+1) 10 (0) 21 (0)
/ / / \ / \
1 (0) 4 (0) 8 (0) 13(0) 19(0) 24(0)Answer:
Final AVL tree has root 7, left subtree 3 (2->1, 5->4), and right subtree 15 (10->{8, 13}, 21->{19, 24}). Final inorder traversal: 1, 2, 3, 4, 5, 7, 8, 10, 13, 15, 19, 21, 24.