|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
スプレー木（スプレーき、）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。 == 長所と短所 == スプレー木の性能がよいのは、頻繁にアクセスされるノードが根の近くになるように移動させることで、より素早くアクセスできるようにし、自動的に平衡をとり、自動的に最適化するためである。これはほとんどの用途で長所となる特徴であり、特にキャッシュやガベージコレクションのアルゴリズムの実装に便利である。しかし、一様なアクセスが発生するような場合、スプレー木は単純な平衡2分探索木よりもずっと性能が悪くなる。 スプレー木は、平均的ケースでの効率が同程度なら、赤黒木やAVL木などの他の平衡2分探索木に比較して、実装が非常に単純であるという長所もある。また、スプレー木は簿記的データを格納する必要がないため、メモリ使用量も最小限に抑えることができる。ただし、それら他のデータ構造は最悪実行時間を保証することができ、一様なアクセスがあったときでも効率を落とさない。 基本的なスプレー木での最悪ケースの1つとして、木に格納されている全要素にソートされた順序で逐次的にアクセスする場合が挙げられる。これ（n 回アクセスして、毎回 O(log ''n'') の操作を行う）をすると最終的に木構造は完全に非平衡になる。そして、その状態の木でソート順の先頭の要素を探索すると、木を平衡に戻す操作に O(n) の操作が必要になる。これはかなりの遅延になるが、全体としての償却性能は O(log ''n'') になっている。ただし、最近の研究によると、無作為な平衡化を行うことでこのような非平衡状態を防ぎ、他の平衡2分探索木と似たような性能を得られることが示されている。 スプレー木の永続版を作ることもでき、前の版と更新後の新しい版の両方にアクセスできるようにする。この場合、更新には O(log ''n'') の償却メモリ領域が必要である。 他の平衡2分探索木とは逆に、スプレー木は各ノードが同一のキーを持つ場合にうまく機能する。同一のキーがある場合でも償却性能は O(log ''n'') である。どんな操作をしても、木構造内の同一キーのノードの順序は保たれる。これは安定ソートと似たような特徴である。うまく設計すれば、探索によって指定されたキーを持つ左端または右端のノードを取り出すことができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「スプレー木」の詳細全文を読む スポンサード リンク
|