Store the size of each subtree at its root and a search tree answers two new questions in O(log n): the rank of a key, and the i-th smallest key. The rule for what else can be added is sharp — any attribute computable from a node’s own key and its two children’s attributes in constant time. A median field is not one. And every rotation must update the field, or it goes quietly stale.
Core ideas
One mechanism, one criterion, and one maintenance obligation. The criterion is what makes this a technique rather than a trick, and the obligation is where it breaks in practice.
At a node, the size of the left subtree tells you how many keys are smaller than this one within this subtree. That single number converts the search-tree walk into an arithmetic walk: select subtracts as it goes right, rank accumulates as it goes right, and both finish in one root-to-leaf path.
The criterion is constant-time computability from the node’s own key and the attribute values at its two children. Size qualifies: 1 + left + right. So do sum, min, max, and the count of keys satisfying a fixed predicate. A median does not: knowing the medians of two subtrees and one key does not determine the median of the whole, so maintaining it would cost more than a constant per node and the technique gives nothing.
An insertion increments the size at each node on its path. A rotation rearranges three subtrees and must recompute the sizes at the two nodes involved, bottom-up. Forget it and the field is wrong while the tree is correct, which means select returns the wrong key and nothing complains. The lab rotates a size-annotated tree and prints the sizes before and after for exactly that reason.
The material
How select and rank walk, what a range count costs, which attributes are maintainable, and what a rotation has to do.
A search tree in which every node x stores size[x] = size[left(x)] + size[right(x)] + 1, the number of nodes in the subtree rooted at x. An empty subtree has size 0.
The field costs one machine word per node and is maintained by insertion, deletion and rotation. Nothing else about the tree changes.
select(i), the i-th smallest key, counting from 1. At a node, let L be the size of its left subtree. If i = L + 1 the answer is this node’s key, because exactly L keys in this subtree are smaller. If i ≤ L the answer is in the left subtree at the same rank. Otherwise it is in the right subtree at rank i − (L + 1), because the left subtree and this node account for L + 1 of the keys below it.
rank(k), how many keys are at most k. Walk toward k from the root, keeping a running count. Each time the walk goes right, every key in the left subtree and the node itself are below k, so add L + 1. Each time it goes left, add nothing. When k is found, add L + 1 one last time.
Four nodes for select(3) and three for rank(62), on a tree of height 3. Both walks are one path and nothing else, which is the whole claim: O(height), and O(log n) once the tree is balanced. Without the size field, select(3) would need an in-order traversal counting as it went — O(n) — and rank would need the same. The 3 and the 4 are counts on the tree drawn, whose height is 3 because that insertion order was kind; the claim is O(height), and on the sorted order of the shape-problem lesson the identical queries would walk n. The augmentation buys O(log n) only on top of something that keeps the tree short, which is why an order-statistic tree is an AVL tree with a size field rather than a search tree with one.
How many keys lie in [20, 70]? Count the keys at most 70 and subtract the keys below 20. Each count is a rank-style walk adding a subtree size at every right turn, so the query is two paths rather than a scan: the lab reports 4 — 25, 37, 50, 62 — from 7 nodes visited across both walks. Listing the keys would of course cost the number of keys listed; counting them does not.
An attribute f can be maintained on a search tree at constant extra cost per structural change if f(x) is computable in constant time from the key at x and the values f(left(x)) and f(right(x)).
Insertion and deletion change f only on one root-to-leaf path, and a rotation changes it only at the two nodes it rearranges; in each case recomputing bottom-up from the criterion costs a constant per node touched. Size satisfies it with 1 + left + right, sum with key + left + right, min with min(key, left). A median does not: the median of a set is not a constant-time function of one key and the medians of two subsets, so the field would have to be rebuilt and the technique buys nothing.
That criterion is the reusable part of this lesson. It is why an interval tree can store the maximum endpoint in a subtree, why an order-statistic tree stores sizes, and why nobody stores a median. The question to ask about any proposed field is not whether it is useful but whether a node could recompute it from its two children without looking further down.
Rotate left at 25 in the tree above. The node 37 rises, 25 becomes its left child, and the sizes must be recomputed at 25 first and then at 37:
The order matters: recompute the node that descended before the node that rose, because the riser’s value depends on it. The lab checks every size in the tree against a fresh recount after the rotation and reports whether they all agree — which is the kind of check worth having, because a stale size field produces wrong answers from a structurally perfect tree and no error anywhere.
Interactive
Rank and select become walks, and the rotation has to maintain the field
Method
The walk is arithmetic, so the discipline is to write the arithmetic down at each node rather than following the shape by eye.
L is the only thing either query needs from a node besides its key. Writing it down at each step is what makes the two rules mechanical instead of a guess about which way the target lies.
i = L + 1 stops. i ≤ L goes left with i unchanged. Otherwise go right with i reduced by L + 1. Forgetting the reduction is the standard error and it gives an answer that is too small by the number of keys skipped.
Going left passes over nothing that is below the target. Going right passes over the whole left subtree and the node, so add L + 1. At the target, add L + 1 once more for the keys below it in its own left subtree, plus itself.
An insertion increments along its path. A rotation recomputes at the descending node first and the rising node second. Then check the invariant size[x] = size[left] + size[right] + 1 somewhere, because nothing else in the structure will notice if it fails.
Three queries on the same nine-node tree, with the node count for each. The in-order sequence is 6 12 18 25 37 50 62 75 87.
select(5) and rank(37) are inverse queries and both cost three nodes on this tree, which is the point of the pair: one integer per node bought two operations that a plain search tree cannot perform at all without a full traversal.
The range count is 4 from seven nodes visited, and the seven is worth noticing: it is two independent walks down a tree of height 3, not a scan of the four keys. If the query had been to list the keys the cost would include them; counting them does not, and that asymmetry is exactly what the augmentation is for.
For a faded rehearsal, compute select(9) and rank(62) on the same tree. The supplied first step for select(9) is that L = 5 at the root and 9 > 6, so the walk goes right with i = 3. Finish both, predict the node counts, and check them in the lab — three each. Then rotate left at 25 and write down the two sizes that change, in the order they must be recomputed.
You should be able to run select and rank on a drawn size-annotated tree writing the arithmetic at each node, count the nodes a range query visits and say why it is not proportional to the answer, state the augmentation criterion and apply it to size, sum, min and a median, and recompute the sizes after a rotation in the correct order.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.