computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, an order statistic tree is a variant of the

binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a Rooted tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...

(or more generally, a

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing fo ...

) that supports two additional operations beyond insertion, lookup and deletion: * Select(''i'') – find the ''i''-th smallest element stored in the tree * Rank(''x'') – find the rank of element ''x'' in the tree, i.e. its index in the sorted list of elements of the tree 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 (i.e., the number of nodes below it). All operations that modify the tree must adjust this information to preserve the invariant that size = size eft[x + size[right[x">.html" ;"title="eft[x">eft[x + size[right[x + 1 where

size[nil">">eft[x<_a>_+_size[right[x.html" ;"title=".html" ;"title="eft[x">eft[x + size[right[x">.html" ;"title="eft[x">eft[x + size[right[x + 1

where size[nil= 0 by definition. Select can then be implemented as

 function Select(t, i)
     // Returns the i'th element (one-indexed) of the elements in t
     p ← size[left[t+1
     if i = p
         return t
     else if i < p
         return Select(left[t], i)
     else
         return Select(right[t], i - p)

Rank can be implemented, using the parent-function p  as

 function Rank(T, x)
     // Returns the position of x (one-indexed) in the linear sorted list of elements of the tree T
     r ← size eft[x + 1
     y ← x
     while y ≠ T.root
         if y = right[p[y">.html" ;"title="eft[x">eft[x + 1
     y ← x
     while y ≠ T.root
         if y = right[p[y
             r ← r + size[left[p[y] + 1
         y ← p[y]
     return r

Order-statistic trees can be further amended with bookkeeping information to maintain balance (e.g., tree height can be added to get an order statistic  AVL tree, or a color bit to get a  red–black order statistic tree). Alternatively, the size field can be used in conjunction with a  weight-balancing scheme at no additional storage cost.

 References



 See also

*  Implicit treap
* Segment tree 




In computer science, the segment tree is a data structure used for storing information about Interval (mathematics), intervals or segments. It allows querying which of the stored segments contain a given point. A similar data structure is the i ...
 can be used for counting queries, and rank is a counting query, as if each node stores 1 and they are summed from beginning to element

 External links


Order statistic tree
on PineWiki, Yale University.
* The  Python packag
blist
uses order statistic B-trees to implement  lists with fast insertion at arbitrary positions.

{{CS-Trees

 Search trees
 Selection algorithms