↩ back to Node-Linked Trees

Order Statistics Tree

Every one of this site's seven comparison-based search trees — Choosing a Search Tree lines them up — answers the same question: is x present? None of them, as built, can answer "what's the 5th-smallest value in this set" or "how many stored values are less than 37" without an O(n) walk of the whole tree. This, the site's 22nd Node-Linked Trees entry, isn't an eighth way to balance a tree — it's the same Treap from three entries back, with exactly one number added to every node: the size of the subtree rooted there. That single field, kept correct through every rotation, is enough to answer both queries in O(log n): select(k) returns the k-th smallest value, and rank(x) returns how many stored values are smaller than x. Nothing about when or how the tree rotates changes at all — the balancing mechanism and the order-statistics queries are completely independent of each other, which is the actual point of this page.

Try it

Loaded with the identical sequence treap.html's own demo uses — 1 through 7 inserted ascending, through the same seeded priority draws — so the tree below starts at the exact same shape (height 4, root 4) as that page's own worked example; adding the size field changes nothing about which rotations fire, only what else each node now knows about itself. Each node shows its value and, in small type, the size of its own subtree — the root's size is always the tree's total count. Try Select k=5: the walk compares k against the left subtree's size at each node, the same kind of binary decision a plain search makes by comparing keys, just comparing counts instead — it lands on 5, the actual 5th-smallest of {1..7}. Try Rank x=4: it should return 3 (exactly three stored values — 1, 2, 3 — are smaller than 4). Then try deleting 4, the current root, and running both queries again — sizes update immediately along every path a rotation touches, with no separate rebuild step.

Augmenting for order statistics

The general technique — CLRS calls it "augmenting a data structure" — works on any balanced binary search tree, not just a treap: pick a field whose value at any node can be recomputed in O(1) from that node's own two children (here, size = 1 + size(left) + size(right)), then recompute it at every node touched by every structural change. A treap's only structural changes are rotations, and a single rotation only changes the parent/child relationship between exactly two nodes — so fixing up size costs O(1) per rotation, recomputing the lower node first (its children are unchanged) and then the one that moved above it. Insert and delete are otherwise identical to plain treap insert/delete (see treap.html's own walkthrough) — bubble a new leaf up while it beats its parent's priority, or trickle a two-child target down toward its higher-priority child until it can be spliced out — with one added step: after any insert, walk back up the path fixing every ancestor's size; after any rotation during that bubble-up or during delete's trickle-down, fix the two rotated nodes' sizes immediately.

select(k) (1-indexed: k=1 means the smallest) starts at the root and, at each node, compares k against leftSize = size(node.left): if k equals leftSize + 1, this node itself is the answer; if k is no bigger than leftSize, the answer is somewhere in the left subtree, so recurse left with k unchanged; otherwise it's in the right subtree, so recurse right with k reduced by leftSize + 1 (skipping past everything already counted on the left, plus this node itself). rank(x) walks down comparing x against each node's own value: while x is less than or equal to the current node's value, that node and everything in its right subtree are too big to count, so go left with the running count unchanged; once x is strictly greater, this node and its entire left subtree are all smaller than x, so add size(left) + 1 to the running count and go right. Both are ordinary BST descents — one comparison per level, same shape as search — just comparing a count instead of a key at select's branch point, and accumulating a running total instead of returning a boolean at rank's.

Reference implementation

class OrderStatisticsTree {
  constructor(rng = Math.random) {
    this.root = null;
    this.rng = rng;
  }

  #size(n) { return n === null ? 0 : n.size; }
  #fix(n) { if (n !== null) n.size = 1 + this.#size(n.left) + this.#size(n.right); }

  #rotateRight(x) {
    const y = x.left;
    x.left = y.right;
    if (y.right !== null) y.right.parent = x;
    y.parent = x.parent;
    if (x.parent === null) this.root = y;
    else if (x === x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.right = x;
    x.parent = y;
    this.#fix(x); this.#fix(y);           // x first: its children are already settled
  }

  #rotateLeft(x) {
    const y = x.right;
    x.right = y.left;
    if (y.left !== null) y.left.parent = x;
    y.parent = x.parent;
    if (x.parent === null) this.root = y;
    else if (x === x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.left = x;
    x.parent = y;
    this.#fix(x); this.#fix(y);
  }

  insert(value) {
    if (this.root === null) {
      this.root = { value, priority: this.rng(), left: null, right: null, parent: null, size: 1 };
      return;
    }
    let cur = this.root, last = null;
    const path = [];
    while (cur !== null) {
      last = cur;
      path.push(cur);
      if (value === cur.value) return;                 // duplicates ignored
      cur = value < cur.value ? cur.left : cur.right;
    }
    const z = { value, priority: this.rng(), left: null, right: null, parent: last, size: 1 };
    if (value < last.value) last.left = z; else last.right = z;
    for (let i = path.length - 1; i >= 0; i--) this.#fix(path[i]);
    let x = z;
    while (x.parent !== null && x.priority > x.parent.priority) {
      if (x === x.parent.left) this.#rotateRight(x.parent);
      else this.#rotateLeft(x.parent);
    }
  }

  delete(value) {
    let cur = this.root;
    while (cur !== null && cur.value !== value) cur = value < cur.value ? cur.left : cur.right;
    if (cur === null) return false;
    while (cur.left !== null && cur.right !== null) {
      if (cur.left.priority > cur.right.priority) this.#rotateRight(cur);
      else this.#rotateLeft(cur);
    }
    const child = cur.left !== null ? cur.left : cur.right;
    if (child !== null) child.parent = cur.parent;
    if (cur.parent === null) this.root = child;
    else if (cur.parent.left === cur) cur.parent.left = child;
    else cur.parent.right = child;
    for (let p = cur.parent; p !== null; p = p.parent) this.#fix(p);
    return true;
  }

  select(k) {                                           // 1-indexed; undefined if k out of range
    let cur = this.root;
    while (cur !== null) {
      const leftSize = this.#size(cur.left);
      if (k === leftSize + 1) return cur.value;
      if (k <= leftSize) cur = cur.left;
      else { k -= leftSize + 1; cur = cur.right; }
    }
    return undefined;
  }

  rank(x) {                                             // count of stored values < x
    let cur = this.root, count = 0;
    while (cur !== null) {
      if (x <= cur.value) cur = cur.left;
      else { count += this.#size(cur.left) + 1; cur = cur.right; }
    }
    return count;
  }
}

The interactive demo above uses equivalent insertOST/deleteOST/ selectOST/rankOST functions with extra bookkeeping to record the descent path and which nodes' left-subtree sizes got folded into a rank count, purely to drive the highlighting and log text — the algorithm is identical. Verified from scratch against an independent oracle (a plain sorted array, rebuilt from a JavaScript Set after every operation): 3,000 randomized trials of 60 mixed insert/delete/select/rank operations each on a deliberately small value range (to force heavy rotation activity), checking after every single operation — 180,000 operations, 405,166 checks (BST order, heap order, parent pointers, every node's size field against a fresh recursive recount, root size against the reference set's own size, plus the actual select/rank answer against the sorted array), zero mismatches. Re-verified by extracting the exact shipped insertOST/ deleteOST/selectOST/rankOST functions out of the HTML and re-running an equivalent pass directly against them, plus a real click-driven fake-DOM harness confirming the two worked examples named above (select k=5 on the loaded tree returns 5; rank x=4 returns 3). See /tmp/ost/ref.js and /tmp/ost/stress.js, scratch, not committed.

Pitfalls

A rotation that forgets to fix up size leaves every other invariant intact — the corruption is invisible until something actually calls select or rank. BST order, heap order, and every parent pointer all stay perfectly correct if a rotation moves nodes around without touching their size fields, because none of those three checks ever looks at size at all — search, plain insert, and plain delete would keep working exactly as before, with no visible symptom. Checked against the real shipped code with the two #fix calls removed from both rotation functions: 2,000 seeded trials of 20 inserts each (enough to guarantee rotations fire) caught a real size-field mismatch in 1,971 of them the instant the tree was checked afterward — the 29 misses were simply trials whose random priorities happened not to trigger a single rotation, not cases where the bug failed to corrupt anything. A test suite that only checks BST/heap validity, the way plain treap's own verification does, would call every one of those 1,971 broken trees perfectly healthy.

rank's boundary comparison has to be non-strict on the "go left" branch, or it silently double-counts the queried value itself. Change x <= cur.value to the seemingly equivalent x < cur.value and every query for a value that's actually present in the tree breaks: when x equals the current node's own value, the broken comparison takes the "count and go right" branch instead of "go left," folding that node into the count as if it were smaller than x rather than equal to it. Measured directly: 2,000 seeded trials with that one-character change, checking rank of the just-inserted-or-just-deleted value after every operation where it was present — 35,990 checks, 35,990 mismatches, always off by exactly one. The fix is the same "which side does a tie belong to" question every binary-search- shaped routine on this site has to answer explicitly rather than guess.

Where it shows up

• C++'s GNU policy-based data structures (__gnu_pbds::tree). A standard-library-adjacent ordered set that ships this exact augmentation out of the box — order_of_key(x) and find_by_order(k) are this page's rank and select under different names — widely used in competitive programming specifically because a plain std::set has no way to ask either question without a linear scan.
• Running-median maintenance. Keep every seen value in an order statistics tree and call select(⌈size/2⌉) after each insert: an O(log n) running median, updated incrementally, instead of re-sorting or rebuilding a two-heap structure from scratch.
• The augmentation isn't tied to a treap specifically. Any balanced binary search tree can carry a subtree-size field the same way, as long as every structural change is local enough to fix up in O(1) — AVL and red-black rotations are exactly as local as a treap's. This page builds it on a treap for the same reason treap.html's own closing section gives for treaps in general: "one straightforward rotation loop with a single comparison to make," the simplest base to add one more field to.
• A different route to the same two answers: a Fenwick Tree over a pre-compressed value range. Binary lifting over the same prefix-sum structure Fenwick Tree already builds answers select and rank in O(log n) too — but only over a value universe that's known and compressed to a fixed range ahead of time. An order statistics tree has no such requirement: inserting a value nobody anticipated just becomes one more node.

Complexity

Time: select and rank are both O(log n) expected, the identical bound treap.html already establishes for search/insert/delete, since all four are one comparison per level down a treap whose balance the size field never influences. Measured directly, not just asserted: average node visits per select call on a randomly-built tree, against log₂(n) —

the same slowly-widening gap to the ideal treap.html's own height table measures for plain search, since select walks exactly the same root-to-node path search would for whichever node it lands on. Without the size field, the only way to answer either query is an O(n) full in-order walk — the entire reason to carry one extra integer per node. Space: O(n) — a treap's usual two child pointers, one parent pointer, and one priority, plus exactly one more integer per node for size.

This site's guide, Choosing a Search Tree, places this entry among the ones that answer a different question from plain membership.