スプレー木のソースを表示

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

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

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

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

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

スプレー木の[[永続データ構造|永続]]版を作ることもでき、前の版と更新後の新しい版の両方にアクセスできるようにする。この場合、更新には O(log ''n'') の償却メモリ領域が必要である。{{要出典|date=2024年7月}}

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

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

個々のステップには、以下の3要素が関係する。
* ''x'' は親ノード ''p'' の右の子ノードか、それとも左の子ノードか
* ''p'' は根ノードか否か
* ''p'' は親ノード ''g'' の右の子ノードか、それとも左の子ノードか

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

; zig ステップ
: ''p'' が根ノードの場合に実行される。[[木の回転]]は、''x'' と ''p'' を繋ぐ辺の上で行われる。zig ステップはスプレー操作前の状態で ''x'' の深さが奇数だったときだけ、スプレー操作の最後のステップとして実行される。
: [[画像:splay_tree_zig.svg]]
; zig-zig ステップ
: ''p'' が根ノードではなく、''x'' も ''p'' も親に対して共に右の子ノード、あるいは共に左の子ノードの場合、実行される。下図では、''x'' も ''p'' の左の子ノードの場合を示している。木の回転は ''p'' とその親である ''g'' を繋ぐ辺の上で行われ、次に ''x'' と ''p'' を繋ぐ辺の上で行われる。zig-zig ステップは、Allen と Munro が ''rotate to root'' と名づけた手法とスプレー木の唯一の違いである。
: [[画像:Zigzig.gif]]
; zig-zag ステップ
: ''p'' が根ノードではなく、''x'' が右の子ノードで ''p'' が左の子ノードの場合（または逆の組合せの場合）、実行される。木の回転はまず ''x'' と ''p'' を繋ぐ辺の上で行われ、次に ''x'' と新たな親ノードとなった ''g'' とを繋ぐ辺の上で行われる。
: [[画像:Zigzag.gif]]

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

;平衡定理 (balance theorem)<ref name=SleatorTarjan>{{Citation | first1=Daniel D. | last1=Sleator | first2=Robert E. | last2=Tarjan | title=Self-Adjusting Binary Search Trees | url= https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf|journal=Journal of the [[Association for Computing Machinery|ACM]] | volume=32 | issue=3 | pages=pp. 652-686 | year= 1985}}</ref>
: シーケンス ''S'' を実行するコストは <math>O(m(\log n + 1)+n\log n)\,\!</math> である。すなわち、スプレー木は少なくとも ''n'' 回のアクセスのシーケンスにおいて、静的平衡2分探索木と同程度の性能を発揮する。
;静的最適性定理 (static optimality theorem)<ref name=SleatorTarjan/>
: ''S'' において要素 ''i'' にアクセスする回数を <math>q_i</math> とする。すると ''S'' を実行するコストは <math>O\Bigl(m+\sum_{i=1}^n q_i\log\frac{m}{q_i}\Bigr)</math> となる。すなわち、スプレー木は少なくとも ''n'' 回のアクセスのシーケンスにおいて、最適化された静的平衡2分探索木と同程度の性能を発揮する。
;静的指定理 (static finger theorem)<ref name=SleatorTarjan/>
: ''S'' において <math>j^{th}</math> 番目にアクセスされる要素を <math>i_j</math> とし、''f'' を任意の固定要素（これを指 ''finger'' と呼ぶ）とする。すると ''S'' を実行するコストは <math>O\Bigl(m+n\log n+\sum_{j=1}^m \log(|i_j-f|+1)\Bigr)</math> となる。
;ワーキングセット定理 (working set theorem)<ref name=SleatorTarjan/>
: ''j'' 番目のアクセスと以前に同じ要素 <math>i_j</math> がアクセスされた間にアクセスされた別々の要素の個数を <math>t(j)</math> とする。すると''S'' を実行するコストは <math>O\Bigl(m+n\log n+\sum_{j=1}^m \log(t(j)+1)\Bigr)</math> となる。
;動的指定理 (dynamic finger theorem)<ref name=ColeEtAl>R. Cole, B. Mishra, J. Schmidt, A. Siegel. ''On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences''. SIAM Journal on Computing 30, pages 1-43, 2000.</ref><ref name=Cole>R. Cole. ''On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof''. SIAM Journal on Computing 30, pages 44-85, 2000.</ref>
: ''S'' を実行するコストは <math>O\Bigl(m+n+\sum_{j=1}^m \log(|i_{j+1}-i_j|+1)\Bigr)</math> である。
;走査定理 (scanning theorem)<ref name=Tarjan>R.E. Tarjan. ''Sequential access in splay trees takes linear time''. Combinatorica 5, pages 367-378, 1985.</ref>
: '''逐次アクセス定理'''とも呼ばれる。スプレー木の ''n'' 個の要素に対称的順序でアクセスすると、スプレー木の初期状態に関わらず <math>\Theta(n)\,\!</math> の時間がかかる。これまでに証明された最もきつい上限は <math>4.5n</math> である。<ref name=Elmasry>Amr Elmasry. ''On the sequential access theorem and deque conjecture for splay trees''. Theor. Comput. Sci. 314(3), pages 459-466, 2004.</ref>

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

; 動的最適性予想<ref name=SleatorTarjan/>
: 要素 <math>x</math> にアクセスするのに、根ノードから走査してコスト <math>d(x)+1</math> かかる2分探索木アルゴリズムを <math>A</math> とする。そして、<math>A</math> において、任意の木の回転を1のコストでできるとする。<math>A</math> においてアクセスのシーケンス <math>S</math> を実行するコストを <math>A(S)</math> とする。すると、スプレー木が同じアクセスをするのにかかるコストは <math>O(n + A(S))</math> である。

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

; 走査予想 (traversal conjecture)<ref name=SleatorTarjan/>
: 同じ要素を格納している2つのスプレー木 <math>T_1</math> と <math>T_2</math> があるとする。シーケンス <math>S</math> が <math>T_2</math> において要素を前順（深さ優先順）に走査するシーケンスであるとする。このシーケンス <math>S</math> を <math>T_1</math> 上で実行するコストは <math>O(n)</math> となる。
; デック予想 (deque conjecture)<ref name=Pettie>S. Pettie. ''Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture''. In Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms, pages 1115--1124, 2008.</ref><ref name=Sundar>R. Sundar. ''On the deque conjecture for the splay algorithm''. Combinatorica 12(1):95--124, 1992.</ref><ref name=Tarjan/>
: <math>S</math> が[[両端キュー]]（デック）操作を <math>m</math> 回行うシーケンスであるとする。するとスプレー木上で <math>S</math> を実行するコストは <math>O(m + n)</math> となる。
; 分割予想 (split conjecture)<ref name=Lucas>J. Lucas. ''On the Competitiveness of Splay Trees: Relations to the Union-Find Problem''. Online Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 7, pages 95--124, 1991.</ref>
: <math>S</math> がスプレー木の要素の任意の順列とする。すると、<math>S</math> の順序に従って要素を削除するコストは <math>O(n)</math> である。

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* [[ドナルド・クヌース|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.

== 外部リンク ==
=== アルゴリズム ===
* [https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf "Self-adjusting Binary Search Trees", Sleator and Tarjan (the original publication)]
* [http://www.nist.gov/dads/HTML/splaytree.html NIST's Dictionary of Algorithms and Data Structures: Splay Tree]

=== 実装 ===
* [http://www.link.cs.cmu.edu/link/ftp-site/splaying/ Implementations in C and Java by Sleator (one of the original inventors)]
* [http://fxr.watson.org/fxr/source//sys/tree.h FreeBSD's single header file implementation]

=== 可視化 ===
* [http://www.cs.nyu.edu/algvis/java/SplayTree.html New York University: Dept of Computer Science: Algorithm Visualization: Splay Trees]
* [https://web.archive.org/web/20070308005154/http://web-cat.cs.vt.edu/AlgovizWiki/SplayTrees splay tree visualizations]
* [http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/SplayTree-Example.html Splay Tree Applet]
* [https://web.archive.org/web/20050801080205/http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm AVL, Splay and Red/Black Applet]

{{データ構造}}

{{DEFAULTSORT:すふれき}}
[[Category:二分木]]
[[Category:探索木]]
[[Category:償却データ構造]]