B-Tree (C)
Topics: data structures, balanced trees, ordered map
Problem
Implement a B-tree ordered map of int -> int with minimum degree t
(CLRS style). Every node holds between t-1 and 2t-1 keys; the tree stays
balanced by splitting a full child and pushing its median key up to the
parent (and splitting the root to add height). Support get, insert, and an
ordered range scan — deletion is out of scope. Nodes come from a
caller-provided pool, bump-allocated via bt_alloc (no malloc); each node is
sized for the largest supported degree BT_MAX_T.
typedef struct BTNode {
int n; bool leaf;
int keys[2*BT_MAX_T - 1]; int vals[2*BT_MAX_T - 1];
struct BTNode *children[2*BT_MAX_T];
} BTNode;
typedef struct { BTNode *pool; size_t cap; size_t used; int t; BTNode *root; } BTree;
void bt_init(BTree *b, BTNode *storage, size_t cap, int t);
bool bt_get(BTree *b, int key, int *out);
void bt_insert(BTree *b, int key, int val); // insert or update
size_t bt_range(BTree *b, int lo, int hi, int *keys, int *vals, size_t maxout); // lo<=k<=hi, ascending
The split-on-the-way-down invariant
Insert descends from the root, and before stepping into a child that is full
(2t-1 keys), split it first. That keeps the parent guaranteed non-full when you
recurse, so a split never cascades upward. To start, if the root is full,
allocate a new root, hang the old root as its only child, split it, and continue.
bt_split_child(parent, i): the full child keeps keys [0, t-1), the new
right sibling takes [t, 2t-1), and the median keys[t-1] moves up into the
parent at position i (with the right sibling linked at i+1). Move children
too when the child is internal.bt_get: at each node, scan to the first key >= target; match → done, leaf
→ absent, else descend into children[i].bt_range: in-order walk — before each key descend left if it may contain
keys >= lo, emit the key if in [lo, hi], and stop once a key exceeds hi.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/btree && /tmp/btree
Sign in to submit your solution.