Introduction

A binary search tree keeps things sorted: every left child has a smaller key, every right child has a larger one. But a plain BST is only as good as the order items arrive. Insert them in sorted order and you get a linked list, not a tree — every lookup now costs O(n)O(n) instead of O(log⁡n)O(\log n).

To fix that, you need the tree to stay balanced. AVL trees and red-black trees do it with elaborate rotation rules and extra color or height bits on every node. Those algorithms work, but they are notoriously subtle to implement correctly.

A treap takes a completely different route. Give each node a second field called its priority — a uniformly random number drawn when the node is created. Now enforce two invariants simultaneously:

  • BST property on keys: left subtree keys < node key < right subtree keys.
  • Max-heap property on priorities: every parent has a higher priority than its children.

Aragon and Seidel proved in 1989 that these two rules together force the tree's shape to be the unique binary search tree consistent with both orderings — and because priorities are random, the expected height is O(log⁡n)O(\log n).

No rotation counters, no color bits, no rebalancing passes. Randomness does the work.

Try It: Split and Merge

The two fundamental treap operations are split and merge. Split divides the treap into two treaps (keys ≤ threshold and keys > threshold). Merge fuses them back, restoring both invariants.

<p class="hint">A treap stores each node's <b>key</b> (BST order, shown in the box) and a random <b>priority</b> (smaller number = higher priority, shown in blue below the key). Use <b>Insert</b> to add a key, <b>Split</b> to divide at a threshold, and <b>Merge</b> to reunite.</p>
<div class="controls">
  <label>Key: <input id="key-in" type="number" min="1" max="99" value="50" style="width:52px"></label>
  <button id="btn-insert">Insert</button>
  <span class="sep">|</span>
  <label>Split ≤ <input id="split-in" type="number" min="1" max="99" value="40" style="width:52px"></label>
  <button id="btn-split">Split</button>
  <button id="btn-merge" disabled>Merge back</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>
<div id="msg" class="msg"></div>
<div id="canvas-wrap"><canvas id="cv" width="680" height="280"></canvas></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .9rem; }
input[type=number] { font: inherit; padding: .2rem .3rem; border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.sep { color: #aaa; }
.msg { font-size: .93rem; font-weight: 600; min-height: 1.3em; margin-bottom: .3rem; }
.msg.ok  { color: #0a7d33; }
.msg.bad { color: #c92f3c; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; background: #f7f9fb; border-radius: 10px; border: 1px solid #dde3ea; max-width: 100%; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Treap: each node has a key (BST invariant) and a random priority (max-heap invariant).
// Core operations: split(t, x) -> [left, right] where left.key <= x < right.key
//                  merge(l, r) -> treap where all l.key < r.key
// Both run in O(log n) expected time.

let uid = 0;
function node(key) {
  return { key, prio: Math.floor(Math.random() * 1000), left: null, right: null, id: ++uid };
}

// split: returns [left, right] where left has keys <= x, right has keys > x
function split(t, x) {
  if (!t) return [null, null];
  if (t.key <= x) {
    const [rl, rr] = split(t.right, x);
    return [{ ...t, right: rl }, rr];
  } else {
    const [ll, lr] = split(t.left, x);
    return [ll, { ...t, left: lr }];
  }
}

// merge: all keys in l must be < all keys in r
function merge(l, r) {
  if (!l) return r;
  if (!r) return l;
  if (l.prio >= r.prio) {
    return { ...l, right: merge(l.right, r) };
  } else {
    return { ...r, left: merge(l, r.left) };
  }
}

function insert(t, key) {
  const [l, r] = split(t, key - 1);
  return merge(merge(l, node(key)), r);
}

// ── State ─────────────────────────────────────────────────────────────────
let root = null;
let splitLeft = null, splitRight = null;
let isSplit = false;

// Seed with a few initial nodes
[20, 50, 10, 35, 65, 80].forEach(k => { root = insert(root, k); });

// ── Drawing ───────────────────────────────────────────────────────────────
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
const NODE_R = 22;

function treeSize(t) { return t ? 1 + treeSize(t.left) + treeSize(t.right) : 0; }

// Assign x positions via in-order traversal
function assignX(t, counter) {
  if (!t) return counter;
  counter = assignX(t.left, counter);
  t._x = counter++;
  counter = assignX(t.right, counter);
  return counter;
}

// Assign y by depth
function assignY(t, depth) {
  if (!t) return;
  t._depth = depth;
  assignY(t.left, depth + 1);
  assignY(t.right, depth + 1);
}

function drawTree(t, parent, xOff, color) {
  if (!t) return;
  const x = xOff + t._x * 52 + 26;
  const y = 24 + t._depth * 60;
  t._px = x; t._py = y;

  if (parent) {
    ctx.beginPath();
    ctx.moveTo(parent._px, parent._py + NODE_R);
    ctx.lineTo(x, y - NODE_R);
    ctx.strokeStyle = '#aab';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }

  // Node circle
  ctx.beginPath();
  ctx.arc(x, y, NODE_R, 0, Math.PI * 2);
  ctx.fillStyle = color;
  ctx.fill();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 1.5;
  ctx.stroke();

  // Key
  ctx.fillStyle = '#1d3557';
  ctx.font = 'bold 13px ui-monospace, monospace';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  ctx.fillText(t.key, x, y - 3);

  // Priority (smaller = higher)
  ctx.fillStyle = '#2a6db5';
  ctx.font = '10px ui-monospace, monospace';
  ctx.fillText('p' + t.prio, x, y + 10);

  drawTree(t.left, t, xOff, color);
  drawTree(t.right, t, xOff, color);
}

function render() {
  ctx.clearRect(0, 0, W, H);

  if (!isSplit) {
    if (!root) {
      ctx.fillStyle = '#999';
      ctx.font = '14px system-ui';
      ctx.textAlign = 'center';
      ctx.textBaseline = 'middle';
      ctx.fillText('Tree is empty. Insert some keys!', W / 2, H / 2);
      return;
    }
    assignX(root, 0);
    assignY(root, 0);
    drawTree(root, null, 10, '#dbeafe');
  } else {
    // Draw left treap (green tint) and right treap (red tint) side by side
    const lSize = treeSize(splitLeft);
    const rSize = treeSize(splitRight);
    const lWidth = lSize * 52 + 20;

    if (splitLeft) {
      assignX(splitLeft, 0);
      assignY(splitLeft, 0);
      drawTree(splitLeft, null, 10, '#d1fae5');
      // Label
      ctx.fillStyle = '#065f46';
      ctx.font = 'bold 12px system-ui';
      ctx.textAlign = 'left';
      ctx.textBaseline = 'top';
      ctx.fillText('Left (keys ≤ split)', 12, 4);
    }

    if (splitRight) {
      const xOff = splitLeft ? lWidth + 10 : 10;
      assignX(splitRight, 0);
      assignY(splitRight, 0);
      drawTree(splitRight, null, xOff, '#fee2e2');
      ctx.fillStyle = '#7f1d1d';
      ctx.font = 'bold 12px system-ui';
      ctx.textAlign = 'left';
      ctx.textBaseline = 'top';
      ctx.fillText('Right (keys > split)', xOff + 2, 4);
    }

    if (!splitLeft && !splitRight) {
      ctx.fillStyle = '#999';
      ctx.font = '14px system-ui';
      ctx.textAlign = 'center';
      ctx.textBaseline = 'middle';
      ctx.fillText('Both halves are empty.', W / 2, H / 2);
    }
  }
}

// ── Validation ────────────────────────────────────────────────────────────
function validateBST(t, min, max) {
  if (!t) return true;
  if (t.key < min || t.key > max) return false;
  return validateBST(t.left, min, t.key - 1) && validateBST(t.right, t.key + 1, max);
}
function validateHeap(t) {
  if (!t) return true;
  if (t.left && t.left.prio > t.prio) return false;
  if (t.right && t.right.prio > t.prio) return false;
  return validateHeap(t.left) && validateHeap(t.right);
}

function msg(text, cls) {
  const el = document.getElementById('msg');
  el.textContent = text;
  el.className = 'msg ' + (cls || '');
}

// ── Button handlers ───────────────────────────────────────────────────────────
document.getElementById('btn-insert').addEventListener('click', () => {
  if (isSplit) { msg('Merge first before inserting.', 'bad'); return; }
  const k = parseInt(document.getElementById('key-in').value, 10);
  if (isNaN(k) || k < 1 || k > 99) { msg('Key must be 1–99.', 'bad'); return; }
  root = insert(root, k);
  const bst = validateBST(root, -Infinity, Infinity);
  const heap = validateHeap(root);
  msg(fmt('Inserted %k%. BST: %v%  Heap: %v2%', { k: k, v: bst ? '✓' : '✗', v2: heap ? '✓' : '✗' }), bst && heap ? 'ok' : 'bad');
  render();
});

document.getElementById('btn-split').addEventListener('click', () => {
  if (isSplit) { msg('Already split — merge first.', 'bad'); return; }
  const x = parseInt(document.getElementById('split-in').value, 10);
  if (isNaN(x) || x < 1 || x > 99) { msg('Split threshold must be 1–99.', 'bad'); return; }
  [splitLeft, splitRight] = split(root, x);
  root = null;
  isSplit = true;
  document.getElementById('btn-merge').disabled = false;
  const lKeys = [];
  function collect(t) { if (!t) return; collect(t.left); lKeys.push(t.key); collect(t.right); }
  const rKeys = [];
  function collectR(t) { if (!t) return; collectR(t.left); rKeys.push(t.key); collectR(t.right); }
  collect(splitLeft);
  collectR(splitRight);
  msg(fmt('Split at %x%. Left: [%v%]   Right: [%v2%]', { x: x, v: lKeys.join(', ') || '∅', v2: rKeys.join(', ') || '∅' }), 'ok');
  render();
});

document.getElementById('btn-merge').addEventListener('click', () => {
  if (!isSplit) return;
  root = merge(splitLeft, splitRight);
  splitLeft = splitRight = null;
  isSplit = false;
  document.getElementById('btn-merge').disabled = true;
  const bst = validateBST(root, -Infinity, Infinity);
  const heap = validateHeap(root);
  msg(fmt('Merged! BST: %v%  Heap: %v2%', { v: bst ? '✓' : '✗', v2: heap ? '✓' : '✗' }), bst && heap ? 'ok' : 'bad');
  render();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  root = null; splitLeft = null; splitRight = null; isSplit = false;
  document.getElementById('btn-merge').disabled = true;
  [20, 50, 10, 35, 65, 80].forEach(k => { root = insert(root, k); });
  msg('Reset to default tree.', 'ok');
  render();
});

render();
msg('Tree seeded with 6 random-priority nodes.', 'ok');

// Log validation result to console for external verification
console.log('Initial BST valid:', validateBST(root, -Infinity, Infinity));
console.log('Initial Heap valid:', validateHeap(root));
Result
Console

Notice how the tree reorganizes after every operation yet always satisfies both invariants. Checking that a tree is a valid treap takes O(n)O(n) — just walk every node and verify the BST and heap conditions. Building an optimal balanced BST from scratch without randomness is harder (see binary search trees and dynamic shortest paths for related ideas about optimal structure).

The Real Complexity

How fast are treap operations?

  • Search, insert, delete: all run in O(log⁡n)O(\log n) expected time. The expected height of a random treap on nn keys is at most 4.3ln⁡n4.3 \ln n, a consequence of the priorities forming a random permutation.
  • Split and merge: also O(log⁡n)O(\log n) expected time. Split follows a root-to-leaf path determined entirely by the threshold key and the heap invariant. Merge races two paths simultaneously and picks the higher-priority root at each step.
  • Worst-case: O(n)O(n) — a pathological priority draw can produce a skewed tree, just as quicksort can degenerate. But the probability of the tree exceeding height clog⁡nc \log n drops exponentially in cc.
  • Proven result (Aragon & Seidel, 1989): the expected number of rotations to insert or delete a node is exactly 2. This is the source of treaps' practical speed.

Compared to deterministic alternatives:

Structure Worst-case height Balance mechanism Complexity to implement
Unsorted BST O(n)O(n) None Trivial
AVL tree O(log⁡n)O(\log n) Height bookkeeping + rotations High
Red-black tree O(log⁡n)O(\log n) Color rules + rotations Very high
Treap O(n)O(n) w.h.p. O(log⁡n)O(\log n) Random priorities Low

The treap trades a deterministic worst-case guarantee for a probabilistic one — and wins on simplicity, which matters enormously in practice.

Where It Matters

The split/merge primitive makes treaps unusually versatile:

  • Order-statistics tree: augment each node with its subtree size. Then finding the kk-th smallest element or the rank of any key costs O(log⁡n)O(\log n), exactly as in a balanced BST — but with a simpler codebase.
  • Persistent treaps: because split and merge create new nodes rather than modifying existing ones, making them persistent (keeping all past versions alive) costs only one extra pointer per node. This is the backbone of functional ordered sets in languages like Haskell.
  • Rope data structure: represent a long string as a treap on character indices. Substring insertion, deletion, and concatenation all become treap merges and splits — each O(log⁡n)O(\log n) instead of O(n)O(n) for a flat array.
  • Competitive programming: treaps are a contest staple because they replace segment trees, interval trees, and sorted sets with a single data structure and roughly 50 lines of code. See also binary search for the sorted-order guarantees they rely on.
  • Implicit treap: use the subtree size as the implicit key (no explicit key stored). This turns the treap into a sequence data structure that supports O(log⁡n)O(\log n) split, merge, and arbitrary indexed access — more powerful than a doubly linked list and faster than a balanced BST for positional queries.

The unifying theme: once you have O(log⁡n)O(\log n) split and merge, almost any sequence or set operation reduces to a small composition of those two primitives.

Conclusion

The treap's insight is almost embarrassingly simple: let randomness do the balancing. Add one random number to each node, obey the heap invariant, and the resulting tree is expected to be as flat as any hand-balanced structure — with far less code.

Split and merge make this structure genuinely powerful. Nearly every ordered-set or sequence operation reduces to a composition of those two primitives, which means a treap can replace half a dozen specialized data structures without sacrificing asymptotic performance.

The next time you reach for an AVL tree or a red-black tree and dread the implementation, remember: a coin flip per node might be all you need. That is the lesson the treap has quietly been teaching since 1989.

Share this article

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

Comments

Loading comments...

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