- Asked 2/14
- 2072 Asoj · 6 marks
B-tree of order 5 for letters C N G A H ...
Short answer
Construct by sequential insertion; overflow at 5 keys, split median up. Final tree: root [M], internal nodes [D G] and [Q T], leaf nodes [A C], [E F], [H K L], [N P], [R S], [W X Y Z].
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 step.
Order 5 means at most 4 keys per node and at least 2 keys in a non-root node. Letters are compared alphabetically. When a node reaches 5 keys it is split at the median (3rd key), which moves up.
Step-by-step construction
| Step | Insert | Tree after step | Action |
|---|---|---|---|
| 1 | C | [C] | fits in leaf |
| 2 | N | [C N] | fits in leaf |
| 3 | G | [C G N] | fits in leaf |
| 4 | A | [A C G N] | fits in leaf |
| 5 | H | [G]{[A C], [H N]} | leaf [A C G H N] overflows, split: G moves up; new root |
| 6 | E | [G]{[A C E], [H N]} | fits in leaf |
| 7 | K | [G]{[A C E], [H K N]} | fits in leaf |
| 8 | Q | [G]{[A C E], [H K N Q]} | fits in leaf |
| 9 | M | [G M]{[A C E], [H K], [N Q]} | leaf [H K M N Q] overflows, split: M moves up |
| 10 | F | [G M]{[A C E F], [H K], [N Q]} | fits in leaf |
| 11 | W | [G M]{[A C E F], [H K], [N Q W]} | fits in leaf |
| 12 | L | [G M]{[A C E F], [H K L], [N Q W]} | fits in leaf |
| 13 | T | [G M]{[A C E F], [H K L], [N Q T W]} | fits in leaf |
| 14 | Z | [G M T]{[A C E F], [H K L], [N Q], [W Z]} | leaf [N Q T W Z] overflows, split: T moves up |
| 15 | D | [D G M T]{[A C], [E F], [H K L], [N Q], [W Z]} | leaf [A C D E F] overflows, split: D moves up |
| 16 | P | [D G M T]{[A C], [E F], [H K L], [N P Q], [W Z]} | fits in leaf |
| 17 | R | [D G M T]{[A C], [E F], [H K L], [N P Q R], [W Z]} | fits in leaf |
| 18 | X | [D G M T]{[A C], [E F], [H K L], [N P Q R], [W X Z]} | fits in leaf |
| 19 | Y | [D G M T]{[A C], [E F], [H K L], [N P Q R], [W X Y Z]} | fits in leaf |
| 20 | S | [M]{[D G]{[A C], [E F], [H K L]}, [Q T]{[N P], [R S], [W X Y Z]}} | leaf [N P Q R S] overflows, split: Q moves up; internal node [D G M Q T] overflows, split: M moves up; new root |
Final B-tree of order 5
[M]
[D G] [Q T]
[A C] [E F] [H K L] [N P] [R S] [W X Y Z]
Tree height is 3 levels (root, one internal level, leaves).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- B-tree from 78, 21, 14, 11, 97, 85, 74, 63 · Data Structure and Algorithm, chapter 6 · asked 2×
- B-tree of order 3 for 52, 46, 27, ... · Data Structure and Algorithm, chapter 6
- B-tree of order 5 for 82, 12, 22, ... · Data Structure and Algorithm, chapter 6 · asked 2×
- B-tree properties; order 5 for 3, 14, 7, ... · Data Structure and Algorithm, chapter 6 · asked 2×
- Expression tree and traversals · Data Structure and Algorithm, chapter 6
- Box trace and TOH recursion tree · Data Structure and Algorithm, chapter 5
- AVL tree for 3, 2, 1, 4, 5, 6, 7, ... · Data Structure and Algorithm, chapter 6
- FP-tree on HotDogs data · Data Mining, chapter 4
- FP-tree on t1-t5 data · Data Mining, chapter 4
- First-order system impulse and step response · Signals and Systems, chapter 5
- Impulse and ramp response from first order step response · Control Systems, chapter 3