スプレー操作

ウィキペディア小見出し辞書

スプレー操作

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:14 UTC 版)

「スプレー木」の記事における「スプレー操作」の解説

ノード x にアクセスするとき、x についてのスプレー操作によってそれを根に移動させる。スプレー操作は x を根に近い方へ移動させるスプレーステップを次々に実行することで行われる。アクセスの度にそのノードに対してスプレー操作を行うことで、最近アクセスされたノードは根の近くに保持されるので、木の平衡を大まかに保ったまま、必要な償却時間制限を達成できる。 個々のステップには、以下の3要素が関係する。 x は親ノード p の右の子ノードか、それとも左の子ノードか p は根ノードか否か p は親ノード g の右の子ノードか、それとも左の子ノードか スプレーステップには、以下の3種類が存在する。 zig ステップ p が根ノードの場合に実行される。木の回転は、x と p を繋ぐ辺の上で行われる。zig ステップはスプレー操作前の状態で x の深さが奇数だったときだけ、スプレー操作の最後のステップとして実行される。 zig-zig ステップ p が根ノードではなく、x も p も親に対して共に右の子ノード、あるいは共に左の子ノードの場合、実行される。下図では、x も p の左の子ノードの場合を示している。木の回転は p とその親である g を繋ぐ辺の上で行われ、次に x と p を繋ぐ辺の上で行われる。zig-zig ステップは、Allen と Munro が rotate to root と名づけた手法とスプレー木の唯一の違いである。 zig-zag ステップ p が根ノードではなく、x が右の子ノードで p が左の子ノードの場合（または逆の組合せの場合）、実行される。木の回転はまず x と p を繋ぐ辺の上で行われ、次に x と新たな親ノードとなった g とを繋ぐ辺の上で行われる。