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.

CategoryAlgorithmNotes