スプレー木
シーケンス S を実行するコストは O ( m ( log  n + 1 ) + n log  n ) {\displaystyle O(m(\log n+1)+n\log n)\,\!} である。すなわち、スプレー木は少なくとも n 回のアクセスのシーケンスにおいて、静的平衡2分探索木と同程度の性能を発揮する。