如何證明替罪羊樹的均攤複雜度？

01-08

當然是選擇。。用勢能法分析啦~

我們知道，一個結點 $v$ 被稱為 α-weight-balanced 當且僅當 $weight(left(v)), weight(right(v)) leq alpha cdot weight(v)$ ，通常定義 $weight(v) = size(v) + 1$ ，這會使一些分析變得簡單。（也使weight-balanced tree不需要考慮邊界情況）

定義 $Delta(v) = |weight(left(v)) - weight(right(v))|$ ，那麼可以看出 α-weight-balanced 相當於 $Delta(v) leq (2alpha - 1) cdot weight(v)$ 。

設重構操作的時間為 $k cdot size + Theta(1)$ ，定義樹 $T$ 的勢函數 $Phi(T) = frac k {2 alpha - 1} sum_{v in T}Delta(v)$ 。

每次插入會使路徑上的所有結點 $v$ 的 $Delta pm 1$ ，此過程的

$egin{align} 均攤代價 = 實際代價 + Delta Phi \ leq height(T) + frac k {2 alpha - 1} cdot height(T) \ = (frac k {2 alpha - 1} + 1) cdot height(T) end{align}$

注意到 $height(T) leq ?log_{frac 1 α}(weight(T))?$ ，可得

$均攤代價 leq (frac k {2 alpha - 1} + 1) cdot log_{frac 1 alpha}(weight(T)) = O(log(size(T)))$

對於每次重構，有 $Delta(v) > (2alpha - 1) cdot weight(v)$ ，那麼

$egin{align} 均攤代價 = 實際代價 + Delta Phi \ leq (k cdot weight(v) + Theta(1)) + (Theta(1) - frac k {2 alpha - 1} cdot Delta(v)) \ leq Theta(1) + k cdot weight(v) - frac k {2 alpha - 1} cdot (2alpha - 1) cdot weight(v)) \ leq Theta(1) + k cdot weight(v) - k cdot weight(v) \ = Theta(1) end{align}$

所以，替罪羊樹一次插入的均攤代價為 $O(log(size(T)))$ 。