tests/sims/btree.test.ts
The automated tests for the /simulators/btree simulator. They run the model on its own, outside the browser, and compare it with a reference that doesn't depend on the model being right. They run on every change to the simulator's code.
- Proactive splitting gives the same tree as the CLRS algorithm after every insert and delete.
- B-tree and B+ tree invariants hold after random inserts and deletes, for every split setting.
// /simulators/btree
import { test } from 'node:test';
import { BTree, validate } from '../../src/lib/sims/btreeModel.ts';
import { checker, lcg } from './check.ts';
// The CLRS insert (split full nodes on the way down) and delete (make sure a child has a spare key
// before descending), written independently of the model, for comparing tree shapes step by step.
type N = { keys: number[]; children: N[]; leaf: boolean };
function clrsTree(order: number) {
let root: N = { keys: [], children: [], leaf: true };
const copy = (n: N): N => ({ keys: [...n.keys], children: n.children.map(copy), leaf: n.leaf });
const lower = (arr: number[], k: number) => {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] < k) lo = mid + 1;
else hi = mid;
}
return lo;
};
function splitChild(parent: N, i: number) {
const y = parent.children[i];
const mid = Math.floor(order / 2);
const z: N = { keys: y.keys.slice(mid + 1), children: y.leaf ? [] : y.children.slice(mid + 1), leaf: y.leaf };
const median = y.keys[mid];
y.keys = y.keys.slice(0, mid);
if (!y.leaf) y.children = y.children.slice(0, mid + 1);
parent.children.splice(i + 1, 0, z);
parent.keys.splice(i, 0, median);
return median;
}
function insertNonFull(n: N, k: number) {
if (n.leaf) {
const i = lower(n.keys, k);
if (n.keys[i] !== k) n.keys.splice(i, 0, k);
return;
}
let i = lower(n.keys, k);
if (n.children[i].keys.length >= order) {
const median = splitChild(n, i);
if (k > median) i++;
else if (k === median) return;
}
insertNonFull(n.children[i], k);
}
function insert(k: number) {
const next = copy(root);
if (next.keys.length >= order) {
const nr: N = { keys: [], children: [next], leaf: false };
splitChild(nr, 0);
insertNonFull(nr, k);
root = nr;
} else {
insertNonFull(next, k);
root = next;
}
}
const minKey = (n: N) => { while (!n.leaf) n = n.children[0]; return n.keys[0]; };
const maxKey = (n: N) => { while (!n.leaf) n = n.children[n.children.length - 1]; return n.keys[n.keys.length - 1]; };
const minKeys = () => Math.ceil(order / 2) - 1;
function merge(p: N, i: number) {
const l = p.children[i], rr = p.children[i + 1];
l.keys = [...l.keys, p.keys[i], ...rr.keys];
if (!l.leaf) l.children = [...l.children, ...rr.children];
p.keys.splice(i, 1);
p.children.splice(i + 1, 1);
}
function ensureRich(p: N, i: number) {
const c = p.children[i];
if (c.keys.length > minKeys()) return;
const l = i > 0 ? p.children[i - 1] : null;
const rr = i < p.children.length - 1 ? p.children[i + 1] : null;
if (l && l.keys.length > minKeys()) {
c.keys.unshift(p.keys[i - 1]);
p.keys[i - 1] = l.keys.pop()!;
if (!c.leaf) c.children.unshift(l.children.pop()!);
} else if (rr && rr.keys.length > minKeys()) {
c.keys.push(p.keys[i]);
p.keys[i] = rr.keys.shift()!;
if (!c.leaf) c.children.push(rr.children.shift()!);
} else if (l) merge(p, i - 1);
else if (rr) merge(p, i);
}
function deleteFrom(n: N, k: number) {
const i = lower(n.keys, k);
if (i < n.keys.length && n.keys[i] === k) {
if (n.leaf) { n.keys.splice(i, 1); return; }
const l = n.children[i], rr = n.children[i + 1];
if (l.keys.length > minKeys()) { const pred = maxKey(l); deleteFrom(l, pred); n.keys[i] = pred; }
else if (rr.keys.length > minKeys()) { const succ = minKey(rr); deleteFrom(rr, succ); n.keys[i] = succ; }
else { merge(n, i); deleteFrom(n.children[i], k); }
return;
}
if (n.leaf) return;
ensureRich(n, i);
deleteFrom(n.children[lower(n.keys, k)], k);
}
function del(k: number) {
const next = copy(root);
deleteFrom(next, k);
root = !next.leaf && next.keys.length === 0 ? next.children[0] : next;
}
const shape = (n: N): unknown => (n.leaf ? n.keys : [n.keys, n.children.map(shape)]);
return { insert, del, shape: () => JSON.stringify(shape(root)) };
}
const shapeOf = (t: BTree) => {
const w = (n: { leaf: boolean; keys: number[]; children: unknown[] }): unknown => (n.leaf ? n.keys : [n.keys, n.children.map((c) => w(c as never))]);
return JSON.stringify(w(t.root as never));
};
test('proactive splitting gives the same tree as the CLRS algorithm after every insert and delete', () => {
const { ok, done } = checker();
const r = lcg(9);
for (const order of [3, 4, 5, 7]) for (let trial = 0; trial < 200; trial++) {
const ref = clrsTree(order);
const t = new BTree({ variant: 'b', maxKeys: order, split: 'proactive', bias: 'left' });
const present = new Set<number>();
for (let i = 0; i < 60; i++) {
const k = Math.floor(r() * 80);
if (r() < 0.3) {
if (!present.has(k)) continue;
ref.del(k); t.delete(k); present.delete(k);
} else {
if (present.has(k)) continue;
ref.insert(k); t.insert(k); present.add(k);
}
ok(ref.shape() === shapeOf(t), `order ${order}: ${ref.shape()} vs ${shapeOf(t)}`);
}
}
done();
});
test('B-tree and B+ tree invariants hold after random inserts and deletes, for every split setting', () => {
const { ok, done } = checker();
const r = lcg(10);
for (const variant of ['b', 'bplus'] as const) for (const maxKeys of [2, 3, 4, 5, 6]) for (const bias of ['left', 'right'] as const) for (let trial = 0; trial < 60; trial++) {
const t = new BTree({ variant, maxKeys, split: 'overflow', bias });
const set = new Set<number>();
for (let i = 0; i < 120; i++) {
const k = Math.floor(r() * 150);
if (r() < 0.4 && set.size) {
const arr = [...set];
const x = arr[Math.floor(r() * arr.length)];
ok(t.delete(x), 'delete of a present key failed');
set.delete(x);
} else {
t.insert(k);
set.add(k);
}
const v = validate(t);
ok(!v.length, `${variant} max ${maxKeys} ${bias}: ${v.join('; ')}`);
ok(t.keys().join() === [...set].sort((a, b) => a - b).join(), `${variant} keys out of order or missing`);
}
for (const k of set) ok(t.has(k), 'present key not found');
for (let k = 150; k < 160; k++) ok(!t.has(k), 'absent key found');
}
done();
});
Shared helpers: tests/sims/check.ts. The model under test is imported from src/lib/sims/.