Order statistic tree


In computer science, an order statistic tree is a variant of the binary search tree that supports two additional operations beyond insertion, lookup and deletion:
Both operations can be performed in worst case time when a self-balancing tree is used as the base data structure.

Augmented search tree implementation

To turn a regular search tree into an order statistic tree, the nodes of the tree need to store one additional value, which is the size of the subtree rooted at that node. All operations that modify the tree must adjust this information to preserve the invariant that
size = size = 0 by definition. Select can then be implemented as
function Select
// Returns the i'th element of the elements in t
l ← size
else if i < l
return Select
else
return Select
Rank can be implemented as
function Rank
// Returns the position of x in the linear sorted list of elements of the tree T
r ← size
r ← r + sizeleft[y.p + 1
y ← y.p
return r
Order-statistic [trees can be further amended with bookkeeping information to maintain balance. Alternatively, the size field can be used in conjunction with a weight-balancing scheme at no additional storage cost.