Skip to main content

B-tree from 78, 21, 14, 11, 97, 85, 74, 63

Short answer

Assuming order 5, insert sequentially and split when a node holds 5 keys. Final tree: root [21 78] with leaf children [11 14], [63 74], [85 97].

Construct B-tree from the data set given by 78, 21, 14, 11, 97, 85, 74, 63 showing each insertion step.

The order is not given, so a B-tree of order 5 is assumed (at most 4 keys per node; a node splits when it receives a fifth key, and the median moves up).

Insertion steps (order 5)

StepInsertTree after stepAction
178[78]fits in leaf
221[21 78]fits in leaf
314[14 21 78]fits in leaf
411[11 14 21 78]fits in leaf
597[21]{[11 14], [78 97]}leaf [11 14 21 78 97] overflows, split: 21 moves up; new root
685[21]{[11 14], [78 85 97]}fits in leaf
774[21]{[11 14], [74 78 85 97]}fits in leaf
863[21 78]{[11 14], [63 74], [85 97]}leaf [63 74 78 85 97] overflows, split: 78 moves up

Final B-tree

[21 78]
[11 14]  [63 74]  [85 97]

If order 3 is intended (at most 2 keys per node)

The final tree is:

[74]
[21]  [85]
[11 14]  [63]  [78]  [97]

Here a split happens whenever a node gets a third key. The tree has three levels because the root splits when the key 63 pushes 74 up.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →