An X-fast trie answers the exact same three
questions as Van Emde Boas Tree — member,
successor, predecessor, over a fixed universe {0, ..., U-1} — in the same
O(log log U) time, but gets there by a completely different mechanism. Instead of a
recursive skeleton of clusters preallocated to cover the whole universe, it keeps one hash table
per bit of the key — w = log₂ U levels, plus the root — mapping each prefix
that's an ancestor of some stored value to a small record, and threads the actual stored values
together in a sorted doubly linked list. Finding where a query value's path stops matching anything
real becomes a binary search over those w+1 hash tables rather than
one guaranteed-shape recursive call per level — the same "binary search a monotonic yes/no
sequence" shape as Binary Search on Answer,
just applied to trie levels instead of array indices.
The universe below has the same 16 values as the Van Emde Boas page, split into 5 rows instead of nested clusters — one row per trie level, from level 0 (the root, a single cell) down to level 4 (the 16 actual leaf values). A cell is lit up if that prefix is an ancestor of some stored value. The same 5 values are preloaded as the vEB page, {2, 3, 5, 8, 14}, so the two structures can be compared directly on identical data. Insert a value, or pick Member / Successor / Predecessor and a value, then step through to see exactly which levels get probed and which hash-table entries get touched.
A hash table per level, not a recursive skeleton. Level j's hash
table holds every j-bit prefix that's a real ancestor of some currently-stored value —
nothing is preallocated. On the preloaded set {2, 3, 5, 8, 14} (binary
0010, 0011, 0101, 1000, 1110), level 1 holds both possible prefixes (0 and
1, since some value starts with each), but level 3 only holds the four 3-bit prefixes
that are actually ancestors of one of those five leaves. This is the direct trade against vEB's
fixed O(U) allocation: space here is proportional to how many distinct prefixes the
stored values actually create, which is at most n · (w+1) — see Complexity.
The descendant pointer. Any node that's missing exactly one child stores a
single pointer: if it's missing its left child, the pointer holds the smallest
leaf in the right subtree it does have; if missing its right child, the largest
leaf in the left subtree. That single pointer is enough to answer successor or predecessor the
instant a query's path runs off the edge of the real trie — no need to climb back up looking for
somewhere to go. On the preloaded set, level 3's node for prefix 111 (an ancestor of
only 14 = 1110) is missing its right child, so it points to 14 itself —
the largest leaf in the only subtree it has.
Binary search finds the drop-off point. For a fixed query value x,
whether prefix(x, j) exists in level j's table is true for
every level up to some threshold and false for every level past it — x's
path through the trie either keeps matching something real or it doesn't, and once it stops
matching it can never start again (except at the very last level, if x itself turns
out to be present). That's exactly the monotonic yes/no/no/no shape a binary search needs: instead
of checking levels 0, 1, 2, 3, ... in order, jump straight to the middle level,
narrow the range by half depending on the answer, and repeat — O(log(w+1)) hash
lookups instead of up to w+1 of them. Since w = log₂ U, that's
O(log log U) lookups total, each expected O(1). Once the deepest
matching level is found, that node's own descendant pointer (or, if x itself was
found, a single hop along the sorted linked list) gives the answer directly.
Insert has to touch every level — that's the asymmetry with vEB. Answering a
query only needs to find the drop-off point, which binary search does in
O(log log U) lookups. But recording a brand-new value means creating a hash
table entry at every level from the drop-off point down to the leaf, and
potentially updating a descendant pointer at every level above the drop-off point too —
together that's exactly w+1 node-visits, no fewer, regardless of where the drop-off
happens to fall. Instrumenting the reference implementation below confirms this exactly: across 110
randomized inserts at three universe sizes, every single one touched precisely w+1
node-visits (5 at w=4, 17 at w=16, 33 at w=32) — never more,
never fewer. So insert is O(log U) expected, not O(log log U) — unlike
Van Emde Boas Tree, whose insert genuinely does hit O(log log U) because its
empty-cluster shortcut skips recursing into a subtree that's about to hold exactly one value. An
X-fast trie can't take that shortcut: a hash table entry has to exist at every level or the binary
search that makes queries fast would have nothing to find.
class XFastTrie {
constructor(w) { // w = number of bits in the universe (U = 2^w)
this.w = w;
this.U = 1 << w;
this.levels = []; // levels[j]: Map from j-bit prefix -> { missingSide, desc }
for (let j = 0; j <= w; j++) this.levels.push(new Map());
this.present = new Set();
this.prev = new Map(); // sorted doubly linked list over present values
this.next = new Map();
}
prefix(x, j) { return x >>> (this.w - j); } // top j bits of x
bitAt(x, j) { return (x >>> (this.w - 1 - j)) & 1; } // bit deciding level j -> j+1
// Binary search for the deepest level whose prefix of x exists. The loop's own probes never
// reach level w (mid is always < hi), so level w needs one explicit check afterward.
longestMatch(x) {
let lo = 0, hi = this.w;
while (hi - lo > 1) {
const mid = (lo + hi) >> 1;
if (this.levels[mid].has(this.prefix(x, mid))) lo = mid; else hi = mid;
}
if (hi === this.w && this.levels[hi].has(this.prefix(x, hi))) lo = hi;
return lo;
}
member(x) {
if (this.levels[0].size === 0) return false;
return this.longestMatch(x) === this.w;
}
predecessorSuccessor(x) {
if (this.levels[0].size === 0) return { pred: null, succ: null };
const lo = this.longestMatch(x);
if (lo === this.w) {
const p = this.prev.get(x), s = this.next.get(x);
return { pred: p === -1 ? null : p, succ: s === this.U ? null : s };
}
const node = this.levels[lo].get(this.prefix(x, lo));
const bit = this.bitAt(x, lo);
if (bit === 0) { // x would go left; left is missing
const succ = node.desc; // desc = min of the right subtree
const p = this.prev.get(succ);
return { pred: p === -1 ? null : p, succ };
} else { // x would go right; right is missing
const pred = node.desc; // desc = max of the left subtree
const s = this.next.get(pred);
return { pred, succ: s === this.U ? null : s };
}
}
insert(x) {
if (this.present.has(x)) return;
if (this.levels[0].size === 0) { // bootstrap: first key ever
this.levels[0].set(0, { missingSide: null, desc: null });
for (let j = 0; j < this.w; j++) {
const b = this.bitAt(x, j);
Object.assign(this.levels[j].get(this.prefix(x, j)), { missingSide: 1 - b, desc: x });
this.levels[j + 1].set(this.prefix(x, j + 1), { missingSide: null, desc: null });
}
this.present.add(x);
this.prev.set(x, -1);
this.next.set(x, this.U);
return;
}
const lo = this.longestMatch(x);
if (lo === this.w) return; // already present
const node = this.levels[lo].get(this.prefix(x, lo));
const bit = this.bitAt(x, lo);
let pred, succ;
if (bit === 0) { succ = node.desc; const p = this.prev.get(succ); pred = p === -1 ? null : p; }
else { pred = node.desc; const s = this.next.get(pred); succ = s === this.U ? null : s; }
const predVal = pred === null ? -1 : pred, succVal = succ === null ? this.U : succ;
this.prev.set(x, predVal);
this.next.set(x, succVal);
if (predVal !== -1) this.next.set(predVal, x);
if (succVal !== this.U) this.prev.set(succVal, x);
this.present.add(x);
// Ancestors above the drop-off already have x's own direction as a real child (that's how the
// match got this far) — if such an ancestor is missing its OTHER side, x might be a new
// extreme of the side it does have.
for (let j = 0; j < lo; j++) {
const anc = this.levels[j].get(this.prefix(x, j));
if (anc.missingSide === null) continue; // both children present already
if (anc.missingSide === 0) { if (x < anc.desc) anc.desc = x; }
else { if (x > anc.desc) anc.desc = x; }
}
// The drop-off node itself just gained the child it was missing — both sides now present.
node.missingSide = null;
node.desc = null;
// Brand-new nodes from the drop-off down to the leaf: each has exactly one child (toward x),
// so x is trivially both the min and max of the only subtree any of them have.
for (let j = lo + 1; j <= this.w; j++) {
const cur = { missingSide: null, desc: null };
if (j < this.w) { const b = this.bitAt(x, j); cur.missingSide = 1 - b; cur.desc = x; }
this.levels[j].set(this.prefix(x, j), cur);
}
}
}Verified two ways before writing any of the prose above. First, exhaustively across three
universe sizes: 2,000 randomized trials of 10 inserts each at w=4, 500 trials of 20
inserts at w=6, and 100 trials of 40 inserts at w=8 — after every single
insert, every one of the U possible query points was checked for member, successor,
and predecessor against a plain sorted-array reference: 0 mismatches across
1,984,000 point-checks. Second, the binary-search claim itself was measured directly, not just
argued: building a 2,000-key trie at w=16, w=24, and w=32
and running 5,000 random queries against both the binary-search longestMatch above and
a naive level-by-level linear scan, both always agreed on the answer, but the average number of
hash-table checks stayed flat around 5-6 for binary search across all three universe sizes while
linear scan's average tracked n's typical shared-prefix depth rather than
w — see Pitfalls below for the worst-case gap between them, which is where the real
difference shows up.
Skipping the ancestor descendant-pointer update breaks successor/predecessor while
leaving membership completely correct — the two checks catch genuinely different bugs. A
tempting shortcut when writing insert is to only set up the newly created nodes below
the drop-off point and skip the loop over levels 0..lo-1 above it, reasoning that those
ancestors already existed and don't need to change. They don't need new children, but any
of them that's still missing its other side has a descendant pointer that can go stale the
moment the new value becomes a new extreme of the side it does have. Removing that loop and
stress-testing the result: member() stayed 100% correct (0 mismatches on the same
harness above, since membership only depends on which hash-table entries exist, never on descendant
pointers), while successor/predecessor were wrong on 23.9% of point-checks at
w=4 and 35.5% at w=6 — worse at the larger size, since more
insertions mean more opportunities for a stale pointer to be the one consulted. A test that only
checks membership after writing insert would ship this bug undetected.
Scanning levels in order instead of binary-searching them stays correct but throws away
the entire point of the structure. Checking levels[0], levels[1], levels[2], ...
in sequence until one is missing finds the exact same drop-off level as the binary search above —
it's a correctness-preserving change, not a bug a stress test would ever catch. But the cost
stops being O(log log U): inserting just {0, 1} into a w=32
trie and querying 2 (which shares a 30-bit prefix with both stored keys before
diverging) takes the binary search 6 hash-table checks to find the drop-off,
against 32 for the linear scan checking every level up to it — the same
gap, measured directly rather than assumed, that separates O(log w) from
O(w).
Time: member, successor, and predecessor
are O(log log U) expected — O(log(w+1)) hash-table lookups from
the binary search, each expected O(1), plus one O(1) descendant-pointer
or linked-list hop. insert is O(log U) expected, not
O(log log U) — see Why It Works for why it can't take the same shortcut vEB's insert
does. The "expected" qualifier matters here in a way it doesn't for vEB: vEB's bound is worst-case,
guaranteed by its fixed recursive shape regardless of what's stored, while every level here is a
real hash table, so an adversarial key distribution against a weak hash function could degrade
lookups away from O(1) — a risk vEB's array-indexed clusters simply don't have.
Space: O(n · (w+1)) = O(n log U) — each of n stored
values can create at most one new hash-table entry per level, capped at w+1 levels.
That's the direct trade against vEB's O(U): when n is much smaller than
U (a million keys drawn from a 64-bit universe, say), this structure costs a small
multiple of n instead of an astronomical, mostly-empty U — but for a
small, densely-populated universe like this page's own 16-value demo, vEB's flat allocation is
actually the cheaper of the two.
This site's guide, Choosing a Range Query Structure, sets Van Emde Boas Tree aside from its range-aggregate members as answering a genuinely different question — membership and ordering over a fixed universe, not a query over a contiguous array range. This page answers that identical question, so it sits alongside vEB in that same exception, not among the range-aggregate structures being compared.