Augmenting Data Structures

By the end of this lesson you will be able to trace select and rankOf on an order-statistic tree, explain exactly why the size field can be kept correct in O(lg n) through both insertion and rotation without slowing the underlying tree down, apply a general four-step method to invent your own augmented data structure, trace intervalSearch on an interval tree and explain why it is safe to ignore whole subtrees, and implement the (n,m)-Josephus permutation in O(n lg n) using an order-statistic tree.

This lesson assumes you're comfortable with binary search trees (insert, search, rotations) from C12 and, ideally, why red-black trees keep height O(lg n) from C13. "Augmenting" means: you already have a working, well-understood data structure — here we use plain BSTs to demonstrate the technique, but in production you would augment a red-black tree so every operation stays O(lg n) — and you want to bolt EXTRA information onto it (a "sticky note" on every node) to answer a new kind of question, without breaking anything that already worked.

1. What does "augmenting" mean?

Imagine a library's shelving system (a binary search tree, ordered by title) that already supports "find this exact title" perfectly. Now your manager asks: "which volume is the 500th most popular title, by checkout count?" The shelving order can't answer that — it only knows alphabetical order. Rather than throwing out the shelves and building a totally new system, you staple a small sticky note to every shelf-section saying "this section holds N volumes total." Now, by reading sticky notes as you walk down the aisles, you can jump straight to the 500th volume without counting one by one. That sticky note is an augmented attribute; the walk-and-jump procedure is a new operation the augmentation makes possible.

This lesson does exactly that, twice. First it staples a size counter onto a search tree to answer "what's the i-th smallest key?" (an order-statistic tree, sections 2–5). Then it staples a max value onto a search tree to answer "does any stored interval overlap this one?" (an interval tree, sections 7–9). In between, section 6 distills both examples into one reusable four-step method for augmenting ANY data structure with ANY new attribute.

Augmenting always has the same shape: (1) keep the old structure and all its old operations working exactly as before, (2) add new field(s) to every node, (3) prove the new field(s) can be kept correct without slowing down the old operations, (4) write new operations that read the new field(s) to answer a question the old structure couldn't.

2. Order-statistic trees & the size attribute

The rank of a key is simply "if I lined up every key in the tree from smallest to largest, what position (1st, 2nd, 3rd, ...) would this one be in?" An order-statistic tree is a binary search tree where every node x also stores x.size = the number of nodes in the subtree rooted at x (including x itself). The missing-child sentinel nil has nil.size = 0.

The defining identity — true at every single node, always — is x.size = x.left.size + x.right.size + 1.

In Dart the sentinel nil (whose size is 0) becomes null, so "the size of a possibly missing child" is written x?.size ?? 0. First the node class, then the identity as a function that checks it at every node:

This is exactly like the library sticky note: "how many volumes are on MY shelf-section" = "volumes on my left half" + "volumes on my right half" + "me, if I'm a volume too." Because this identity only ever refers to a node and its two children (never anything further away), it stays cheap to maintain no matter how the tree changes shape (section 5 below).

Here is a 15-key order-statistic tree we'll use for every example in sections 3–5 (each circle shows key on top and size underneath):

The same 15-key tree as code (the building block every Dart demo on this page, and every example in the question bank, starts from):

The underlying tree drawn here is a plain, unbalanced BST — we chose an insertion order that happens to build a perfectly balanced shape so the pictures are easy to read. A REAL order-statistic tree augments the red-black tree of C13, which guarantees height O(lg n) no matter what order keys arrive in. The size-maintenance technique you're about to see is IDENTICAL either way — the local-dependency rule (section 5) is precisely the argument that it doesn't matter what balancing scheme sits underneath.

3. select: find the i-th smallest key

Back to the library: you want the 13th most-alphabetically-early volume. Stand at the root shelf-section. Read the sticky note on your LEFT half: it says how many volumes come before you alphabetically, within this section. If your target position matches "left-count + 1", you're standing on it right now. If your target is smaller, it's hiding in the left half — go there and ask the same question with the same target number. If it's bigger, it's in the right half — but you must first "use up" everything in your left half AND yourself, so subtract (left-count + 1) from your target before recursing right.

The pseudocode for select(x, i) (ranks count from 1: "the 1st smallest", "the 13th smallest"; x.left.size means 0 if x.left is nil):

Dart implementation. A rank is a counting position, not an array index, so i stays 1-based ("the 1st smallest", "the 13th smallest") while everything else works with pointers:

Input size → what is feasible. one query walks a single root-to-node path, at most the height h ≤ 2 lg(n+1): n = 10⁶ keys is at most 40 steps, so 10⁵ queries are 4·10⁶ steps (instant). Walking the in-order sequence to the i-th key instead costs up to n = 10⁶ steps per query — 10¹¹ for 10⁵ queries — so use select as soon as you ask more than a handful of queries.

Sentinel note: the pseudocode writes x.left.size and relies on nil.size = 0 always existing, so the expression never crashes. Dart has no sentinel object — null plays that role — so x.left.size becomes x.left?.size ?? 0 (read "size of the left child, or 0 if there is no left child"). Nothing else changes: the logic and recursion structure are identical.

Trace 1 — a normal case, finding the 13th smallest key of the 15-key tree above:

Trace 2 — an edge case, finding the very smallest key (i=1). Watch how this always walks the LEFT spine of the tree to the bottom, because at every node the answer "i=1 is smaller than my rank" is true until there's no left child left to check:

Now try any rank yourself on the same 15-key tree (valid ranks: 1–15):

Running time: each recursive call does O(1) work and moves one level down the tree, so select costs O(h) where h is the tree's height — O(lg n) on a red-black tree, but O(n) on a badly unbalanced plain BST (e.g. keys inserted in already-sorted order, which degenerates into a linked list). This is exactly why real order-statistic trees sit on a balanced tree.

select(x, i): O(h) = O(lg n) on a balanced tree. It never looks at more than one node per level — it always knows, from the size field alone, which single subtree could possibly contain the answer.

4. rankOf: find a key's rank

The reverse question: you're standing at a specific shelf (you already have a pointer to node x) and want to know your OWN alphabetical position among ALL volumes in the whole library, not just your local section. Count everyone on your left (your local rank), then walk up toward the root. Every time you climb up and discover you were the RIGHT child of your parent, that means your parent's entire left half — plus your parent itself — all come before you in the wider library; add all of them to your running count. If you were the LEFT child, nothing changes (everyone on the other side of your parent was already going to be bigger than you, so they don't get added).

The pseudocode for rankOf(t, x) (it needs parent pointers):

Dart implementation (the rank result is 1-based, exactly like select):

Input size → what is feasible. the loop climbs at most h ≤ 2 lg(n+1) parents (about 40 for n = 10⁶) and uses O(1) extra space; it needs parent pointers, which OsNode.parent provides.

Sentinel note: same ?.size ?? 0 substitution for the sentinel, plus y.parent! in Dart: the loop condition y != root already guarantees that y.parent exists inside the loop body, so asserting it with ! is safe.

Trace 1 — a normal case, finding the rank of key 65 in the same 15-key tree (walking up three levels):

Trace 2 — an edge case, finding the rank of the ROOT key (50). The while y ≠ t.root loop runs ZERO times — the rank is just the initial x.left.size + 1 computed at the very start, with no walking up needed at all:

Now pick any key that exists in the same 15-key tree and watch the walk-up:

Running time: the loop walks from x up to the root, one parent pointer per iteration, O(1) work each — so rankOf also costs O(h) = O(lg n) on a balanced tree, matching select exactly.

select answers "position → key"; rankOf answers "key (well, a node pointer to it) → position." Both cost O(h), and both rely on nothing but the size field plus normal tree pointers.

5. Maintaining size through insertion and rotation

Sticky notes are only useful if they stay accurate. Every time a volume is added to (or removed from) a shelf-section, every ANCESTOR section's sticky note must go up (or down) by exactly one — but sections that aren't ancestors are completely unaffected. And whenever the librarian reorganizes shelves (a rotation, swapping which section is "inside" which), only the TWO sections directly involved need their notes recomputed — everyone else's sticky note is still correct, untouched.

Insertion — an ordinary BST insert needs just one extra line (line 4 below) to also maintain size while descending to find where the new node belongs, plus z.size ← 1 for the new leaf:

In Dart (the same descent, with x.size++ on every node passed; the new leaf starts at size 1):

Input size → what is feasible. n = 10⁵ inserts into a balanced tree ≈ 10⁵×17 = 1.7·10⁶ size bumps. On a plain BST fed sorted keys the same code walks n²/2 = 5·10⁹ nodes, which is why a real order-statistic tree sits on the red-black tree.

Every node visited on the way down gets size + 1 (line 4); the brand-new leaf itself starts at size = 1 (line 17). That is O(h) extra work total — no slower, asymptotically, than the unaugmented insert.

Build your own order-statistic tree from scratch and watch every visited node's size tick up as each key is inserted (type any distinct integers, comma-separated):

Why size and not a global rank, in code: insert a new smallest key into a balanced tree and count how many stored values would have to change under each choice:

Notice this is why the attribute to store is size, not a global rank (storing each node’s rank within its own subtree is a different, workable idea, because that depends only on the subtree): if node x stored "my rank in the whole tree," then inserting a new SMALLEST key would force updating the rank of literally every other node — O(n) work, not O(lg n). Size only ever needs updating along the O(h)-long path from the root to wherever the change happened, because a node's size never depends on anything outside its own subtree.

Rotation — the rotation from the red-black lesson needs exactly two extra lines (14–15) to fix up size, and remarkably, only the two nodes directly involved in the rotation ever need their size recomputed — never any node further away, and never a walk up to the root:

Dart implementation (the pointer names x.parent / nil become x.parent / null; otherwise line-for-line identical):

Watch leftRotate(x) on a small 5-node subtree — notice y.size just COPIES the old x.size (an O(1) shortcut: the whole subtree's total node count obviously can't change from a rotation, so whatever x used to cover, y now covers), while x.size is freshly recomputed from its NEW children:

rightRotate is the exact mirror image. Watch it applied to the tree leftRotate just produced — restoring the original shape and the original sizes exactly:

In Dart (mirror image; lines 14–15 again fix the two sizes):

Input size → what is feasible. a rotation costs O(1) at any n: two size fields are rewritten (y.size copies the old subtree total, x.size is recomputed from its new children).

The local-dependency rule as code. An Augmentation is just a function of a node and its two children's values; AugTree keeps it correct through insert, delete and left-rotate by calling refresh on the nodes whose children changed. The same tree class below is used with three different attributes (size, sum of keys, height), and the stored values are checked against a from-scratch recomputation at every node:

The local-dependency rule: if an attribute f at node x can be computed using ONLY x, x.left and x.right (and, through them, x.left.f and x.right.f), then insertion and deletion can maintain f at every node without changing a balanced tree's O(lg n) running time. Size fits this pattern exactly (the identity in section 2). Why it works: a change to some node's f can only affect that node's ancestors, and there are only O(lg n) of them. For MANY attributes, including size, a rotation is even cheaper: O(1), because only the two rotated nodes actually change.

Size survives insertion in O(h) total extra work (one increment per node on the descent path) and survives each rotation in O(1) extra work (recompute exactly 2 nodes). Neither slows down the O(lg n) red-black tree operations from the previous lesson.

6. The general method: four steps to augment anything

Everything you just watched happen to the size field fits into a checklist you can reuse for ANY new attribute on ANY data structure — a future min-gap field, a sum field, a count-of-red-nodes field, anything.

Pick the base structure. For order-statistic trees: a red-black tree (a plain BST here, for teaching). For interval trees (section 7): also a red-black tree, keyed differently.
Decide what extra information every node should carry. For order-statistic trees: size. For interval trees: max.
Check that the existing modifying operations can keep that information correct. This is exactly section 5's work: show insert, delete and rotate can all keep the new field correct without hurting the O(lg n) time bound — usually by checking the field depends only on a node and its two children (the local-dependency rule).
Write the new operations the augmentation was built for. For order-statistic trees: select and rankOf. For interval trees: intervalSearch (section 8).

These four steps are NOT always done strictly in order — real design work bounces between them. You might pick a candidate attribute (step 2), realize step 3 fails (it can't be maintained cheaply), and go back to pick a different attribute. Storing a global rank instead of size (section 5's pitfall) is exactly a step-2 choice that FAILS step 3.

Steps 1–2 are design choices; step 3 is a correctness-and-efficiency PROOF obligation (don't skip it — a beautiful new operation built on a field that can't actually be kept correct is worthless); step 4 is where you finally get the payoff.

7. Interval trees & the max attribute

Now apply the SAME four-step method to a completely different problem: a calendar app holding many reserved meetings, each a closed time interval [low, high] (both endpoints included). You want to instantly answer "does ANY existing meeting overlap this new one I'm about to reserve?" A plain BST keyed by start time can't answer this by itself — you'd have to check every meeting one by one, O(n).

Two intervals overlap exactly when i.low ≤ j.high AND j.low ≤ i.high. The interval trichotomy says every pair of intervals is in EXACTLY ONE of three relationships: they overlap, or i is entirely to the left of j (i.high < j.low), or i is entirely to the right (j.high < i.low).

Applying the four-step method: (1) base structure = a red-black tree keyed by each interval's low endpoint (a plain BST here, as with order-statistic trees above); (2) new field: x.max = the largest HIGH endpoint anywhere in the subtree rooted at x, i.e. max(x.high, x.left.max, x.right.max); (3) shown in section 9 below, by the same local-dependency reasoning as size; (4) intervalSearch, next.

Here are 10 intervals stored in an interval tree, keyed by low endpoint (each box shows [low,high] on top, max underneath):

8. intervalSearch

Standing at a node, ask: does MY interval overlap the query? If yes, done — return it (the search only promises to find SOME overlap, not all of them, and not necessarily the "best" one). If no: look at your left child's max sticky note. If it's smaller than the query's low endpoint, then EVERY interval in your entire left subtree ends too early to possibly overlap — skip the whole subtree, go right. Otherwise, some interval over there MIGHT reach far enough — go left (and the correctness argument below shows this choice never wrongly misses an overlap elsewhere).

The pseudocode for intervalSearch(t, i):

Dart implementation (low/high are plain integers; nil becomes null):

Input size → what is feasible. intervalSearch follows one root-to-leaf path: h ≤ 2 lg(n+1) ≈ 40 steps for n = 10⁶ intervals, so 10⁵ queries are 4·10⁶ steps. Scanning all n intervals per query would be 10¹¹. To list ALL k overlaps instead of one, a pruned walk costs O(min(n, k lg n)).

Sentinel note: intervals themselves don't have an indexing convention — low/high are just integers, identical in both languages. The only change is the sentinel-to-null substitution, same as every other procedure in this lesson.

Trace 1 — a normal, successful search for any interval overlapping [26,28]:

Trace 2 — an edge case: an UNSUCCESSFUL search for [15,16], which overlaps nothing in the tree. Watch the loop terminate at a null child rather than looping forever:

Now build your own interval tree (comma-separated low-high pairs) and search it with your own query interval:

Fact B (safe skipping): intervalSearch either returns a node overlapping the query, or returns nil and NO node in the whole tree overlaps the query. Proof idea (loop invariant): "if the tree contains an interval overlapping the query, then the subtree rooted at the current x contains one." Going right is only chosen when either the left child doesn't exist, or its max < i.low — and by the interval trichotomy, EVERY interval with a high endpoint that small must lie entirely to the query's left, so it can never overlap; the invariant survives. Going left is chosen when x.left.max ≥ i.low, meaning some interval j achieving that max reaches far enough that, combined with the tree being keyed by low endpoint, everything in the RIGHT subtree must start even later than j does — so if an overlap exists anywhere reachable from here, it's safe to say it's in the left subtree (or was x itself, already ruled out). Termination at nil then proves NOTHING overlaps, by the contrapositive of the invariant.

Fact B as code. The loop invariant "if the tree holds an overlap, then the subtree rooted at the current x holds one" is asserted at the top of every iteration, and the two ways the loop can end are checked (the returned node overlaps, or NIL is returned only when nothing overlaps):

intervalSearch costs O(h) = O(lg n) — exactly one root-to-leaf path, just like select and rankOf — because the max field lets it discard an entire subtree with one O(1) comparison instead of ever having to look inside it.

9. Maintaining max through insertion and rotation

Exactly the same pattern as size (section 5): the BST insert gains two extra lines to extend max along the descent path,

In Dart (a node on the way down extends its max if the new interval reaches further; the new node starts with max = high):

and the rotation gains two extra lines — but this time y.max can still just copy the OLD x.max directly (an interval's max endpoint over a whole subtree doesn't change just because the subtree's internal shape changed), while x.max must be recomputed from its new children plus its own high endpoint:

Watch leftRotate fix up max on a small interval subtree:

Deleting an interval: an ordinary BST delete, then recompute max on the path from the first changed spot to the root, exactly like the order-statistic delete recomputes size in section 10. The extra parent walk costs O(h):

Input size → what is feasible. Interval insert and delete are O(h) = O(lg n) on a balanced tree: n = 10⁶ updates ≈ 4·10⁷ steps. Rotations cost O(1) each, so the red-black fixups add nothing asymptotically.

Another augmentation: the point of maximum overlap. Keep, for every node of a tree over the coordinate range, the deepest overlap anywhere below it; max = add + max(left.max, right.max) is again a function of the node and its two children. Used by the My Calendar questions below, with coordinates up to 10⁹:

max satisfies the same local-dependency rule as size (it depends only on a node, its own high endpoint, and its two children's max) — so it survives insertion in O(h) total and each rotation in O(1), exactly like size did.

10. The Josephus permutation via an order-statistic tree

The (n,m)-Josephus permutation: n people stand in a circle, numbered 1..n. Starting the count at person 1, count off m people around the (shrinking) circle and remove the m-th; keep going, always continuing the count from wherever you left off, until everyone is gone. The order people are removed in is the "Josephus permutation." Example for (n,m) = (9,4): the removal order is ⟨4,8,3,9,6,5,7,2,1⟩.

There are two natural algorithms: (a) an O(n) method when m is a CONSTANT (a circular linked list works directly), and (b) an O(n lg n) method for a general (not constant) m — which is exactly an order-statistic tree in disguise! Seat the n people as the n keys of an order-statistic tree (in-order position = seat position). Finding "the next person to eliminate, counting m around from wherever we are" is precisely a select call on a computed rank; removing them is a delete that also fixes sizes. Both cost O(lg n), and we do it n times.

The tricky part is the size-aware delete: it's an ordinary BST delete (three cases: no children / one child / two children) with one addition: after splicing the structure back together, walk from the point of change up to the root, recomputing size = left.size + right.size + 1 at each ancestor — O(h) total, same bound as everything else in this lesson.

With that delete in hand, the whole Josephus algorithm (with the O(n) circular-list reference it is checked against, and the balanced build of the starting tree):

Input size → what is feasible. n = 10⁵ people with m up to 10⁹ → n rounds × (one select + one delete ≈ 2×17 steps) ≈ 3.4·10⁶ steps. The circular-list simulation walks m steps per removal (up to 10¹⁴ in total) and List.removeAt is O(n) per removal (n² = 10¹⁰), so it only suits small n or constant m.

Trace 1 — the worked example, (n,m) = (9,4):

Trace 2 — an edge case, m = 1: counting off just 1 person every time removes everyone in their ORIGINAL seat order, with no skipping at all:

Now try your own circle size and count — n from 2–20, m from 1–20:

Why is this O(n lg n) overall and not O(n lg² n) or worse? Each of the n rounds does exactly one select (O(lg n)) and one delete (O(lg n)) — O(lg n) per round, n rounds, O(n lg n) total. verify/c14.dart checks this algorithm against a brute-force circular-list simulation on 300 random (n,m) pairs and confirms they always agree.

A subtle detail worth noticing in the animation: after removing a person, the "next count starts from" position does NOT reset to 1 — it continues from wherever the just-removed rank was (with wraparound, since the circle shrank by one). Get this wrong (e.g. always restart counting from rank 1) and you'll silently compute a completely different, wrong permutation that still "looks like an algorithm ran" — the kind of bug that's easy to miss without a brute-force cross-check.

The Josephus problem is a good capstone for the whole lesson: it takes the FIRST augmented structure (the order-statistic tree) and combines select with a new operation (a size-aware delete) to solve a problem that has nothing to do with "order statistics" on the surface — a reminder that once a structure is augmented, its new powers compose with everything else a tree can already do.

Quiz

Interview questions

Cheat sheet

Structure / operation	Time	Space (extra)	Notes
Order-statistic tree: extra field	—	O(1) per node (one int)	x.size = x.left.size + x.right.size + 1
select(x, i)	O(h) = O(lg n) balanced	O(h) recursion stack	i is a 1-based rank, not an array index
rankOf(t, x)	O(h) = O(lg n) balanced	O(1)	needs parent pointers; walks up, not down
Size maintenance on insert	O(h) total extra	O(1) per node visited	+1 on every node along the descent path
Size maintenance on rotation	O(1)	O(1)	only the 2 rotated nodes change — no walk to root needed
Local-dependency rule (general augmentation)	O(lg n) per update	—	works for ANY field depending only on a node + its 2 children
Interval tree: extra field	—	O(1) per node (one int)	x.max = max(x.high, x.left.max, x.right.max); keyed by LOW endpoint
intervalSearch(t, i)	O(h) = O(lg n) balanced	O(1)	finds SOME overlap or proves none exists — not "the best" overlap
Max maintenance on insert / rotation	O(h) total / O(1)	O(1)	identical pattern to size
(n,m)-Josephus, constant m	O(n)	O(n)	direct circular linked list simulation
(n,m)-Josephus, general m via order-statistic tree	O(n lg n)	O(n)	n rounds × (select + delete), each O(lg n)