 [FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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:
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:

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.

2014-06-17 11:58