Order-Statistics Tree

What Problem This Solves

A sorted array answers 'what is the k-th smallest element' in constant time by direct indexing, and answers 'what is the rank of element x' in logarithmic time via binary search. The catch is that inserting or deleting a value in a sorted array costs linear time, because everything after the affected position must shift. A plain balanced binary search tree flips this trade-off: insertion and deletion are logarithmic, but finding the k-th smallest element requires an in-order traversal that costs linear time, since the tree stores no information about how many elements sit in each subtree. Neither structure alone gives fast versions of all four operations at once: search, insert, delete, and rank-based selection. The order-statistics tree closes this gap by augmenting a balanced tree, most commonly a red-black tree, with one integer per node representing subtree size. Because a red-black tree already guarantees a tree height of O(log n) through its color and balance invariants, and because subtree size can be maintained during the same rotations that preserve those invariants, the augmentation is essentially free. It adds constant space per node and constant extra work per rotation, while unlocking selection and rank queries that would otherwise force a full traversal. This pattern generalizes: the same augmentation principle applies to interval trees, which store subtree maximum endpoints, or to trees storing subtree sums for range-aggregate queries. In every case, the underlying balanced tree provides logarithmic height, and a carefully chosen augmenting field, updatable in constant time per rotation, provides an extra fast query without sacrificing the original tree's insert and delete performance. The order-statistics tree is the canonical, simplest example of this augmentation technique, and studying it well makes the more elaborate augmented structures far easier to understand later.

The Augmentation: Storing Subtree Size

Every node x in an order-statistics tree carries a field size[x], defined as the number of nodes in the subtree rooted at x, including x itself. Formally, size[x] = size[left[x]] + size[right[x]] + 1, where an empty child contributes zero. This recursive definition is what makes maintenance manageable: whenever a node's children change, its size can be recomputed from its immediate children alone, without looking any deeper into the tree. During a standard binary search tree insertion, a new node is added as a leaf at the end of a root-to-leaf search path; every ancestor on that path gains exactly one descendant, so each of their size fields simply increases by one as the insertion walks back up, or equivalently is incremented while walking down before the leaf is attached. Deletion is symmetric: removing a node decreases the size field of every ancestor on the path to the removed node by one. The trickier case is rotation, the operation a red-black tree uses to restore balance after an insertion or deletion. A rotation, whether left or right, changes which node is the parent and which is the child among two nodes, meaning it changes whose subtree contains what. Concretely, in a left rotation around node x with right child y, node y takes x's place, x becomes y's left child, and y's former left subtree becomes x's new right subtree. After this pointer surgery, only two size fields need recomputation, and they must be recomputed in the correct order: first size[x], using x's now-updated children, then size[y], using y's new left child x and its unchanged right child. Because only a constant number of nodes have their subtree membership altered by any single rotation, updating size fields adds only constant overhead to each rotation, so the overall insertion or deletion remains O(log n).

OS-SELECT: Finding the k-th Smallest Element

OS-SELECT(x, k) finds the node holding the k-th smallest key in the subtree rooted at x, using the stored size fields to make an informed decision at every step rather than exploring blindly. The procedure begins by computing r = size[left[x]] + 1, which is the rank of node x within its own subtree: everything in x's left subtree is smaller than x, so x itself is the (r)-th smallest element in that subtree. Three cases follow. If k equals r, node x is exactly the answer, and the search terminates immediately. If k is less than r, the desired k-th smallest element must lie somewhere in the left subtree, since that subtree alone already contains at least k elements smaller than or equal to what's needed; the algorithm recurses into left[x] with the same value of k. If k is greater than r, the desired element lies in the right subtree, but its rank there is smaller than k, because r elements, namely x and its entire left subtree, are already known to precede it; the algorithm recurses into right[x] with the adjusted value k minus r. This is not a full traversal of the tree; it is a single descent from root to the answer node, making exactly one comparison-driven decision per level. Since the tree height is O(log n) by the balancing invariant, OS-SELECT runs in O(log n) time. Contrast this with an in-order traversal approach, which would need to visit and count up to k nodes, potentially touching a large fraction of the tree; OS-SELECT instead prunes an entire subtree at every step it doesn't need to explore, exactly the way binary search prunes half the search space at every comparison.

OS-RANK: Finding an Element's Position

OS-RANK(T, x) answers the mirror-image question: given a pointer to a node x already found in the tree, what is its rank, meaning its position if the whole tree were listed in sorted order? The algorithm exploits the same size fields but walks upward from x toward the root instead of downward from the root. It initializes a running count r = size[left[x]] + 1, the rank of x within its own subtree, exactly as in OS-SELECT. Then it climbs the tree one parent at a time. At each step, if the current node y is the right child of its parent, that means the parent and the parent's entire left subtree, along with the parent itself, all have keys smaller than everything counted so far, so the algorithm adds size[left[parent]] + 1 to r before moving up to the parent. If y is instead the left child of its parent, nothing needs to be added, because the parent and the parent's other subtree are all larger, and the count r is unaffected; the algorithm simply moves up to the parent. This continues until the root is reached, at which point r holds the correct overall rank of x in the entire tree. Because this walk follows a single root-to-node path in reverse, and that path has length O(log n) in a balanced tree, OS-RANK also runs in O(log n) time. Notice the elegant symmetry between OS-SELECT and OS-RANK: one descends using size fields to locate a node given a target rank, the other ascends using size fields to compute a rank given a located node, and both rely on exactly the same augmentation and exactly the same asymptotic bound.

Practical Use: Streaming Medians and Percentiles

A natural application of an order-statistics tree is maintaining statistics like the median or an arbitrary percentile over a dataset that keeps changing, with values being inserted and removed continuously, such as a live feed of sensor readings, transaction amounts, or latency measurements. Recomputing the median naively would mean re-sorting the entire dataset every time a value arrives or leaves, an approach whose cost grows without bound as the stream continues, since each of n updates would cost O(n log n) for a fresh sort. With an order-statistics tree, each new value is inserted in O(log n) time, and the tree automatically rebalances itself, updating size fields along the way as described earlier. Whenever the current median is needed, a single OS-SELECT call with k = (n+1)/2 for odd n, or an average of the (n/2)-th and (n/2+1)-th smallest for even n, retrieves it in O(log n) time, using the size field of the root's left child to immediately know whether the median so far lies left, right, or at the root. The same idea generalizes cleanly to arbitrary percentiles: the 90th percentile of n elements corresponds to k = ceil(0.9 * n), and OS-SELECT finds it with the same single descent, regardless of how large n grows. This makes the order-statistics tree attractive for dashboards and monitoring systems that need to report percentile-based service-level metrics, like the 95th-percentile response time, continuously as new measurements arrive and old ones age out. It also outperforms a naive two-heap median-tracking scheme when arbitrary percentiles, not just the median, are required, since two heaps are specialized for a fixed split point, whereas one order-statistics tree serves any rank query on demand. Deletion of arbitrary elements, not just the extremes, is also handled cleanly, unlike in many heap-based schemes.

Frequently asked questions

Try it live

Everything above runs in your browser — open Order-Statistics Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.