2012年3月19日月曜日

Splay Tree への insert の amortized cost が O(log N) の証明

Purely Functional Data Structures の 5.4 で、Splay Tree に要素を insert すると、一回あたりの最悪計算量は O(N) ですが、amortized cost は O(log N) になる、という話の証明です。

まず insert の定義を確認します。

insert x t = let (a, b) = partition x t
             in T (a, x, b)

(partition は長いので省略します。テキスト (Purely Functional Data Structures) の P.50 or P.198 を見てください。)
partition のポイントは二段ごとに再帰していくこと。あるノードについて partition が呼ばれると、その中で、孫ノードに対して再帰的に partition が呼ばれます。なので、insert の計算量は O(N) となりますが、amortized cost が O(log N) となることを証明します。

始めにいくつか関数を定義します。
  • #t := t (tree) に含まれるノードの数 + 1
  • φ(t) := log(#t)
  • Φ(t) := sum $ map φ $ nodes t (t に含まれる全てのノードに対して φ を適用した結果の和)
次に partition の actual cost を T(t)、amortized cost を A(t) とすると、ポテンシャル関数 Φ(t) を使って次のような関係が成立します。
A(t) = T(t) + Φ(a) + Φ(b) - Φ(t)
ここで、a, b は、t について呼び出した partition の結果である sub-tree です。

補題として、A(t) <= 1 + 2φ(t) = 1 + 2log(#t) を示します (Theorem 5.2)。これが成り立つとすると、挿入後の tree を t' として、
[amortized cost of insert] = A(t) + 1 + Φ(t') - (Φ(a) + Φ(b))     (*1)
                                        = A(t) + 1 + φ(t')
                                        <= 1 + 2log(#t) + 1 + log(#t + 1)
                                         2 + 3log(#t)
(*1) insert の amortized cost は、partition の amortized cost と、データコンストラクタの適用と、ポテンシャルの変化の和
となり、insert の amortized cost が O(log N) であることがわかります。

さて、partition の再起呼び出しには zig-zig ケースと zig-zag パターンの 2 つがあります。(冗長に書くと、左の子を辿るのを zig, 右の子を辿るのを zag として、zig-zig, zig-zag, zag-zig, zag-zag の 4 パターンありますが、zig-zig と zag-zag, zig-zag と zag-zig は対称な操作なのでまとめて、zig-zig と zig-zag だけを考えます)

zig-zig ケースを考えます。下の図のようなツリーを考え、partition pivot s の結果 sub-tree u が二つに分かれて、a, b になったとします。

partition の amortized cost A(s) を展開していきます。
A(s) = T(s) + Φ(a) + Φ(s') - Φ(s)                                            (*2)
        = 1 + T(u) + Φ(a) + Φ(s') - Φ(s)                                     (*3)
        = 1 + A(u) - Φ(a) - Φ(b) + Φ(u) + Φ(a) + Φ(s') - Φ(s)   (*4)
        = 1 + A(u) - Φ(b) + Φ(u) + Φ(s') - Φ(s)                          (*5)
(*2) A の定義より
(*3) T(s) は、u に対して partition を呼んだコスト + 1
(*4) A の定義を T について整理したものを使って、T(u) を A(u), Φ, φ に置換
(*5) Φ(a) はキャンセル
ここで、Φ(s) と Φ(s') を φ を使ってできる限り展開すると、
Φ(s) = φ(s) + φ(t) + Φ(u) + Φ(c) + Φ(d)
Φ(s') = φ(s') + φ(t') + Φ(b) + Φ(c) + Φ(d)
となります。(b, c, d, u は内部構造が分からないので、φ で展開できないことに注意)

これを元の式に代入して整理すると、
A(s) = 1 + A(u) + φ(s') + φ(t') - φ(s) - φ(t)
となります。

u は s より小さい木なので、帰納法の過程より A(u)  <= 1 + 2φ(u) を代入すると、
A(s) <= 2 + 2φ(u) + φ(s') + φ(t') - φ(s) - φ(t)
u は t より小さく、s' は s より小さいので、φ(t) を φ(u) に置き換え、φ(s) を φ(s') に置き換えても式の大小関係は崩れない(φ(t), φ(s) の符号は負であることに注意)ので、
A(s) <= 2 + 2φ(u) + φ(s') + φ(t') - φ(s') - φ(u)
        < 2 + φ(u) + φ(t')
#u + #t' < #s なので、Lemma 5.1 (ここでは省略。テキスト参照のこと) より、
A(s) < 1 + 2φ(s) 
となり、証明終了となります。

zig-zag ケースの場合も、下図を参考にして式を展開をしていくと同じ結果が得られます。


数式を blog で書くのつらいなぁ・・・。

0 件のコメント:

コメントを投稿