A · Compressed recap
Trees: root, leaf, internal node; level of root = 1; height = number of levels; full m-ary tree with h levels has (m^h − 1)/(m − 1) nodes. Search trees order keys so a search follows one path; balanced = all leaves on one level.
B-tree of order p (max children): ≤ p − 1 keys; non-root internal ≥ ⌈p/2⌉ children; root ≥ 2 children unless a leaf; every key once, with a record pointer; node size p·P + (p − 1)(K + Pr) ≤ B. Conventions differ (min keys d, CLRS min degree t). Insert into a leaf, split on overflow, median up, root split grows height. Delete: borrow or merge; root empty shrinks height. Keys: max p^h − 1, min 2⌈p/2⌉^(h−1) − 1.
B · Merged rule card
5.4.1 Tree primer: node, root, leaf, height, search tree, balanced tree
- Root, parent, child, sibling, leaf, internal node, subtree; level of root = 1; height = number of levels.
- m-ary tree with h levels: max (m^h − 1)/(m − 1) nodes; m^(h−1) leaves.
- m-way search tree: ≤ m − 1 sorted keys, ≤ m children, keys split children's ranges.
- Balanced = all leaves at the same level; height ≈ log_m n; one node = one block.
5.5.1 B-tree structure and order (order conventions and the GATE trap)
- B-tree order p (max children): ≤ p − 1 keys; non-root internal ≥ ⌈p/2⌉ children; root ≥ 2 children unless leaf; all leaves same level.
- Each key appears once, with a record pointer.
- Node size: p·P + (p − 1)(K + Pr) ≤ B.
- Conventions: max children p; min keys d (d..2d keys); min degree t (t−1..2t−1 keys).
5.5.2 B-tree search and insertion with node splits
- Search: compare in node, stop if found, else follow the matching child; ≤ height accesses.
- Insert into a leaf; on overflow (p keys) split, median moves up; cascade; root split → height + 1.
- Trace format: level-by-level brackets; count every node split.
5.5.3 B-tree deletion basics; min/max keys; height bounds
- Delete internal key → swap with predecessor/successor in a leaf. Leaf underflow → borrow (rotate through parent) or merge (with parent's separator). Root emptied → height − 1.
- Max keys (height h) = p^h − 1. Min keys = 2⌈p/2⌉^(h−1) − 1.
- h_min = ⌈log_p(n + 1)⌉; h_max = 1 + ⌊log_⌈p/2⌉((n + 1)/2)⌋.
C · Interleaved GATE-style questions
Q1 · NAT · 1 mark(s) — Trees
A full binary tree with 4 levels has how many leaves?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Order
B = 2048, K = 16, P = 8, Pr = 8. B-tree order p (max children)?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Splits
Max 2 keys per node. Insert 50, 40, 30, 20, 10 into an empty B-tree. How many splits?
Numerical answer: ________
Q4 · MCQ · 1 mark(s) — Min fill
In a B-tree of order 8 (max children), a non-root internal node has at least:
- (A) 1 key
- (B) 3 keys
- (C) 4 keys
- (D) 7 keys
Q5 · NAT · 2 mark(s) — Max keys
B-tree of order 4, height 3. Maximum number of keys?
Numerical answer: ________
Q6 · NAT · 2 mark(s) — Min keys
B-tree of order 4, height 3. Minimum number of keys?
Numerical answer: ________
Q7 · MCQ · 2 mark(s) — Convention
A question states "B-tree of order 4, each node has between 4 and 8 keys". The maximum number of children of a node is:
- (A) 9
- (B) 5
- (C) 8
- (D) 4
Q8 · MCQ · 1 mark(s) — Height
Which event makes all leaves of a B-tree one level deeper?
- (A) a borrow
- (B) a leaf split
- (C) a merge
- (D) a root split
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 8 · 1 mark(s)
2³.
Re-read: Lesson 5.4.1 — Tree primer: node, root, leaf, height, search tree, balanced tree
Q2 Answer: 64 · 2 mark(s)
8p + 24(p − 1) ≤ 2048 → 32p ≤ 2072 → p ≤ 64.75 → 64.
Re-read: Lesson 5.5.1 — B-tree structure and order (order conventions and the GATE trap)
Q3 Answer: 2 · 2 mark(s)
30 splits [30 40 50] → root [40]; 10 splits [10 20 30] → 20 up: root [20 40].
Re-read: Lesson 5.5.2 — B-tree search and insertion with node splits
Q4 Answer: (B) · 1 mark(s)
⌈8/2⌉ = 4 children → 3 keys.
- (A) is wrong: Only the root may have 1 key.
- (C) is wrong: That is the number of children.
- (D) is wrong: That is the maximum.
Re-read: Lesson 5.5.1 — B-tree structure and order (order conventions and the GATE trap)
Q5 Answer: 63 · 2 mark(s)
4³ − 1.
Re-read: Lesson 5.5.3 — B-tree deletion basics; min/max keys; height bounds
Q6 Answer: 7 · 2 mark(s)
m = 2: 2·2² − 1.
Re-read: Lesson 5.5.3 — B-tree deletion basics; min/max keys; height bounds
Q7 Answer: (A) · 2 mark(s)
Min-keys convention (d = 4): max 8 keys → 9 children.
- (B) is wrong: No.
- (C) is wrong: That is the max number of keys.
- (D) is wrong: Misreads order as max children.
Re-read: Lesson 5.5.1 — B-tree structure and order (order conventions and the GATE trap)
Q8 Answer: (D) · 1 mark(s)
New root.
- (A) is wrong: No change.
- (B) is wrong: Same level.
- (C) is wrong: Can reduce height.
Re-read: Lesson 5.5.2 — B-tree search and insertion with node splits