PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q4

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Discuss the application of multiway search tree. Define B-tree. Using the insertion algorithm of B tree. Create 3-order B tree for the given sequence of date. 8,14,2,15,3,1,12,6,5

Solution

Applications of Multi-Way Search Trees & Definition of B-Tree:

Order-3 B-Tree (2-3 Tree, Max 2 Keys/Node) Construction for 8, 14, 2, 15, 3, 1, 12, 6, 5:

  1. Insert 8, 14: [8, 14] (full).
  2. Insert 2: [2, 8, 14] overflows promote median 8: root [8], leaves [2], [14].
  3. Insert 15: [14, 15].
  4. Insert 3: [2, 3].
  5. Insert 1: [1, 2, 3] overflows promote 2 to root [2, 8]; leaves [1], [3], [14, 15].
  6. Insert 12: [12, 14, 15] overflows promote 14 into root [2, 8, 14]! Root overflows promote 8 to new root [8]: [8] -> ([2] -> [1], [3]) and ([14] -> [12], [15]).
  7. Insert 6: [3, 6].
  8. Insert 5: [3, 5, 6] overflows promote 5 to [2, 5]; leaves under [2, 5] are [1], [3], [6].
                 [8]
              /       \
         [2, 5]       [14]
        /  |   \      /   \
      [1] [3]  [6]  [12]  [15]
Answer:

Multi-way search trees power database/file-system indexing by minimizing disk reads. Final 3-order B-tree: root [8], level-1 [2, 5] and [14], leaves [1], [3], [6], [12], [15].

All past exam questions for Data Structure and Algorithms