.. _ost:

Order Statistic Tree
==========================

In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion:

.. code:: c++

    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 O(log n) worst case time when a self-balancing tree is used as the base data structure.

To have oder statistic, we just need to add a cardinality member variable in the node to represent the node number of the tree with the current node as root.

.. figure:: ostree.png
    :align: center
    :name: ostree
    
    order statistic tree select algorithm


The node definition could be like :numref:`order_statistics_tree_node`.

.. literalinclude:: percentile_tree_test.cpp
  :language: c++
  :lines: 6-11
  :linenos:
  :name: order_statistics_tree_node
  :caption: order statistic tree node
  :emphasize-lines: 3


In GNU STL, we can use GNU Policy-Based STL map as an order statistic tree.

.. literalinclude:: order_statistics_tree_test.cpp
  :language: c++
  :lines: 8-23
  :linenos:
  :name: order_statistics_tree
  :caption: order statistic tree in GNU STL
  :emphasize-lines: 14-15

Related questions: Percentile Query Tree(:numref:`ost_percentile_query_tree`)