前任者の問題

コンピュータサイエンスにおいて、先行要素問題とは、与えられた要素に対して、その要素の前後にどの要素が順序通りに現れるかを効率的に問い合わせるための要素セットを維持する問題である。この問題を解決するために使用されるデータ構造には、バランスのとれた二分探索木、ファン・エムデ・ボアス木、融合木などがある。静的先行要素問題では、要素セットは変化しないが、動的先行要素問題では、セットへの挿入と削除が許される。^{[ 1 ]}

先行問題とは、最近傍問題の単純なケースであり、それを解決するデータ構造は、整数ソートなどの問題に応用できる。

この問題は、 U個の整数のサブセットを含む集合Sを維持することです。これらの整数はそれぞれワードサイズwで格納できるため、${\displaystyle U\leq 2^{w}}$問題を解決するデータ構造は、これらの操作をサポートします。^{[ 2 ]}

• predecessor(x)これは、 Sの中でxより厳密に小さい最大の要素を返します。
• successor(x)これは、 Sの中でxより厳密に大きい最小の要素を返します。

さらに、この問題の動的なバージョンを解決するデータ構造は、以下の操作もサポートしています。

• insert(x)これは、xを集合Sに追加する。
• delete(x)これは、集合Sからxを削除する。

この問題は、ワードRAMなどの計算の二分法 モデルで分析されるのが一般的です。

この問題に対する簡単な解決策の 1 つは、バランスのとれた二分探索木を使用することです。これにより、（ビッグ O 表記で）実行時間は次のようになります。${\displaystyle O(\log n)}$先行クエリの場合。Van Emde Boas ツリーはクエリ時間で次の値を達成します。${\displaystyle O(\log \log U)}$しかし、${\displaystyle O(U)}$スペース。^{[ 1 ]}ダン・ウィラードは、 x-fast トライでこのスペース使用の改善を提案したが、${\displaystyle O(n\log U)}$スペースとクエリ時間は同じで、より複雑なy-fast トライでは、必要なのは${\displaystyle O(n)}$空間。^{[ 3 ]}マイケル・フレッドマンとウィラードによって導入された融合ツリーは、${\displaystyle O(\log _{w}n)}$クエリ時間と${\displaystyle O(n)}$静的問題の先行クエリの場合。^{[ 4 ]}動的問題は指数木を使用して解決されています。${\displaystyle O(\log _{w}n+\log \log n)}$クエリ時間、^{[ 5 ]}、および期待時間${\displaystyle O(\log _{w}n)}$ハッシュ化を使用する。^{[ 6 ]}

先行問題の下限を証明したり、漸近的に最適な解の実行時間を特定したりする論文が数多く発表されている。例えば、Michael BeameとFaith Ellenは、 wのすべての値に対して、クエリ時間（ビッグシータ表記）を持つnの値が存在することを証明した。${\displaystyle \Omega \left({\tfrac {\log w}{\log \log w}}\right)}$同様に、nのすべての値に対して、クエリ時間が${\displaystyle \Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)}$^{[ 1 ]}下限の証明には、通信複雑性の概念が含まれる。

静的先行問題に関して、Mihai PătrașcuとMikkel Thorup は、セルプローブモデルにおける最適な探索時間の下限を次のように示しました。^{[ 7 ]}$${\displaystyle O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.}$$ RAMのワード長は${\displaystyle w}$セットには以下が含まれます${\displaystyle n}$整数${\displaystyle \ell }$ビットずつで、RAMでは次のように表現されます。${\displaystyle S}$空間の言葉、そして定義する${\displaystyle a=\lg {\frac {S}{n}}+\lg w}$。

の場合${\displaystyle w=\ell =\gamma \lg n}$のために${\displaystyle \gamma >1}$そして${\displaystyle S=n\cdot \lg ^{O(1)}n}$最適な検索時間は ${\displaystyle \Theta (\lg \ell )}$そして、ファン・エムデ・ボアス木はこの限界を達成する。^{[ 7 ]}

• 整数ソート
• y-fast トライ
• 融合ツリー