スプレー木の動的最適性予想とは？データ構造における有名な未解決問題を解説

動的最適性予想（Dynamic Optimality Conjecture）とは

スプレー木（Splay Tree）は、SleatorとTarjanが1985年に提案した自己適応型の二分探索木です。アクセスされた要素を根へ移動させる「スプレー操作」により、頻繁にアクセスされる要素ほど素早く取り出せるようになるという特徴を持ちます。スプレー木には、ならし解析に基づく証明済みの性能保証がありますが、それとは別に、未証明のまま大きな注目を集めている予想が存在します。それが「動的最適性予想（Dynamic Optimality Conjecture）」です。

この予想は次のように定式化されます。任意の二分探索木アルゴリズムBについて、要素yへのアクセスは根からyへの経路を辿ることで行われ、そのコストをd(y)+1とします（d(y)はyの深さ）。また、アクセスとアクセスの間に、Bは木に対して任意の回転操作を行うことができ、1回の回転につきコスト1がかかるとします。アクセス列sをアルゴリズムBが実行する際の総コストをB(s)と表すとき、スプレー木が同じアクセス列sを実行するコストはO(n + B(s))で抑えられる、というのがこの予想の主張です。

言い換えれば、スプレー木は「どのような二分探索木アルゴリズムと比べても、定数倍の差を除いて劣らない性能を発揮する」ということになります。この予想は提唱から40年近く経った今もなお完全には証明されておらず、データ構造理論における最も有名な未解決問題の一つとされています。

動的最適性予想から導かれる未証明の系

動的最適性予想が正しければ、以下に示すような重要な性質（系）がすべて導かれます。しかし、これらの系も個別には依然として証明されていません。

走査予想（Traversal Conjecture）

2つのスプレー木t1とt2が同じ要素の集合を含んでいるとします。t2のすべての要素を行きがけ順（preorder、すなわち深さ優先探索の順序）で訪問することで得られる列をsとします。このとき、t1に対してアクセス列sを実行する全体のコストはO(n)となります。直感的には、「ある木の構造をなぞるようなアクセス列は、別の木でも効率的に処理できる」ことを意味します。

両端キュー予想（Deque Conjecture）

p個の両端キュー（deque）操作（push、pop、inject、eject）からなる操作列sを考えます。このとき、スプレー木上で操作列sを実行するコストはO(p + n)となります。これは、スプレー木を両端キューとして利用した場合でも、効率的に動作することを示唆しています。

分割予想（Split Conjecture）

sをスプレー木に含まれる要素の任意の順列（並び順）とします。このとき、sの順序に従って要素を1つずつ削除していくコストはO(n)となります。つまり、どの順序で削除を行っても、全体として線形時間で処理できることを主張しています。

まとめ

動的最適性予想は、スプレー木の「普遍的な最適性」を主張する非常に強力な予想であり、その証明はデータ構造理論における重要な研究テーマであり続けています。部分的な進展はあるものの、完全な証明または反証はまだ得られておらず、走査予想・両端キュー予想・分割予想といった系の解明とともに、今後の研究の進展が期待される分野です。