Augmenting Data Structures

Dynamic Order Statistics

The i-th order statistic of a set of n elements where i exists in {1, 2, …, n} is the element with the i-th smallest key.

Node representations:

• key[x]

• color[x]

• size[x] = size[2x+1] + size[2x+2] + 1 (Size of left and right and itself)

• right[x]

• left[x]

Goal:

given an order-statistic tree, return a pointer to the node containing the i-th smallest key in the subtree

We need to maintain the size field during insert and deletion operations efficiently. 

You can do this using a QuickSort like method and creating a random pivot.