PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q5

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

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

Question

Define B-tree with its properties. construct a B-tree of order 5 from the following data: 1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3, 12, 14, 20, 21, 16

Solution

Definition and Properties of a B-Tree of Order : A B-Tree of order is a self-balancing multi-way search tree optimized for disk-based storage:

  1. Every node has at most children and at most keys (for : max 4 keys, max 5 children).
  2. Every internal node (except the root) has at least children and keys (for : min 3 children, min 2 keys).
  3. The root has at least 2 children if it is not a leaf.
  4. All leaf nodes appear at the exact same depth.
  5. Keys inside each node are sorted in ascending order and partition child subtrees.

Insertions 1, 7, 6, 2, 11 (First Split):

        [6]
       /   \
   [1, 2]  [7, 11]

Insertions 4, 8, 13, 10, 5, 19, 9, 18, 24, 3:

Insertions 12, 14, 20, 21, 16 (Leaf and Root Split):

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

Final B-tree of order 5 (height 3):

All past exam questions for Data Structure and Algorithms