Scapegoat Tree

個人的メモ

ここで $n$ 頂点の平衡二分探索木 $T$ が最適であるとは任意の $n$ 頂点の平衡二分探索木 $T'$ について $height(T) \le height(T')$ が成り立つことと考えることにする.
定数 $\alpha$ を $1 / 2 < \alpha < 1$ となるように定め(実装では $2 / 3$ としている), 要素数を $n$ としたとき必ず任意の頂点の深さが $\lfloor \log_{1 / \alpha} n \rfloor + 1$ 以下となるように更新を行う.
まず変数 $M$ を前回の restart 操作以降での最大の要素数と定義する(restart 操作は後に定義するが $M$ は現在の要素数を $n$ としたとき常に $n \le M \le n / \alpha$ が成り立つようにする). 要素を erase する場合は単純に平衡二分木から削除するが, (削除後の要素数) $< \alpha \cdot M$ が成り立つときは restart 操作を行う. restart 操作とは現在の存在する要素から成る最適な平衡二分木を再構築することで, これは要素数について線形時間で可能である. また restart 操作後 $M =$ (現在の要素数) に更新をする. このとき任意の頂点についてその深さが $\lfloor \log_{1 / \alpha} M \rfloor$ 以下となっていることに注意する.
次に要素 $x$ を insert する場合は $M = \max(M$, insert 前の要素数$ + 1)$ に更新したあと要素を二分探索木の葉の位置に挿入し, その深さを $d$ としたとき $d \le \lfloor \log_{1 / \alpha} M\rfloor$ が成り立つなら 木は balanced である, 成り立たないなら balanced でないと考える.
木が balanced で無かった場合は $x$ の先祖のある要素の組 $\{y, z\}$ ($y$ は $z$ の親) について ($z$ を根とする部分木のサイズ) > $\alpha$ $\cdot$ ($y$ を根とする部分木のサイズ) が成り立つことが背理法から分かる. このとき頂点 $y$ のことを scapegoat と呼ぶ. scapegoat は複数存在しうるが, 例えば $x$ から根方向に先祖をたどって初めて見つかる scapegoat を根とする部分木について線形時間で最適な平衡二分探索木を再構築するということをする.
今帰納的に考えると $x$ を insert する前は全ての頂点についてその深さが $\lfloor \log_{1 / \alpha} M\rfloor$ 以下であることが言え, また ($z$ を根とする部分木のサイズ) > $\alpha$ $\cdot$ ($y$ を根とする部分木のサイズ) $\ge (1 / 2) \cdot$ ($y$ を根とする部分木のサイズ) も成り立つ. よって $y$ の左の子を根とする部分木と右の子を根とする部分木の間のサイズの差は $2$ 以上あり, $y$ を根とする部分木は飽和していない. つまり $y$ を根とする部分木について最適な平衡二分探索木を再構築すると全ての頂点の深さは $\lfloor \log_{1 / \alpha} M\rfloor$ 以下となる. ゆえにうまく更新ができていることが分かる.
結局アルゴリズム中常に $n \le M \le n / \alpha$ および任意の頂点の深さが $\lfloor \log_{1 / \alpha} M\rfloor$ 以下が成り立っているため, たしかに任意の頂点の深さが $\lfloor \log_{1 / \alpha} n \rfloor + 1$ 以下となっている.
計算量については例えば $y$ を根とするサイズ $m$ の部分木を再構築することになった場合は前回 $y$ を根とする部分木について再構築したときもしくは $y$ を insert したとき以来 $y$ を根とする部分木内で少なくとも $((2 \alpha - 1) / (2 - 2 \alpha)) \cdot (m - 1)$ 回の挿入もしくは $(1 - 1 / (2 \alpha)) \cdot (m - 1)$ 回の削除が起こっているので再構築でかかる計算量 $\O(m)$ はポテンシャル的にペイする(細かい係数は計算ミスしてるかもしれない). また restart 操作についても要素数 $m$ の最適な平衡二分木を構築することになった場合, 前回 restart 操作を行ったときもしくはアルゴリズムが開始したとき以来少なくとも $(1 / \alpha - 1) \cdot m$ 回の erase 操作が起きているのでこちらもポテンシャル的にペイする.
よってポテンシャル解析は scapegoat を根とする部分木について再構築するパートにかかる部分が本質で上記の説明から新たに要素 $x$ を挿入する際に木の根と葉 $x$ の間の頂点に $\O(1)$ のポテンシャルを乗せることで解析がうまく回ることが分かる. ゆえに任意の頂点について深さが $\lfloor \log_{1 / \alpha} n \rfloor + 1$ 以下である事実と合わせてならし計算量は $\O(\log n)$ となることが分かる.