スプレー木（Splay Tree）とは？データ構造の特徴と回転操作をわかりやすく解説

スプレー木（splay tree）は、自己平衡型二分探索木の一種であり、「最近アクセスした要素には再び素早くアクセスできる」という特別な性質を持つデータ構造です。挿入・検索・削除といった基本操作は、ならし計算量 O(log n) で実行できます。

スプレー木の大きな特徴は、ランダムでない一連の操作に対して、そのパターンが事前に分からない場合でも、他の探索木よりも優れた性能を発揮することが多い点です。二分探索木における通常の操作はすべて、「スプレーイング（splaying）」と呼ばれる一つの基本操作と組み合わせて実行されます。

スプレー木の基本的な性質

各ノード a には、実数値のキー key(a) が格納されているものと仮定します。

任意の二分探索木において、ノード a の左部分木には key(a) よりも小さいキー値を持つ要素が含まれ、右部分木には key(a) よりも大きいキー値を持つ要素が含まれます。この規則により、探索効率が保たれています。

スプレー木における検索と回転操作

スプレー木では、まず通常の二分探索木と同じ手順で目的の要素 a を検索します。具体的には以下の流れです。

• 根の値とクエリ要素を比較する
• 小さければ左部分木を再帰的に探索する
• 大きければ右部分木を再帰的に探索する
• 等しければ検索完了

検索後、大まかに言えば、a の連続する祖先のペア（b = parent(a)、c = parent(b)）ごとに、特定の組み合わせの回転操作を実行します。これらの回転の結果として、a が c の位置へ移動することになります。

zig 操作

a が奇数個の真の祖先を持つ場合、残りの祖先（根の子であるノード）も別途処理する必要があります。この終端ケースでは、a と根との間の辺を回転します。このステップは「zig 操作」と呼ばれます。

zig-zig 操作

a と b がどちらもそれぞれの親に対して同じ側の子（両方とも左子、または両方とも右子）である場合、まず b とその親 c の間の辺を回転し、次に a とその親 b の間の辺を回転します。このステップは「zig-zig 操作」と呼ばれます。

zig-zag 操作

a が左子（または右子）であり、b が反対側の右子（または左子）である場合、まず a と b の間の辺を回転し、次に a と c の間の辺を回転します。このステップは「zig-zag 操作」と呼ばれます。