Past exam question: 2066 Bhadra (Regular / Back), Q8
Open in the Padhaiko appQuestion
Why tree balancing is required? Insert the following keys to a 5-way B-tree: 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 4, 19, 8, 31, 35, 10, 13, 12
Solution
Why Tree Balancing is Required: When keys are inserted in sorted or nearly sorted order into a standard BST, the tree degenerates into a skewed linear chain of height , degrading search, insertion, and deletion from to (and causing excessive disk reads on external storage). Balancing keeps tree height (or for B-trees).
5-Way B-Tree Construction (, Max 4 Keys/Node):
- Insert
3, 7, 9, 23, 45:[3, 7, 9, 23, 45]splits at9root[9], leaves[3, 7],[23, 45]. - Insert
1, 5, 14, 25, 24:1, 5into[1, 3, 5, 7].14, 25, 24overflows[14, 23, 24, 25, 45]promote24to root[9, 24]; leaves:[1, 3, 5, 7],[14, 23],[25, 45].
- Insert
13, 11, 4, 19, 8:13, 11into[11, 13, 14, 23].4overflows[1, 3, 4, 5, 7]promote4to root[4, 9, 24]; leaves:[1, 3],[5, 7].19overflows[11, 13, 14, 19, 23]promote14to root[4, 9, 14, 24]; middle leaves:[11, 13],[19, 23].8into[5, 7, 8].
- Insert
31, 35, 10, 13, 12:31, 35into[25, 31, 35, 45].10, 13into[10, 11, 13, 13].12overflows[10, 11, 12, 13, 13]promote12into full root[4, 9, 12, 14, 24]!- Root splits at median
12into new root[12]:
[12]
/ \
[4, 9] [14, 24]
/ | \ / | \
[1,3] [5,7,8] [10,11] [13,13] [19,23] [25,31,35,45]Answer:
Tree balancing prevents skewed height degradation and guarantees operations. Final 5-way B-tree: root [12], level-1 [4, 9] and [14, 24], leaves [1, 3], [5, 7, 8], [10, 11], [13, 13], [19, 23], [25, 31, 35, 45].