splay tree

ウィキペディア

スプレー木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/07/22 03:13 UTC 版)

スプレー木（スプレーき、英: 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)^[1]

シーケンス S を実行するコストは ${\displaystyle O(m(\log n+1)+n\log n)\,\!}$カテゴリ