Order-maintenance problem とは

コンピュータサイエンスでは、注文保守の問題は、以下の操作をサポートする完全に順序付けられたセットを維持することを伴う。
 insert(X、Y):総順序でYの直後にXを挿入します。 order(X、Y) – Xが全体の順序でYよりも先かどうかを判定します。 (X)を削除すると、セットからXが削除されます。
Paul Dietzは、1982年にこの問題を解決するためのデータ構造を初めて導入しました。このデータ構造は、 O ( log n ) {\displaystyle O(\log n)} (Big O表記)のinsert(X、Y)を一定時間で償却された時間と序列削除。 Athanasios Tsakalidisは、 O ( log n ) {\displaystyle O(\log n)} での削除をサポートし、インダイレクションで償却された時間 O ( 1 ) {\displaystyle O(1)} への挿入および削除のパフォーマンスを向上させる同じ性能​​限界を持つBB [α]ツリーを使用しました。 DietzとDaniel Sleatorは、1987年の最悪の一定時間の改善を発表しました。
オーダー・メンテナンスの効率的なデータ構造には、データ構造永続性、グラフ・アルゴリズム、フォールト・トレラントなデータ構造など、多くの分野でアプリケーションがあります。