Splay 木概論
Splay 木の基本操作
$\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n \log(n)$（ただし $n$ は節点数）なるポテンシャル $Φ(T)$ のもと、次の操作ができる二分木です。
| クエリ | 引数 | 事前条件 | 効果 | ポテンシャル増分 | 最悪時間計算量 |
|---|---|---|---|---|---|
| $\mathtt{splay}$ | 節点 $u$ | なし | inorder を保って $u$ が根になるように変形する | $O(\log(n)) - h(u)$ | $O(h(u))$ |
従って次のことがわかります。
- $\mathtt{splay}$ をばかりを $q$ 回連続して呼んだ場合、$O( (n + q)\log(n))$ 時間かかります。（なお実コストのほうで解析すると $O(nq)$ であることもわかり、$q = o(\log(n))$ のときはこちらのほうが良い評価です。）
- $q$ 回の $\mathtt{splay}$ の前後に実コスト $O(h(u))$ の別の操作（$\mathtt{find}$ など）の操作を挟んでも同じ評価ができます。
ポテンシャル
各節点 $u$ に対して $u$ の部分木の節点数を $\mathtt{size}(u)$ とおき、$\rank(u) = \log(\mathtt{size}(u))$ とおきます。このときスプレー木 $T$ のポテンシャルは次のように定義されます。このポテンシャルは常に $0$ 以上 $n \log(n)$ 以下です。
$$ Φ(T) = \sum_ { u \in T } \rank(u) $$
マージ可能順序集合データ構造
これはマージ可能順序集合データ構造（ただしもちろんマージは $\max(T) ≤ \max(U)$ のときだけやっていいやつです）として使うことができます。「事前条件」と「効果」を省略しているので若干の曖昧性が残っていますが、この記事の主題ではないため重要ではありません。
| クエリ | 引数 | 実装 | ポテンシャル増分 | 最悪時間計算量 |
|---|---|---|---|---|
| $\mathtt{find}$ | キー $k$ | $k$ の場所を根から探索して、見つけた後で $\mathtt{splay}$ する | $O(\log n) - h(u)$ | $O(h(u))$ |
| $\mathtt{merge}$ | スプレー木 $T, U$ | $T$ の最も右の節点 $\max(T)$を $\mathtt{splay}$ して、$U$ をその右の子とする | $O(\log |T| + \log |U|) - h(\max(T))$ | $O(h(\max(T))$ |
| $\mathtt{split}$ | スプレー木 $T$, キー $k$ | $k$ 以上の最も左の $u$ を根から探索して、 $\mathtt{splay}$ し、根の左の子を切り離す | $O(\log n) - h(u)$ | $O(h(u))$ |
| $\mathtt{insert}$ | スプレー木 $T$, キー $k$ | $\mathtt{split}(k)$ し、新たにキー $k$ の節点を作ってそれで join する | $O(\log n) - h(u)$ | $O(h(u))$ |
| $\mathtt{delete}$ | スプレー木 $T$, キー $k$ | $\mathtt{find}$ で値の有無を確認したあと、$\mathtt{split}(k)$ し、右側の木の根と右の子と切り離す | $O(\log n) - h(u)$ | $O(h(u))$ |
従って次のことがわかります。
- $\mathtt{find}, \mathtt{insert}, \mathtt{delete}$ をばかりを $q$ 回連続して呼ぶと $O( (n + q)\log(n))$ 時間（もちろん $O(nq)$ 時間でもあります）
- Splay 木の多重集合に対して、$\mathtt{find}, \mathtt{insert}, \mathtt{delete}, \mathtt{merge}, \mathtt{split}$ をばかりを $q$ 回連続して呼ぶと $O( (n + q)\log(n))$ 時間（ただし $n$ はこの多重集合内の splay 木の節点の総数）（もちろん $O(nq)$ 時間でもあります）
ポテンシャル増分に関する証明
$\mathtt{splay}$ 以外について
$\mathtt{splay}$ 以外については $\mathtt{splay}$ に関する解析結果を認めると簡単です。
| クエリ | 証明 |
|---|---|
| $\mathtt{split}$ | $\mathtt{splay}$ の効果のほかには、辺の消滅でポテンシャルが減少するだけなのでよいです |
| $\mathtt{merge}$ | $\mathtt{splay}$ の効果のほかには、辺を張ることで根のポテンシャルが $\log(|T| + |U|) - \log(|T|)$ 増加するだけなのでよいです |
| $\mathtt{delete}$ | $\mathtt{split}, \mathtt{merge}$ の効果のほかには、根と右の子の切り離しでポテンシャルが減少するだけなのでよいです |
| $\mathtt{insert}$ | $\mathtt{split}, \mathtt{merge}$ の効果のほかには、根による join でポテンシャルが $\log(|T|)$ 増加するだけなのでよいです |
$\mathtt{splay}$ について
Zig, zig-zag, zig-zig の $3$ 通りそれぞれについて、ポテンシャル増分は次のようになります。ただし $x$ の定義はまあなんかあれ（TODO）で、$p$ は操作前の木における $x$ の親、$g$ は操作前の木における $p$ の親です。また表中の $\rank$ はすべて操作前の木における $\rank$です。
| 操作 | ポテンシャル増分 |
|---|---|
| $\mathtt{zig}(x)$ | $O(\rank(p) - \rank(x))$ |
| $\mathtt{zigZag}(x)$ | $O(\rank(g) - \rank(x)) - 2$ |
| $\mathtt{zigZig}(x)$ | $O(\rank(g) - \rank(x)) - 2$ |
この $-2$ がものすごく大事です。Zig ステップが高々 $1$ 回であることから、この $-2$ をすべて足し合わせると $-2 \lfloor h(u) / 2 \rfloor = O(1) - h(u)$ になるわけです。またそれ以外の項を足し合わせると $O(\rank(\mathtt{root}(T)) - \rank(u)) = O(\log(n))$ になることもわかりますから、結局すべて合計すると $O(\log(n)) - h(u)$ になるわけです。
$\mathtt{zig}$ について
次のようになります。ただし $a ∘ b = a + 1 + b$ により、演算子 $∘$ を定義しました。
$$ \exp(ΔΦ) = \frac{a∘b∘c}{a∘b} \cdot \frac{b∘c}{a∘b∘c} ≤ \frac{a∘b∘c}{a∘b} $$
これより $ΔΦ ≤ \rank(p) - \rank(x)$ となります。
$\mathtt{zigZag}$ について
次のようになります。なお最後の不等式は AM–GM 不等式 $x y ≤ \left(\frac{x + y}{2} \right) ^ 2$ を用いました。
$$ \begin{aligned} \exp(ΔΦ) &= \frac{a∘b∘c∘d}{b∘c} \cdot \frac{a∘b}{a∘b∘c} \cdot \frac{c∘d}{a∘b∘c∘d} \\ &= \frac{a∘b∘c∘d}{b∘c} \cdot \left( \frac{a∘b∘c∘d}{a∘b∘c} \cdot \frac{a∘b}{a∘b∘c∘d} \right) \cdot \frac{c∘d}{a∘b∘c∘d} \\ &≤ \left(\frac{a∘b∘c∘d}{a∘b}\right) ^ 2 \cdot \frac{a∘b}{a∘b∘c∘d} \cdot \frac{c∘d}{a∘b∘c∘d} \\ &≤ \left(\frac{a∘b∘c∘d}{a∘b}\right) ^ 2 \cdot \left(\frac{1}{2}\right) ^ 2 \end{aligned} $$
これより $ΔΦ ≤ 2(\rank(g) - \rank(x)) - 2$ となります。
$\mathtt{zigZig}$ について
次のようになります。なお最後の不等式は AM–GM 不等式 $x y ≤ \left(\frac{x + y}{2} \right) ^ 2$ を用いました。
$$ \begin{aligned} \exp(ΔΦ) &= \frac{a∘b∘c∘d}{a∘b} \cdot \frac{b∘c∘d}{a∘b∘c} \cdot \frac{c∘d}{a∘b∘c∘d} \\ &≤ \frac{a∘b∘c∘d}{a∘b} \cdot \frac{a∘b∘c∘d}{a∘b} \cdot \frac{c∘d}{a∘b∘c∘d} \\ &≤ \left(\frac{a∘b∘c∘d}{a∘b}\right) ^ 3 \cdot \frac{a∘b}{a∘b∘c∘d} \cdot \frac{c∘d}{a∘b∘c∘d} \\ &≤ \left(\frac{a∘b∘c∘d}{a∘b}\right) ^ 3 \cdot \left(\frac{1}{2}\right) ^ 2 \end{aligned} $$
これより $ΔΦ ≤ 3(\rank(g) - \rank(x)) - 2$ となります。
証明まとめ
以上より $\mathtt{splay}$ によるポテンシャル増分は $3(\log(n) - \rank(u)) - 2\lfloor h(u) / 2 \rfloor$ 以下であることがわかりました。
