↩ back to Array-Backed Trees

Van Emde Boas Tree

Every ordered-set structure on this site so far measures its cost against n, the number of elements actually stored — a balanced binary search tree answers member/successor/ predecessor in O(log n). A Van Emde Boas tree (vEB tree) answers the same three questions in O(log log U) instead, where U is the size of a fixed universe the values must come from — {0, 1, ..., U-1} — regardless of how many of those values are actually present. That's a genuinely different, usually much smaller, number: for a universe of a billion integers, log₂ U ≈ 30 but log₂ log₂ U ≈ 5. The trade for that speed is the structure itself: instead of one tree shaped by insertion order, it's a fixed recursive skeleton — built once, sized by U alone — of clusters of clusters of clusters, all the way down to pairs.

Try it

The universe below has 16 values, 0 through 15, split into 4 clusters of 4 (the thick tick marks), each of which splits again into 2 pairs of 2 (the thin tick marks) — the recursive structure bottoms out at pairs, the smallest universe size the algorithm needs a special case for. The summary row below it isn't part of the universe at all: it's a separate, smaller Van Emde Boas structure that tracks only which of the 4 top-level clusters are non-empty, letting the algorithm skip straight to the next occupied cluster instead of scanning every value one at a time. A set of 5 values is preloaded. Insert a value, or pick Member / Successor / Predecessor and a value, then step through to see exactly which clusters and summary get touched.

Why it works

The recursive split. A vEB structure over universe size u stores its own min and max directly, plus — when u > 2 — an array of √u child clusters, each itself a vEB structure over universe size √u, and one summary, a single extra vEB structure of size √u that tracks which of those clusters are non-empty. Any value x splits into high(x) = ⌊x / √u⌋ (which cluster) and low(x) = x mod √u (where inside that cluster) — on this page's u = 16 structure, √u = 4, so x = 6 is high=1, low=2: cluster 1, position 2 inside it.

The min is never stored twice. When a structure is empty, insert sets min = max = x and stops — no recursion at all. When a later insert arrives smaller than the current min, the code doesn't insert the new value recursively; it swaps: the old min gets inserted into the clusters instead, and the new, smaller value becomes the min directly. The result is that a structure's own min is never duplicated anywhere inside its children — it exists exactly once, as a plain field. On the preloaded demo set {2, 3, 5, 8, 14}, 2 is inserted first and becomes the top structure's min directly; when 3 arrives next, 3 isn't less than 2, so it recurses normally into cluster 0 and is stored there as 3 — cluster 0's own min ends up 3, not 2, because 2 was never pushed down into any cluster at all. Checking member(2) only ever succeeds via the top structure's own x === min check, never by recursing — try it above.

Exactly one recursive call, not two — that's what makes it O(log log U). A naive reading of insert looks like it makes two recursive calls whenever a cluster is empty: one into the summary, one into the cluster itself. It doesn't. Look closely at the empty-cluster branch: the summary gets a real recursive insert call, but the cluster itself is never recursed into — its min and max are set directly, the same O(1) shortcut described above, because a structure that's about to hold exactly one value doesn't need to recurse to record that. So every call to insert makes at most one real recursive call, into a structure of size √u: either the summary (cluster was empty) or the cluster itself (cluster was already occupied), never both. That gives the recurrence T(u) = T(√u) + O(1). Substituting m = log₂ u turns repeated square-rooting into repeated halving, S(m) = S(m/2) + O(1), which solves to S(m) = O(log m) — back in terms of u, O(log log u). Confirmed directly against the reference implementation below, not just asserted: instrumenting every insert call across 40,000 randomized inserts on this page's own u = 16 structure, not one of them ever made more than one recursive call in a single frame. Successor and predecessor have the same shape — recurse into the cluster if it has something bigger (or smaller), otherwise recurse into the summary, never both.

Reference implementation

class VanEmdeBoas {
  constructor(u) {                 // u must be 2 or a perfect square whose root is also
    this.u = u;                    // valid (this reference expects u = 4^k, e.g. 16, 256, 65536)
    this.min = null;
    this.max = null;
    if (u > 2) {
      this.clusterSize = Math.round(Math.sqrt(u));
      this.numClusters = this.clusterSize;
      this.summary = new VanEmdeBoas(this.clusterSize);
      this.cluster = [];
      for (let i = 0; i < this.numClusters; i++) this.cluster.push(new VanEmdeBoas(this.clusterSize));
    }
  }

  high(x) { return Math.floor(x / this.clusterSize); }
  low(x)  { return x % this.clusterSize; }
  index(h, l) { return h * this.clusterSize + l; }

  member(x) {
    if (x === this.min || x === this.max) return true;
    if (this.u === 2) return false;
    return this.cluster[this.high(x)].member(this.low(x));
  }

  insert(x) {
    if (this.min === null) { this.min = this.max = x; return; }
    if (x < this.min) { const t = this.min; this.min = x; x = t; }   // swap — see "Why it works"
    if (this.u > 2) {
      const h = this.high(x), l = this.low(x);
      if (this.cluster[h].min === null) {
        this.summary.insert(h);                        // ONE recursive call...
        this.cluster[h].min = this.cluster[h].max = l;  // ...the other branch is O(1), not recursive
      } else {
        this.cluster[h].insert(l);                      // the other case: ONE recursive call
      }
    }
    if (x > this.max) this.max = x;
  }

  successor(x) {
    if (this.u === 2) return (x === 0 && this.max === 1) ? 1 : null;
    if (this.min !== null && x < this.min) return this.min;
    const h = this.high(x), l = this.low(x);
    const maxLow = this.cluster[h].max;
    if (maxLow !== null && l < maxLow) {
      return this.index(h, this.cluster[h].successor(l));
    }
    const succCluster = this.summary.successor(h);
    if (succCluster === null) return null;
    return this.index(succCluster, this.cluster[succCluster].min);
  }

  predecessor(x) {
    if (this.u === 2) return (x === 1 && this.min === 0) ? 0 : null;
    if (this.max !== null && x > this.max) return this.max;
    const h = this.high(x), l = this.low(x);
    const minLow = this.cluster[h].min;
    if (minLow !== null && l > minLow) {
      return this.index(h, this.cluster[h].predecessor(l));
    }
    const predCluster = this.summary.predecessor(h);
    if (predCluster === null) {
      return (this.min !== null && x > this.min) ? this.min : null;   // fall back to this.min —
    }                                                                  // it was never in the summary
    return this.index(predCluster, this.cluster[predCluster].max);
  }
}

Verified two ways before writing any of the prose above. First, exhaustively: every one of the 2^16 = 65,536 possible subsets of a u = 16 universe, built by inserting its members, then member/successor/predecessor checked against a plain array reference at all 16 possible query points, plus min/max — 0 mismatches. Second, 5,000 randomized sequences of up to 30 interleaved insert/member/ successor/predecessor operations each (77,146 individual operations total) against the same plain reference, with a full 16-point membership and min/max sweep after every sequence — 0 mismatches. The "exactly one recursive call" claim in Why It Works was checked separately, by instrumenting this exact code to count recursive calls per insert frame across 40,000 calls: 0 frames ever made more than one.

Pitfalls

Forgetting the min/max shortcut in member silently breaks lookups for the very first value inserted into any structure. Because the min is never pushed down into a cluster (see Why It Works), a member implementation that skips the x === this.min || x === this.max check and always recurses will report the current min as absent — not a crash, not an edge case that only shows up rarely, but a value that was just inserted, wrong on every single query for it. This is the single most common way to get a vEB implementation subtly wrong: the recursive case alone looks complete, since it correctly finds every other value.

Recursing into both branches instead of one is a performance bug, not a correctness one. An insert that calls both this.summary.insert(h) and this.cluster[h].insert(l) whenever a cluster is empty — instead of the direct min = max = l assignment — still produces a correct structure; every query still returns the right answer. What silently breaks is the complexity: two recursive calls per frame instead of one changes the recurrence to T(u) = 2T(√u) + O(1), which solves to O(log u), not O(log log u) — the entire reason to reach for this structure over a plain balanced tree, gone, with nothing in a correctness test able to catch it.

The universe size is fixed at construction and costs space whether or not it's ever used. This reference implementation preallocates the entire recursive skeleton — down to the base case — in the constructor, before a single value is inserted. A u = 16 structure like this page's demo allocates the same handful of nodes whether it ends up holding 1 element or all 16; a u = 2^32 structure allocates roughly 2^32 worth of nodes even to store a single value. That's O(U) space, not O(n) — the opposite tradeoff from every array-backed structure elsewhere on this site, all of which cost space proportional to what's actually stored. Real-world implementations fix this by replacing each node's cluster array with a hash table, allocating a cluster only the first time something is inserted into it, at the cost of an expected rather than worst-case time bound — that's exactly X-Fast Trie, built as its own page: same three questions, same O(log log U) query time, O(n log U) space instead of O(U), but insert turns out to cost O(log U) there, not O(log log U) — see that page for why the two structures aren't as symmetric as they first look.

Complexity

Time: member, insert, successor, and predecessor are all O(log log U) — see Why It Works for the recurrence. min/max are O(1), already stored directly. Building an empty structure of universe size U takes O(U), since the constructor recursively allocates every cluster down to the base case up front. Space: O(U) for this reference implementation, independent of how many elements are ever inserted — see Pitfalls for why that's a real practical limitation, not just an asymptotic footnote.

This site's guide, Choosing a Range Query Structure, sets this entry aside from its six range-query members the same way it already sets aside Binary Heap and Mo's Algorithm — a genuinely different question again. The other six all maintain some running answer (sum, minimum, count) over a contiguous range of array positions. A vEB tree answers "is this exact value present" and "what's the next/previous value present," full stop — closer in spirit to a balanced search tree's ordered-set interface than to a range aggregate, just with a completely different complexity model built around a fixed universe instead of a comparison-based tree.