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: Select – find the i-th smallest element stored in the tree Rank – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the treeBoth operations can be performed in O worst case time when a self-balancing tree is used as the base data structure. Wikipedia