Skip to main content

B-tree of order 5 for 82, 12, 22, ...

Short answer

Keys inserted sequentially; a node overflows at 5 keys and splits, moving median up. Final tree: root [23 56 82] and leaves [12 22], [28 37 44], [59 60 65 74], [96 99].

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

A B-tree of order 5 allows at most 5 children (4 keys) per node and at least 2 keys in a non-root node. A key is inserted into its leaf; if the leaf then holds 5 keys it overflows, is split at the median, and the median moves up to the parent. The split may repeat up to the root.

Step-by-step construction

StepInsertTree after stepAction
182[82]fits in leaf
212[12 82]fits in leaf
322[12 22 82]fits in leaf
423[12 22 23 82]fits in leaf
556[23]{[12 22], [56 82]}leaf [12 22 23 56 82] overflows, split: 23 moves up; new root
696[23]{[12 22], [56 82 96]}fits in leaf
737[23]{[12 22], [37 56 82 96]}fits in leaf
899[23 82]{[12 22], [37 56], [96 99]}leaf [37 56 82 96 99] overflows, split: 82 moves up
959[23 82]{[12 22], [37 56 59], [96 99]}fits in leaf
1074[23 82]{[12 22], [37 56 59 74], [96 99]}fits in leaf
1128[23 56 82]{[12 22], [28 37], [59 74], [96 99]}leaf [28 37 56 59 74] overflows, split: 56 moves up
1265[23 56 82]{[12 22], [28 37], [59 65 74], [96 99]}fits in leaf
1360[23 56 82]{[12 22], [28 37], [59 60 65 74], [96 99]}fits in leaf
1444[23 56 82]{[12 22], [28 37 44], [59 60 65 74], [96 99]}fits in leaf

Final B-tree of order 5

[23 56 82]
[12 22]  [28 37 44]  [59 60 65 74]  [96 99]

All leaves are on the same level and every node respects the key limits.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →