Past exam question: 2062 Baishakh (Regular / Back), Q5
Open in the Padhaiko appQuestion
Define B-tree. Create AVL tree using AVL balancing algorithm for the given sequence of data. 14, 12, 8, 18, 20, 23, 44, 52. Show the steps of balancing clearly.
Solution
Definition of B-Tree: A B-Tree of order is a self-balancing multi-way search tree in which every node has at most children and sorted keys, every internal node (except root) has at least children, the root has at least 2 children (unless a leaf), and all leaves appear at the exact same level.
AVL Construction — 14, 12, 8 (LL Rotation) and 18, 20 (RR Rotation):
- Insert
14, 12, 8: LL (Right) Rotation at14:12becomes root (8, 14). - Insert
18, 20: right of14, then right of18. RR (Left) Rotation at14:18replaces14with children14, 20.
12 (-1)
/ \
8 (0) 18 (0)
/ \
14 (0) 20 (0)Insert 23 (RR Rotation at 12), 44 (RR Rotation at 20), and 52:
- Insert
23: right child of20. .- RR (Left) Rotation at
12:18becomes root!12becomes left child of18(with left8and right14);20(with right23) is right child of18.
- RR (Left) Rotation at
- Insert
44: right child of23. RR (Left) Rotation at20:23replaces20with children20, 44. - Insert
52: right child of44. . All (balanced!).
18 (-1)
/ \
12 (0) 23 (-1)
/ \ / \
8 (0) 14 (0) 20 (0) 44 (-1)
\
52 (0)Answer:
Final AVL tree has root 18, left subtree 12 (8, 14), and right subtree 23 (left 20; right 44 with right child 52).