Skip to main content

B-tree of order 3 for 52, 46, 27, ...

Short answer

Insert sequentially; node overflows at 3 keys, splits. Final B-tree order 3: root [81], left internal [46] with leaves [27 35] [52 72]; right internal [108 115] with leaves [86 90] [110] [121].

Construct a B-tree of order 3 for given set of data: 52, 46, 27, 81, 90, 108, 72, 110, 35, 115, 121 and 86.

A B-tree of order 3 allows at most 3 children (2 keys) per node and at least 1 key in a non-root node. A key is inserted into its leaf; if the leaf then holds 3 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
152[52]fits in leaf
246[46 52]fits in leaf
327[46]{[27], [52]}leaf [27 46 52] overflows, split: 46 moves up; new root
481[46]{[27], [52 81]}fits in leaf
590[46 81]{[27], [52], [90]}leaf [52 81 90] overflows, split: 81 moves up
6108[46 81]{[27], [52], [90 108]}fits in leaf
772[46 81]{[27], [52 72], [90 108]}fits in leaf
8110[81]{[46]{[27], [52 72]}, [108]{[90], [110]}}leaf [90 108 110] overflows, split: 108 moves up; internal node [46 81 108] overflows, split: 81 moves up; new root
935[81]{[46]{[27 35], [52 72]}, [108]{[90], [110]}}fits in leaf
10115[81]{[46]{[27 35], [52 72]}, [108]{[90], [110 115]}}fits in leaf
11121[81]{[46]{[27 35], [52 72]}, [108 115]{[90], [110], [121]}}leaf [110 115 121] overflows, split: 115 moves up
1286[81]{[46]{[27 35], [52 72]}, [108 115]{[86 90], [110], [121]}}fits in leaf

Final B-tree of order 3

[81]
[46]  [108 115]
[27 35]  [52 72]  [86 90]  [110]  [121]

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 →