PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q9

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

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

Question

Construct B-tree of order 5 for the set of data C N G A H E K Q M F W L T Z D P R X Y S showing each steps.

Solution

Order-5 B-Tree Rules (, Max 4 Keys/Node) and First Split (C, N, G, A, H): Using alphabetical order (A < B < ... < Z):

        [G]
       /   \
   [A, C]  [H, N]

Insert E, K, Q, M, F, W, L, T:

Insert Z, D, P, R, X, Y, S (Splits and Root Growth):

                        [M]
                     /       \
              [D, G]           [Q, T]
             /  |   \         /   |   \
         [A,C] [E,F] [H,K,L] [N,P] [R,S] [W,X,Y,Z]
Answer:

Final order-5 B-tree:

All past exam questions for Data Structure and Algorithms