スプレー木

スプレー木（スプレーき、英: splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。

2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。

長所と短所

スプレー木の性能がよいのは、頻繁にアクセスされるノードが根の近くになるように移動させることで、より素早くアクセスできるようにし、自動的に平衡をとり、自動的に最適化するためである。これはほとんどの用途で長所となる特徴であり、特にキャッシュやガベージコレクションのアルゴリズムの実装に便利である。

スプレー木は、平均的ケースでの効率が同程度なら、赤黒木やAVL木などの他の平衡2分探索木に比較して、実装が非常に単純であるという長所もある。また、スプレー木は簿記的データを格納する必要がないため、メモリ使用量も最小限に抑えることができる。ただし、それら他のデータ構造は最悪実行時間を保証することができる。

基本的なスプレー木での最悪ケースの1つとして、木に格納されている全要素にソートされた順序で逐次的にアクセスする場合が挙げられる。これ（n 回アクセスして、毎回 O(log n) の操作を行う）をすると最終的に木構造は完全に非平衡になる。そして、その状態の木でソート順の先頭の要素を探索すると、木を平衡に戻す操作に O(n) の操作が必要になる。これはかなりの遅延になるが、全体としての償却性能は O(log n) になっている。ただし、最近の研究によると、無作為な平衡化を行うことでこのような非平衡状態を防ぎ、他の平衡2分探索木と似たような性能を得られることが示されている。

スプレー木の永続版を作ることもでき、前の版と更新後の新しい版の両方にアクセスできるようにする。この場合、更新には O(log n) の償却メモリ領域が必要である。

他の平衡2分探索木とは逆に、スプレー木は各ノードが同一のキーを持つ場合にうまく機能する。同一のキーがある場合でも償却性能は O(log n) である。どんな操作をしても、木構造内の同一キーのノードの順序は保たれる。これは安定ソートと似たような特徴である。うまく設計すれば、探索によって指定されたキーを持つ左端または右端のノードを取り出すことができる。

スプレー操作

ノード x にアクセスするとき、x についてのスプレー操作によってそれを根に移動させる。スプレー操作は x を根に近い方へ移動させるスプレーステップを次々に実行することで行われる。アクセスの度にそのノードに対してスプレー操作を行うことで、最近アクセスされたノードは根の近くに保持されるので、木の平衡を大まかに保ったまま、必要な償却時間制限を達成できる。

個々のステップには、以下の3要素が関係する。

• x は親ノード p の右の子ノードか、それとも左の子ノードか
• p は根ノードか否か
• p は親ノード g の右の子ノードか、それとも左の子ノードか

スプレーステップには、以下の3種類が存在する。

zig ステップ

p が根ノードの場合に実行される。木の回転は、x と p を繋ぐ辺の上で行われる。zig ステップはスプレー操作前の状態で x の深さが奇数だったときだけ、スプレー操作の最後のステップとして実行される。

zig-zig ステップ

p が根ノードではなく、x も p も親に対して共に右の子ノード、あるいは共に左の子ノードの場合、実行される。下図では、x も p の左の子ノードの場合を示している。木の回転は p とその親である g を繋ぐ辺の上で行われ、次に x と p を繋ぐ辺の上で行われる。zig-zig ステップは、Allen と Munro が rotate to root と名づけた手法とスプレー木の唯一の違いである。

zig-zag ステップ

p が根ノードではなく、x が右の子ノードで p が左の子ノードの場合（または逆の組合せの場合）、実行される。木の回転はまず x と p を繋ぐ辺の上で行われ、次に x と新たな親ノードとなった g とを繋ぐ辺の上で行われる。

計算量

要素数 n のスプレー木で m 回のアクセスのシーケンス S の最悪実行時間について、いくつかの定理と予想が存在する。

平衡定理 (balance theorem)

シーケンス S を実行するコストは $O(m(\log n+1)+n\log n)\,\!$ である。すなわち、スプレー木は少なくとも n 回のアクセスのシーケンスにおいて、静的平衡2分探索木と同程度の性能を発揮する。

静的最適性定理 (static optimality theorem)

S において要素 i にアクセスする回数を $q_{i}$ とする。すると S を実行するコストは $O{\Bigl (}m+\sum _{i=1}^{n}q_{i}\log {\frac {m}{q_{i}}}{\Bigr )}$ となる。すなわち、スプレー木は少なくとも n 回のアクセスのシーケンスにおいて、最適化された静的平衡2分探索木と同程度の性能を発揮する。

静的指定理 (static finger theorem)

S において $j^{th}$ 番目にアクセスされる要素を $i_{j}$ とし、f を任意の固定要素（これを指 finger と呼ぶ）とする。すると S を実行するコストは $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(|i_{j}-f|+1){\Bigr )}$ となる。

ワーキングセット定理 (working set theorem)

j 番目のアクセスと以前に同じ要素 $i_{j}$ がアクセスされた間にアクセスされた別々の要素の個数を $t(j)$ とする。するとS を実行するコストは $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(t(j)+1){\Bigr )}$ となる。

動的指定理 (dynamic finger theorem)

S を実行するコストは $O{\Bigl (}m+n+\sum _{j=1}^{m}\log(|i_{j+1}-i_{j}|+1){\Bigr )}$ である。

走査定理 (scanning theorem)

逐次アクセス定理とも呼ばれる。スプレー木の n 個の要素に対称的順序でアクセスすると、スプレー木の初期状態に関わらず $\Theta (n)\,\!$ の時間がかかる。これまでに証明された最もきつい上限は $4.5n$ である。

動的最適性予想

スプレー木の性能に関しては、証明済みの定理だけでなく、最初のスレイターとタージャンの論文にも記載されていた証明されていない予想が存在する。この予想は動的最適性予想 (Dynamic optimality conjecture) と呼ばれ、それは基本的にスプレー木の性能が他の2分探索木アルゴリズムにある定数係数を加えた範囲内になるという予想である。

動的最適性予想

要素 $x$ にアクセスするのに、根ノードから走査してコスト $d(x)+1$ かかる2分探索木アルゴリズムを $A$ とする。そして、$A$ において、任意の木の回転を1のコストでできるとする。$A$ においてアクセスのシーケンス $S$ を実行するコストを $A(S)$ とする。すると、スプレー木が同じアクセスをするのにかかるコストは $O(n+A(S))$ である。

動的最適性予想には、以下のような証明されていない系が存在する。

走査予想 (traversal conjecture)

同じ要素を格納している2つのスプレー木 $T_{1}$ と $T_{2}$ があるとする。シーケンス $S$ が $T_{2}$ において要素を前順（深さ優先順）に走査するシーケンスであるとする。このシーケンス $S$ を $T_{1}$ 上で実行するコストは $O(n)$ となる。

デック予想 (deque conjecture)

$S$ が両端キュー（デック）操作を $m$ 回行うシーケンスであるとする。するとスプレー木上で $S$ を実行するコストは $O(m+n)$ となる。

分割予想 (split conjecture)

$S$ がスプレー木の要素の任意の順列とする。すると、$S$ の順序に従って要素を削除するコストは $O(n)$ である。

参考文献

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Page 478 of section 6.2.3.

外部リンク

アルゴリズム

• "Self-adjusting Binary Search Trees", Sleator and Tarjan (the original publication)
• NIST's Dictionary of Algorithms and Data Structures: Splay Tree

実装

• Implementations in C and Java by Sleator (one of the original inventors)
• FreeBSD's single header file implementation

可視化

• New York University: Dept of Computer Science: Algorithm Visualization: Splay Trees
• splay tree visualizations
• Splay Tree Applet
• AVL, Splay and Red/Black Applet