データ構造のスプレー木

プレイツリーは、最近アクセスした要素がすぐに再びアクセスできるという追加のプロパティを備えた、自己平衡型のバイナリ検索ツリーとして定義されます。挿入、検索、削除などの基本的な操作は、O（log n）償却時間のスプレーツリーによって実行されます。非ランダム操作の多くのシーケンスでは、シーケンスの特定のパターンが不明な場合でも、スプレーツリーは他の検索ツリーよりもうまく機能します。二分探索木の通常の操作はすべて、スプレイと呼ばれる1つの基本的な操作に結合されます。

ノードaごとに、実数キー（a）を格納するとします。

任意の二分探索木では、任意のノードaの左側のサブツリーにはkey（a）の値よりも小さい「key」値を持つアイテムが含まれ、ノードaの右側のサブツリーにはkey（a）の値よりも高い「key」値を持つアイテムが含まれます。

スプレーツリーでは、最初にクエリアイテムを検索します。たとえば、通常の二分探索ツリーのように、クエリアイテムをルートの値と比較します。それより少ない場合は左側のサブツリーを再帰的に検索し、それより高い場合は再帰的に検索します。右のサブツリーであり、それが等しい場合は完了です。次に、非公式に言えば、連続する祖先のすべての互いに素なペアf a、たとえばb =parent（a）とc =parent（b）を調べ、特定の回転のペアを実行します。これらの回転の結果として、cの代わりにaが使用されます。

aに奇数の適切な祖先がある場合、（ルートの子である）aの祖先も、ターミナルケースでは、別の方法で処理する必要があります。つまり、aとルートの間でエッジを回転させます。このステップはジグステップと呼ばれます。

aとbが両方とも左であるか、両方がそれぞれの親の右の子である場合、最初にbとその親cの間のエッジを回転させ、次にaとその親bの間のエッジを回転させます。このステップは、ジグジグステップと呼ばれます。

aが左（それぞれ右）の子で、bが右（それぞれ左）の子である場合、最初にaとbの間、次にaとcの間でエッジを回転します。このステップは、ジグザグステップとして示されます。