データ構造：仮想木におけるスプレー操作のアルゴリズム

仮想木（Virtual Tree）では、一部の辺は実線（solid）として扱われ、その他の辺は破線（dashed）として扱われます。通常のスプレー操作は、実線で構成される木（solid tree）の内部でのみ実行されます。仮想木内のノード y でスプレーを行うには、以下に示す手法が用いられます。

このアルゴリズムは、木を3回走査し（各パスで1回ずつ）、その都度木を書き換えていきます。第1パスでは、ノード y から開始して実線の木内でのみスプレーを行うことで、y から木全体の根までの経路が破線に変わります。続いて、スプライシング（splicing）によってこの経路を実線に変換します。最後にノード y でスプレーを行うことで、y が木の根になります。以下、より具体的にアルゴリズムを説明します。

スプレー操作 Splay(y) のアルゴリズム

パス1

仮想木を根に向かって上方向にたどります。ただし、スプレーは実線の部分木内でのみ実行します。このパスが終了した時点で、y から根までの経路はすべて破線になります。

パス2

ノード y から上方向へたどりながら、y の各真の祖先（proper ancestor）においてスプライシングを行います。このステップが終了した時点で、y から根までの経路は実線になります。また、ノード y および元の木（第1パス実行前の木）における y のすべての子は、左の子として配置されます。

パス3

ノード y から根まで、通常の方法でスプレーを実行しながら上方向へたどります。

応用例：外部経路重みの最小化とハフマン符号

このような木構造の操作は、事前の知識を活用して確率推定の精度を高めることにも役立ちます。与えられた葉の集合に対して、外部経路の重み（external path weight）が最小となる木を構築することが目標となります。

具体例として、以下の文字出現頻度表を用いたハフマン符号の構築を示します。

文字の出現頻度表

ハフマン符号

上記の例に対応するハフマン木は下図のとおりです。