An order-statistics tree is an augmented (see AugmentedDataStructures) version of a BinarySearchTree that supports the additional operations Rank(x), which returns the rank of x (i.e., the number of elements with keys less than or equal to x) and FindByRank(k), which returns the k-th smallest element of the tree.
To construct an order-statistics tree, start with a tree that keeps track of the number of nodes in each subtree, using the techniques described in AggregateQueries. Let's suppose that each node has an extra field count that counts its descendants (including itself). Then we can implement Rank by a simple DecreaseAndConquer algorithm similar to the SumAtLeast procedure from AggregateQueries.
Rank(root, x): if root is null: error: not found else if x < root.key: return Rank(root.left, x) else if x = root.key: if root.left is not null: return root.left.count + 1 else: return 1 else if x > root.key: if root.left is not null: return root.left.count + 1 + Rank(root.right, x) else: return 1 + Rank(root.right, x)
FindByRank has a similar structure:
FindByRank(root, k): if root is null: error: not found if root.left is null: leftcount = 0 else: leftcount = root.left.count if k <= leftcount: return FindByrank(root.left, k) else if k = leftcount + 1: return root else if k > leftcount + 1: return FindByRank(root.right, k - leftcount - 1)
It is easy to see that both operations take O(log n) time provided the tree is balanced.