PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

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):

  1. Insert 3, 7, 9, 23, 45: [3, 7, 9, 23, 45] splits at 9 root [9], leaves [3, 7], [23, 45].
  2. Insert 1, 5, 14, 25, 24:
    • 1, 5 into [1, 3, 5, 7].
    • 14, 25, 24 overflows [14, 23, 24, 25, 45] promote 24 to root [9, 24]; leaves: [1, 3, 5, 7], [14, 23], [25, 45].
  3. Insert 13, 11, 4, 19, 8:
    • 13, 11 into [11, 13, 14, 23].
    • 4 overflows [1, 3, 4, 5, 7] promote 4 to root [4, 9, 24]; leaves: [1, 3], [5, 7].
    • 19 overflows [11, 13, 14, 19, 23] promote 14 to root [4, 9, 14, 24]; middle leaves: [11, 13], [19, 23].
    • 8 into [5, 7, 8].
  4. Insert 31, 35, 10, 13, 12:
    • 31, 35 into [25, 31, 35, 45].
    • 10, 13 into [10, 11, 13, 13].
    • 12 overflows [10, 11, 12, 13, 13] promote 12 into full root [4, 9, 12, 14, 24]!
    • Root splits at median 12 into 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].

All past exam questions for Data Structure and Algorithms