PadhaikoAll subjects

Past exam question: 2064 Jestha, Q5

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Define B-tree and construct the B-tree for order 5 (i.e. M = 5) for given sequence of data 1,7,6,2,11,4,8,13,10,5,19,9,18,24,3,12,14,20,21,16 showing each steps.

Solution

Definition of Order-5 B-Tree: A B-Tree of order is a balanced multi-way search tree where every node has at most children and sorted keys, every internal node (except root) has at least children and keys, and all leaf nodes lie at the same depth.

Step-by-Step Construction (1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3):

Insert 12, 14, 20, 21, 16 (Root Split):

                         [10]
                      /        \
               [3, 6]           [13, 18]
              /   |   \         /   |    \
         [1,2] [4,5] [7,8,9] [11,12] [14,16] [19,20,21,24]
Answer:

Final order-5 B-tree: root [10], internal nodes [3, 6] and [13, 18], leaves [1, 2], [4, 5], [7, 8, 9], [11, 12], [14, 16], [19, 20, 21, 24].

All past exam questions for Data Structure and Algorithms