スプレー木
S {\displaystyle S} がスプレー木の要素の任意の順列とする。すると、 S {\displaystyle S} の順序に従って要素を削除するコストは O ( n ) {\displaystyle O(n)} である。
スプレー木の性能に関しては、証明済みの定理だけでなく、最初のスレイターとタージャンの論文にも記載されていた証明されていない予想が存在する。この予想は動的最適性予想 (Dynamic optimality conjecture) と呼ばれ、それは基本的にスプレー木の性能が他の2分探索木アルゴリズムにある定数係数を加えた範囲内になるという予想である。
スプレー木の性能がよいのは、頻繁にアクセスされるノードが根の近くになるように移動させることで、より素早くアクセスできるようにし、自動的に平衡をとり、自動的に最適化するためである。これはほとんどの用途で長所となる特徴であり、特にキャッシュやガベージコレクションのアルゴリズムの実装に便利である。
スプレー木は、平均的ケースでの効率が同程度なら、赤黒木やAVL木などの他の平衡2分探索木に比較して、実装が非常に単純であるという長所もある。また、スプレー木は簿記的データを格納する必要がないため、メモリ使用量も最小限に抑えることができる。ただし、それら他のデータ構造は最悪実行時間を保証することができる。
基本的なスプレー木での最悪ケースの1つとして、木に格納されている全要素にソートされた順序で逐次的にアクセスする場合が挙げられる。これ(n 回アクセスして、毎回 O(log n) の操作を行う)をすると最終的に木構造は完全に非平衡になる。
逐次アクセス定理とも呼ばれる。スプレー木の n 個の要素に対称的順序でアクセスすると、スプレー木の初期状態に関わらず Θ ( n ) {\displaystyle \Theta (n)\,\!} の時間がかかる。これまでに証明された最もきつい上限は 4.5 n {\displaystyle 4.5n} である。