スプレー木
要素 x {\displaystyle x} にアクセスするのに、根ノードから走査してコスト d ( x ) + 1 {\displaystyle d(x)+1} かかる2分探索木アルゴリズムを A {\displaystyle A} とする。そして、 A {\displaystyle A} において、任意の木の回転を1のコストでできるとする。 A {\displaystyle A} においてアクセスのシーケンス S {\displaystyle S} を実行するコストを A ( S ) {\displaystyle A(S)} とする。すると、スプレー木が同じアクセスをするのにかかるコストは O ( n + A ( S ) ) {\displaystyle O(n+A(S))} である。
動的最適性予想には、以下のような証明されていない系が存在する。