Splay Tree

個人的メモ

self-adjusting な構造である. つまり事前に lookup クエリの確率分布を知らなくても動的によく参照されるノードは根に近く, そうでないものは根から遠い位置になるように変形される(union-find と同じ).
zig, zig-zig, zig-zag の $3$ つの回転を用いてあるノードを根にする splay と呼ばれる操作が基本になっていて, これが実装できればあとは lookup, insert, erase などは容易に実装できる.
ならし計算量については頂点 $i$ のポテンシャル $r_i$ を $r_i = \log$ (頂点 $i$ を根とする部分木内の頂点数) としてやることで splay 操作が(頂点数を $n$ として)ならし $\O (\log n)$ となることが言える(Access Lemma).
情報理論的な観点から優れたデータ構造であるという裏付けがある(メモ). しかしスプレー木の解析は往々にして困難であり, 計算量の最適性に関する未解決な命題も複数ある(特に動的平衡二分探索木についての最適性).
競技プログラミングの問題をいくつか解いた経験則で言うと, RBST より Splay Tree の方が基本速い(やはり $2$ 回連続同じノードを参照したりみたいなことをするとき Splay Tree の方が優位なのが効いている).