Order statistic tree とは

コンピュータサイエンスでは、順序統計木は、挿入、検索、削除以外の2つの追加操作をサポートするバイナリ検索ツリー(またはより一般的にはBツリー)の変形です。
 選択(i) – ツリーに格納されているi番目の最小要素を見つけるランク(x) – ツリー内の要素xのランク、すなわちツリーの要素のソートされたリスト内のインデックス
両方のオペレーションは、自己均衡ツリーが基本データ構造として使用されるとき、O(log n)最悪の場合の時間で実行され得る。