順序統計ツリー

コンピュータサイエンスにおいて、順序統計木は二分探索木（またはより一般的にはB木^[1] ）の変形であり、挿入、検索、削除に加えて2つの追加操作をサポートします。

• Select( i ) –ツリーに格納されているi番目に小さい要素を見つける
• Rank( x ) –ツリー内の要素xの順位、つまりツリーの要素のソートされたリスト内のインデックスを見つけます。

自己バランスツリーを基本データ構造として使用する と、両方の操作は最悪の場合でもO (log n ) の 時間で実行できます。

通常の探索木を順序統計木に変えるには、木のノードに1つの追加値、つまりそのノードをルートとするサブツリーのサイズ（つまり、その下のノードの数）を格納する必要があります。木を変更するすべての操作は、不変量を維持するためにこの情報を調整する必要があります。

サイズ[x] = サイズ[左[x]] + サイズ[右[x]] + 1

ここでsize[nil] = 0定義により、Selectは次のように実装できる^{[2] :342}

関数Select(t, i)
    // t 内の要素の i 番目の要素 (1 から始まる) を返します
    p ← サイズ[左[t]]+1
    もしi = pならば
        tを返す
    そうでない場合は、 i < p
        の場合はSelect(left[t], i)
    を返し、そうでない場合は
        Select(right[t], i - p)
を返します。

ランクは親関数p[x]を使用して次のように実装できる^{[3] :342}

関数Rank(T, x)
    // ツリー T の要素の線形ソートリスト内の x (1 から始まる) の位置を返します。
    r ← サイズ[左[x]] + 1
    y ← x
    y ≠ T.root
        の場合、 y = right[p[y]]
            r ← r + サイズ[左[p[y]]] + 1
        y ← p[y]
    rを
返す

順序統計木は、バランスを保つために簿記情報でさらに修正することができます（例えば、木の高さを追加して順序統計AVL木を取得したり、色ビットを追加して赤黒順序統計木を取得したりできます）。あるいは、サイズフィールドを重みバランススキームと組み合わせて使用​​​​して、追加のストレージコストをかけずに使用することもできます。^[4]

• 暗黙のトレップ
• セグメントツリーはカウントクエリに使用でき、ランクはカウントクエリであり、各ノードに1が格納され、先頭から要素まで合計されるかのようです。

• イェール大学の PineWiki の順序統計ツリー。
• Pythonパッケージ blist は、順序統計 B ツリーを使用して、任意の位置に高速に挿入できるリストを実装します。