スプレー木

スプレー木とは

スプレー木（Splay Tree）は、自己調整機能を持つ特殊な二分探索木の一種です。最近アクセスされた要素を効率的に再アクセスできるように最適化されており、データ構造の動的な変化に対応できるのが特徴です。ダニエル・スレイターとロバート・タージャンによって発明されました。

基本操作

スプレー木では、挿入、参照、削除といった基本的な操作は、すべて「スプレー操作」という一つの基本操作と組み合わせて実行されます。スプレー操作とは、指定された要素を木の根まで移動させる操作のことで、これによって頻繁にアクセスされるノードが木の根近くに集まり、効率的なアクセスが可能になります。

通常、二分探索木での要素の探索を行った後、その要素が木の根に来るように木の回転を繰り返します。また、探索と再配置を同時に行うトップダウンアルゴリズムも存在します。

長所

自己最適化: スプレー木は、頻繁にアクセスされるノードを根の近くに移動させることで、自動的に平衡を保ち、アクセス効率を最適化します。これにより、キャッシュやガベージコレクションなどのアルゴリズム実装に役立ちます。
実装の容易さ: 赤黒木やAVL木などの他の平衡二分探索木と比較して、実装が比較的単純です。
省メモリ: 簿記的なデータを格納する必要がないため、メモリ使用量を最小限に抑えることができます。
同一キーの扱い: 各ノードが同一キーを持つ場合でも、スプレー木は効率的に機能します。同一キーを持つノードの順序は操作後も保たれ、安定ソートのような特性を持ちます。キーを指定して左端や右端のノードを抽出することも可能です。

短所

最悪ケースの性能: ソートされた順序で要素に逐次アクセスすると、木が完全に非平衡になり、特定要素へのアクセスにO(n)の時間がかかる場合があります。ただし、これは償却時間で見た場合であり、全体としての性能はO(log n)です。最近の研究では、無作為な平衡化でこの問題を軽減できることが示されています。
最悪実行時間の保証: 赤黒木やAVL木とは異なり、最悪実行時間を保証することができません。

スプレー操作の詳細

スプレー操作は、アクセスされたノードxを根まで移動させる操作です。これは、以下の3つの要素に基づいて行われる一連の「スプレーステップ」によって実現されます。

1. ノードxの位置: ノードxは親ノードpの右の子か、左の子か。
2. 親ノードpの位置: 親ノードpは木の根か、そうでないか。
3. 親ノードpの親ノードgの位置: 親ノードpが根でない場合、pは親ノードgの右の子か、左の子か。

スプレーステップには以下の3種類があります。

zigステップ: 親ノードpが根である場合に実行されます。xとpを繋ぐ辺上で木の回転が行われます。
zig-zigステップ: 親ノードpが根でなく、xとpが共に親に対して右の子または左の子である場合に実行されます。pとその親gの間の辺、次にxとpの間の辺で木の回転が行われます。
zig-zagステップ: 親ノードpが根でなく、xとpが親に対して異なる方向の子である場合に実行されます。まずxとpの間の辺、次にxと新しい親gの間の辺で木の回転が行われます。

計算量

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

平衡定理

シーケンスSの実行コストはO(m(log n + 1) + n log n)です。これは、スプレー木が少なくともn回のアクセスシーケンスにおいて、静的な平衡二分探索木と同程度の性能を持つことを示しています。

静的最適性定理

要素iへのアクセス回数をqiとすると、Sの実行コストはO(m + Σ(qi log(m/qi)))となります。これは、スプレー木が最適化された静的な平衡二分探索木と同程度の性能を持つことを意味します。

静的指定理

Sにおいてj番目にアクセスされる要素をijとし、fを固定要素（指）とすると、Sの実行コストはO(m + n log n + Σlog(|ij - f| + 1))です。

ワーキングセット定理

j番目のアクセスで、同じ要素ijが以前にアクセスされてからアクセスされた別の要素の数をt(j)とすると、Sの実行コストはO(m + n log n + Σlog(t(j) + 1))です。

動的指定理

Sの実行コストはO(m + n + Σlog(|ij+1 - ij| + 1))です。

走査定理

スプレー木のn個の要素に対称順序でアクセスすると、初期状態に関わらずΘ(n)の時間がかかります。

動的最適性予想

スプレー木の性能に関する未証明の予想として、動的最適性予想があります。これは、スプレー木の性能が、他の任意の二分探索木アルゴリズムの性能に定数倍を加えた範囲内にあるというものです。この予想が正しければ、スプレー木は常に最適な二分探索木アルゴリズムに近い性能を発揮することになります。

動的最適性予想
要素xへのアクセスにコストd(x)+1がかかる二分探索木アルゴリズムAがあるとする。Aで任意の木の回転をコスト1で行えるとき、アクセスシーケンスSを実行するコストをA(S)とすると、スプレー木が同じアクセスを行うコストはO(n + A(S))となる。

動的最適性予想には、以下の未証明の系が存在します。

走査予想: 同じ要素を格納する2つのスプレー木T1とT2があるとき、T2の要素を前順（深さ優先順）で走査するシーケンスSをT1で実行するコストはO(n)となる。
デック予想: シーケンスSが両端キュー（デック）操作をm回行う場合、スプレー木上でSを実行するコストはO(m + n)となる。
分割予想: シーケンスSがスプレー木の要素の順列である場合、Sの順序に従って要素を削除するコストはO(n)となる。

まとめ

スプレー木は、その自己調整機能により、アクセスパターンに応じて効率的なパフォーマンスを発揮するデータ構造です。特に、アクセス頻度が偏っているデータに対して有効であり、様々なアプリケーションで利用されています。しかし、最悪ケースの性能や動的最適性予想など、まだ解明されていない点も残されており、今後の研究が期待されています。

もう一度検索