スプレー木
同じ要素を格納している2つのスプレー木 T 1 {\displaystyle T_{1}} と T 2 {\displaystyle T_{2}} があるとする。シーケンス S {\displaystyle S} が T 2 {\displaystyle T_{2}} において要素を前順(深さ優先順)に走査するシーケンスであるとする。このシーケンス S {\displaystyle S} を T 1 {\displaystyle T_{1}} 上で実行するコストは O ( n ) {\displaystyle O(n)} となる。
そして、その状態の木でソート順の先頭の要素を探索すると、木を平衡に戻す操作に O(n) の操作が必要になる。これはかなりの遅延になるが、全体としての償却性能は O(log n) になっている。ただし、最近の研究によると、無作為な平衡化を行うことでこのような非平衡状態を防ぎ、他の平衡2分探索木と似たような性能を得られることが示されている。
スプレー木の永続版を作ることもでき、前の版と更新後の新しい版の両方にアクセスできるようにする。この場合、更新には O(log n) の償却メモリ領域が必要である。
他の平衡2分探索木とは逆に、スプレー木は各ノードが同一のキーを持つ場合にうまく機能する。同一のキーがある場合でも償却性能は O(log n) である。どんな操作をしても、木構造内の同一キーのノードの順序は保たれる。これは安定ソートと似たような特徴である。うまく設計すれば、探索によって指定されたキーを持つ左端または右端のノードを取り出すことができる。
S {\displaystyle S} が両端キュー(デック)操作を m {\displaystyle m} 回行うシーケンスであるとする。するとスプレー木上で S {\displaystyle S} を実行するコストは O ( m + n ) {\displaystyle O(m+n)} となる。