Introduction

Suppose you have a sorted set of integers, all drawn from the universe {0,1,…,U−1}\{0, 1, \ldots, U-1\}, and you want to answer predecessor queries: given a key xx, find the largest stored integer that is ≤x\leq x.

A balanced binary search tree does this in O(log⁡n)O(\log n) time. A van Emde Boas tree does it in O(log⁡log⁡U)O(\log \log U) — doubly-logarithmic — but it needs O(U)O(U) space, which is ruinous when U=264U = 2^{64}.

In 1983, Dan Willard invented the y-fast trie, which achieves both goals at once: predecessor in O(log⁡log⁡U)O(\log \log U) time and O(n)O(n) space — linear in the number of stored elements, not the universe size. It is van Emde Boas speed without the astronomical memory price.

The trick is a two-layer design. The top layer is a compact x-fast trie that stores only O(n/log⁡U)O(n / \log U) representative elements. The bottom layer holds O(n)O(n) total elements spread across small balanced BSTs (one per representative). A query first locates the right cluster in O(log⁡log⁡U)O(\log \log U), then searches within a cluster of size O(log⁡U)O(\log U) in O(log⁡log⁡U)O(\log \log U) — both layers contribute the same bound.

Try It: Dynamic Predecessor

The demo below keeps a dynamic set of integers in the range [0,255][0, 255] (so U=256U = 256, log⁡U=8\log U = 8, log⁡log⁡U=3\log \log U = 3). Insert or delete values, then ask for the predecessor of any key.

<p class="hint">A dynamic set of integers from <b>[0, 255]</b> (U=256, log U=8, log log U=3).
    Insert or delete values, then find the <b>predecessor</b> of any key. The x-fast trie
    layer holds one representative per cluster of up to 8 elements.</p>
<div class="controls">
  <div class="row">
    <input id="valInput" type="number" min="0" max="255" placeholder="0–255" />
    <button id="btnInsert" type="button">Insert</button>
    <button id="btnDelete" type="button">Delete</button>
  </div>
  <div class="row">
    <input id="predInput" type="number" min="0" max="255" placeholder="Query key" />
    <button id="btnPred" type="button">Predecessor</button>
    <button id="btnReset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div id="status" class="status"></div>
<div id="trace" class="trace"></div>
<div id="visual" class="visual"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .7rem; }
.row { display: flex; gap: .45rem; flex-wrap: wrap; align-items: center; }
input[type=number] { width: 90px; padding: .38rem .5rem; border: 1px solid #bbb;
  border-radius: 6px; font-size: 14px; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-weight: 600; font-size: .95rem; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.trace { font-size: .82rem; color: #555; background: #f4f6f8; border-radius: 6px;
         padding: .5rem .7rem; min-height: 2.4em; margin-bottom: .6rem;
         font-family: ui-monospace, monospace; line-height: 1.6; white-space: pre-wrap; }
.visual { display: flex; flex-direction: column; gap: .4rem; }
.cluster-row { display: flex; align-items: center; gap: .35rem; flex-wrap: wrap; }
.cluster-label { font-size: .75rem; color: #777; width: 54px; text-align: right;
                 font-family: ui-monospace, monospace; flex-shrink: 0; }
.chip { display: inline-flex; align-items: center; justify-content: center;
        width: 32px; height: 28px; border-radius: 5px; font: 600 12px ui-monospace, monospace;
        border: 1px solid #cdd9e3; background: #e8eef3; color: #1d3557; }
.chip.rep { border-color: #457b9d; background: #d0e4f0; }
.chip.hi { background: #e63946; border-color: #c92f3c; color: #fff; }
.chip.pred-chip { background: #2a9d8f; border-color: #1d7a6f; color: #fff; }
.empty-row { font-size: .8rem; color: #aaa; font-style: italic; margin-left: 60px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Y-fast trie simulation: U=256, log U=8, cluster size = log U = 8.
// We maintain clusters (balanced BSTs simulated as sorted arrays).
// The x-fast trie layer is represented by a Map: representative -> cluster index.
// This demo focuses on the algorithmic behavior, not a pixel-perfect production impl.

const U = 256;
const LOG_U = 8;   // log2(256)
// Each cluster holds at most 2*LOG_U elements; target size LOG_U.
// Representative of a cluster = its maximum element.

// State: array of clusters, each cluster is a sorted array of integers.
let clusters = [];

function allElements() {
  return clusters.flatMap(c => c).sort((a,b)=>a-b);
}

function findCluster(val) {
  // Find the cluster whose representative (max) >= val (first such cluster).
  for (let i = 0; i < clusters.length; i++) {
    if (clusters[i][clusters[i].length - 1] >= val) return i;
  }
  return clusters.length; // beyond all clusters
}

function representative(cluster) {
  return cluster[cluster.length - 1];
}

function insert(val) {
  if (val < 0 || val >= U || !Number.isInteger(val))
    return { ok: false, msg: 'Value must be an integer in [0, 255].' };
  if (allElements().includes(val))
    return { ok: false, msg: fmt('%val% is already in the set.', { val: val }) };

  const trace = [];
  trace.push(fmt('Insert %val%', { val: val }));

  if (clusters.length === 0) {
    clusters.push([val]);
    trace.push("  " + fmt('Set was empty → created first cluster [%val%]', { val: val }));
    return { ok: true, msg: fmt('Inserted %val%.', { val: val }), trace };
  }

  let ci = findCluster(val);
  if (ci === clusters.length) {
    // val is larger than all representatives → goes into last cluster or new one
    ci = clusters.length - 1;
    trace.push("  " + fmt('val > all representatives → target last cluster (rep=%representative%)', { representative: representative(clusters[ci]) }));
  } else {
    trace.push("  " + fmt('x-fast lookup: first cluster with rep ≥ %val% is cluster %ci% (rep=%representative%)', { val: val, ci: ci, representative: representative(clusters[ci]) }));
  }

  // Insert into sorted cluster
  const cl = clusters[ci];
  let pos = cl.findIndex(x => x > val);
  if (pos === -1) pos = cl.length;
  cl.splice(pos, 0, val);
  trace.push("  " + fmt('Inserted into cluster %ci%: [%cl%]', { ci: ci, cl: cl.join(', ') }));

  // Split if oversized (> 2 * LOG_U)
  if (cl.length > 2 * LOG_U) {
    const mid = Math.floor(cl.length / 2);
    const left = cl.slice(0, mid);
    const right = cl.slice(mid);
    clusters.splice(ci, 1, left, right);
    trace.push("  " + fmt('Cluster too large (>%v%) → → split into [%left%] and [%right%]', { v: 2*LOG_U, left: left.join(','), right: right.join(',') }));
  }

  return { ok: true, msg: fmt('Inserted %val%.', { val: val }), trace };
}

function del(val) {
  if (val < 0 || val >= U || !Number.isInteger(val))
    return { ok: false, msg: 'Value must be an integer in [0, 255].' };

  const trace = [];
  trace.push(fmt('Delete %val%', { val: val }));

  let ci = findCluster(val);
  if (ci >= clusters.length || !clusters[ci].includes(val)) {
    return { ok: false, msg: fmt('%val% is not in the set.', { val: val }) };
  }
  trace.push("  " + fmt('Found in cluster %ci% (rep=%representative%)', { ci: ci, representative: representative(clusters[ci]) }));

  const cl = clusters[ci];
  const idx = cl.indexOf(val);
  cl.splice(idx, 1);
  trace.push("  " + fmt('Removed. Cluster %ci% now: [%v%]', { ci: ci, v: cl.length ? cl.join(', ') : 'empty' }));

  if (cl.length === 0) {
    clusters.splice(ci, 1);
    trace.push('  Cluster empty → removed.');
  } else if (cl.length < Math.floor(LOG_U / 2) && clusters.length > 1) {
    // Merge with neighbor
    if (ci > 0) {
      clusters[ci-1] = clusters[ci-1].concat(clusters[ci]).sort((a,b)=>a-b);
      clusters.splice(ci, 1);
      trace.push("  " + fmt('Cluster too small (<%floor%) → → merged with left neighbor.', { floor: Math.floor(LOG_U/2) }));
    } else {
      clusters[ci] = clusters[ci].concat(clusters[ci+1]).sort((a,b)=>a-b);
      clusters.splice(ci+1, 1);
      trace.push("  " + fmt('Cluster too small (<%floor%) → → merged with right neighbor.', { floor: Math.floor(LOG_U/2) }));
    }
  }

  return { ok: true, msg: fmt('Deleted %val%.', { val: val }), trace };
}

function predecessor(key) {
  if (key < 0 || key >= U || !Number.isInteger(key))
    return { ok: false, msg: 'Key must be an integer in [0, 255].' };

  const trace = [];
  trace.push('Predecessor(' + key + ')');

  if (clusters.length === 0)
    return { ok: false, msg: 'Set is empty.', trace };

  // Step 1: x-fast trie layer — find first cluster with rep >= key
  let ci = findCluster(key);
  trace.push("  " + fmt('Step 1 (x-fast layer): first cluster with rep ≥ %key%', { key: key }));

  let predVal = null;
  let predCluster = -1;

  if (ci < clusters.length) {
    const cl = clusters[ci];
    trace.push("    " + fmt('→ cluster %ci% [rep=%representative%]', { ci: ci, representative: representative(cl) }));
    // Step 2: local search within cluster
    const local = cl.filter(x => x <= key);
    if (local.length > 0) {
      predVal = local[local.length - 1];
      predCluster = ci;
      trace.push("  " + fmt('Step 2 (local BST search in cluster %ci%): max ≤ %key% is %predVal%', { ci: ci, key: key, predVal: predVal }));
    } else {
      trace.push("  " + fmt('Step 2: no element ≤ %key% in cluster %ci% → check previous cluster', { key: key, ci: ci }));
    }
  } else {
    trace.push('    → key > all representatives, check last cluster');
  }

  if (predVal === null && (ci === clusters.length || clusters[ci].filter(x=>x<=key).length===0)) {
    // Check previous cluster
    const prevCi = ci > 0 ? ci - 1 : -1;
    if (prevCi >= 0) {
      const cl = clusters[prevCi];
      const local = cl.filter(x => x <= key);
      if (local.length > 0) {
        predVal = local[local.length - 1];
        predCluster = prevCi;
        trace.push("  " + fmt('Step 2 (local BST search in cluster %prevCi%): max ≤ %key% is %predVal%', { prevCi: prevCi, key: key, predVal: predVal }));
      }
    } else if (ci >= clusters.length) {
      // Last cluster
      const cl = clusters[clusters.length - 1];
      const local = cl.filter(x => x <= key);
      if (local.length > 0) {
        predVal = local[local.length - 1];
        predCluster = clusters.length - 1;
        trace.push("  " + fmt('Step 2 (local BST search in last cluster): max ≤ %key% is %predVal%', { key: key, predVal: predVal }));
      }
    }
  }

  if (predVal === null) {
    trace.push("  " + fmt('No predecessor found (all elements > %key%).', { key: key }));
    return { ok: false, msg: fmt('No predecessor of %key% in the set.', { key: key }), trace };
  }

  trace.push("  " + fmt('Predecessor of %key% = %predVal%  (O(log log U) = O(3) steps)', { key: key, predVal: predVal }));
  return { ok: true, msg: fmt('Predecessor of %key% = %predVal%', { key: key, predVal: predVal }), trace, predVal, predCluster };
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg; el.className = 'status ' + (cls||'info');
}
function setTrace(lines) {
  document.getElementById('trace').textContent = lines.join('\n');
}

let lastPred = null;
let lastPredCluster = -1;

function render() {
  const vis = document.getElementById('visual');
  vis.innerHTML = '';
  if (clusters.length === 0) {
    const e = document.createElement('div');
    e.className = 'empty-row'; e.textContent = '(set is empty)';
    vis.appendChild(e); return;
  }
  clusters.forEach((cl, ci) => {
    const row = document.createElement('div');
    row.className = 'cluster-row';
    const lbl = document.createElement('div');
    lbl.className = 'cluster-label';
    lbl.textContent = 'C' + ci + ':';
    row.appendChild(lbl);
    cl.forEach((v, vi) => {
      const chip = document.createElement('div');
      const isRep = (vi === cl.length - 1);
      let cls = 'chip';
      if (ci === lastPredCluster && v === lastPred) cls += ' pred-chip';
      else if (isRep) cls += ' rep';
      chip.className = cls;
      chip.textContent = v;
      chip.title = isRep ? 'representative' : '';
      row.appendChild(chip);
    });
    vis.appendChild(row);
  });
}

function parseInput(id) {
  return parseInt(document.getElementById(id).value, 10);
}

document.getElementById('btnInsert').addEventListener('click', () => {
  const v = parseInput('valInput');
  const r = insert(v);
  setStatus(r.msg, r.ok ? 'ok' : 'bad');
  if (r.trace) setTrace(r.trace);
  lastPred = null; lastPredCluster = -1;
  render();
});

document.getElementById('btnDelete').addEventListener('click', () => {
  const v = parseInput('valInput');
  const r = del(v);
  setStatus(r.msg, r.ok ? 'ok' : 'bad');
  if (r.trace) setTrace(r.trace);
  lastPred = null; lastPredCluster = -1;
  render();
});

document.getElementById('btnPred').addEventListener('click', () => {
  const v = parseInput('predInput');
  const r = predecessor(v);
  setStatus(r.msg, r.ok ? 'ok' : 'bad');
  if (r.trace) setTrace(r.trace);
  lastPred = r.ok ? r.predVal : null;
  lastPredCluster = r.ok ? r.predCluster : -1;
  render();
});

document.getElementById('btnReset').addEventListener('click', () => {
  clusters = [];
  lastPred = null; lastPredCluster = -1;
  setStatus('', '');
  document.getElementById('trace').textContent = '';
  render();
});

// Seed with some initial values
[12, 25, 37, 58, 71, 89, 103, 120, 145, 160, 178, 200, 230, 247].forEach(v => insert(v));
setStatus('Set seeded with 14 values. Try predecessor(100) or insert your own.', 'info');
setTrace(['Ready. Insert values and query predecessor.']);
render();
Result
Console

Notice how the search never scans the whole sorted list. It first narrows down to the right cluster using a hash-table lookup on the representative keys — that is the x-fast trie layer. Then it does a tiny local search within a cluster that holds at most O(log⁡U)=8O(\log U) = 8 elements. Compare that with a binary search over all nn elements: here the cluster size is bounded by a constant of the universe, not by nn.

The Real Complexity

How do y-fast tries hit O(log⁡log⁡U)O(\log \log U) with only O(n)O(n) space? The proof uses two ingredients.

The x-fast trie (top layer). Store only O(n/log⁡U)O(n / \log U) representative keys — one per cluster — in a hash table keyed on binary prefixes. A predecessor query on the representatives takes O(log⁡log⁡U)O(\log \log U) time via binary search on the O(log⁡U)O(\log U) levels of the trie, each level checked in O(1)O(1) with a hash table. The total space for the representatives is O(n/log⁡U⋅log⁡U)=O(n)O(n / \log U \cdot \log U) = O(n).

The balanced BST clusters (bottom layer). Each cluster holds Θ(log⁡U)\Theta(\log U) consecutive elements. There are O(n/log⁡U)O(n / \log U) clusters, so the total number of elements across all clusters is O(n)O(n). A predecessor within a cluster of size Θ(log⁡U)\Theta(\log U) takes O(log⁡log⁡U)O(\log \log U) time.

Insertions and deletions cost O(log⁡log⁡U)O(\log \log U) amortized: when a cluster grows beyond 2log⁡U2 \log U elements, it splits; when it shrinks below 12log⁡U\frac{1}{2} \log U, it merges with a neighbor. Split/merge cost O(log⁡U)O(\log U) but happen so rarely that the amortized cost per operation is O(log⁡log⁡U)O(\log \log U).

The lower bound. Any comparison-based structure on nn integers from a universe of size UU requires Ω(log⁡log⁡U)\Omega(\log \log U) time per predecessor query in the worst case (proven by Fredman and Willard). So y-fast tries are optimal in this model.

This puts y-fast tries in a small club of data structures that are simultaneously time-optimal and space-optimal, beating the binary-search baseline of O(log⁡n)O(\log n) whenever log⁡n≫log⁡log⁡U\log n \gg \log \log U — which happens whenever n≫log⁡Un \gg \log U. For comparison, see sorting lower bounds and van Emde Boas / P vs NP for why such tight bounds matter.

Where It Matters

The predecessor query is more fundamental than it first appears. Many real systems reduce to exactly this problem on large integer universes:

  • IP routing: a router classifies packets by finding the longest-matching prefix in a 32- or 128-bit address space. Y-fast tries (and related structures) enable sub-microsecond lookup at line rate.
  • Event-driven simulation: the next event to fire is the predecessor of "now" in a priority queue keyed by timestamp. O(log log U) extraction keeps simulation throughput high.
  • Database range queries: B-trees answer range queries in O(log⁡n+k)O(\log n + k). When keys are dense integers, a y-fast trie beats the O(log⁡n)O(\log n) first step.
  • Competitive programming: problems that require a dynamic sorted set on integers with large universe size (2302^{30} or more) often accept an O(nlog⁡log⁡U)O(n \log \log U) solution where O(nlog⁡n)O(n \log n) times out.
  • Succinct data structures: the ideas behind y-fast tries — universe decomposition and clustered representation — appear in modern compressed indexes for genomic data and inverted indexes for search engines.

Whenever you have integers, a bounded universe, and repeated predecessor/successor queries, the y-fast trie is the go-to structure — the same ideas power the data structures inside every modern database and router.

Conclusion

Y-fast tries deliver a theorem that feels almost too good to be true: predecessor queries in O(log⁡log⁡U)O(\log \log U) time using only O(n)O(n) space — no compromise on either axis.

The key insight is separation of concerns: a tiny top layer of representatives handles universe navigation, while cheap bottom-layer clusters handle local search. Each layer does exactly what it is good at, and the costs multiply down to O(log⁡log⁡U)O(\log \log U).

The next time you see a sorted set of integers and someone reaches for a balanced BST, remember Willard's 1983 result: if the universe is bounded, you can do doubly logarithmically better, and you don't have to pay a byte extra for it. See also sorting lower bounds for why no integer structure can do better.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/y-fast-tries/Content licensed under CC BY-NC 4.0.