PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q6(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

Construct a B-tree of order 5 for following data: 82, 12, 22, 23, 56, 96, 37, 99, 59, 74, 28, 65, 60 and 44.

Solution

Order-5 B-Tree Rules & Insertions 82, 12, 22, 23, 56: Order max 4 keys per node, min 2 keys (except root).

        [23]
       /    \
  [12, 22]  [56, 82]

Insertions 96, 37, 99, 59, 74:

Insertions 28, 65, 60, 44:

                 [23, 56, 82]
            /      |        |      \
      [12, 22] [28,37,44] [59,60,65,74] [96, 99]
Answer:

Final order-5 B-tree (height 2):

All past exam questions for Data Structure and Algorithms