スプレー木（スプレーき、）は、平衡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") である。どんな操作をしても、木構造内の同一キーのノードの順序は保たれる。これは安定ソートと似たような特徴である。うまく設計すれば、探索によって指定されたキーを持つ左端または右端のノードを取り出すことができる。ノード "x" にアクセスするとき、"x" についてのスプレー操作によってそれを根に移動させる。スプレー操作は "x" を根に近い方へ移動させるスプレーステップを次々に実行することで行われる。アクセスの度にそのノードに対してスプレー操作を行うことで、最近アクセスされたノードは根の近くに保持されるので、木の平衡を大まかに保ったまま、必要な償却時間制限を達成できる。個々のステップには、以下の3要素が関係する。スプレーステップには、以下の3種類が存在する。要素数 "n" のスプレー木で "m" 回のアクセスのシーケンス S の最悪実行時間について、いくつかの定理と予想が存在する。スプレー木の性能に関しては、証明済みの定理だけでなく、最初のスレイターとタージャンの論文にも記載されていた証明されていない予想が存在する。この予想は動的最適性予想 (Dynamic optimality conjecture) と呼ばれ、それは基本的にスプレー木の性能が他の2分探索木アルゴリズムにある定数係数を加えた範囲内になるという予想である。動的最適性予想には、以下のような証明されていない系が存在する。

出典:wikipedia