Union Find は link by size (または link by rank) と経路圧縮を組み合わせることで、各操作をならし \(O(\alpha(n))\) にできることが知られている（\(\alpha\) はアッカーマンの逆関数、\(n\) は頂点数）。このならし計算量は理論的に最良であるが、最悪計算量は \(O(\log n)\) になる（例えば二項木の Find ：Union Find の計算量 (1)）。そこで、この記事では理論的に最良な最悪計算量 \(O(\log n/\log\log n)\) を実現する Union Find を紹介する[1]。
アイディアは、Union と Find の計算量のトレードオフを傾けることである。ただし、ここでの Union とは、Find で根を見つけた後の操作を指す。Union by Rank (Size) は Union \(O(1)\), Find \(O(\log(n))\) であったが、branching factor を \(\Theta(\log(n)/\log\log(n))\) にして、二つの計算量を同量にする。
アルゴリズムの解説
次の三つの条件を満たす根付き木を k-UF 木 (k > 1) と定義する。
- 根と葉以外の頂点は \(k\) 個以上の子を持つ。
- 根は２個以上の子を持つ。
- 葉の深さは全て等しい。
このような木は葉の数 \(n\) に対し高さが \(O(\log_k n)\) である。特に \(k = O(\log n)\) とすると、高さが \(O(\log n/ \log \log n)\) になって、Find の計算量削減が期待できる。条件２は最悪計算量の改善に非本質なので、この記事では忘れてもよい。
k-UF 木の根を集合の名前を表す頂点、葉を集合の元を表す頂点とする。それ以外の頂点は根と葉を繋ぐ以外に意味のない頂点とする。根に載せる頂点の名前は代表元のラベルにすることが多い。二つの集合を合併（Union）し新たな集合を作るとき、対応する二つの k-UF 木を合併して新たな k-UF 木を作る。また、ある元 v の属する集合の名前を得る（Find）ときには、v に対応する k-UF 木の葉から根まで親を辿る。
Find の計算量は木の高さ \(O(\log_k n)\) で抑えられる。Union の計算量については、次の事実が成り立つ。
次のようにすれば、A と B を合併した k-UF 木が \(O(k)\) で構築できる：
- v が B の根でない場合：
- r の子の数が k 以上ならば r を v の兄弟として繋ぎ替える。
- r の子の数が k 未満ならば r の子を r から分離して v の子に繋ぎ替える。r は破棄する。
- v が B の根である場合、A より B の方が根の子の数が多いと仮定しても一般性を失わない。
- r の子の数が k 以上ならば r と v を子とする新しい根を作る。
- r の子の数が k 未満ならば (i) の (2) と同様である。
それぞれの場合を図にすると次のようになる。
以上で Union が \(O(k+\log_k n)\) でできた。
初期状態の 1 元集合は k-UF 木ではないが、同じように合併できる。最悪計算量 \(O(k+\log_k n)\) は \(k = \log n / \log \log n \) のとき最小量 \(O(\log n /\log \log n)\) を取る。最悪計算量 \(O(\log n /\log \log n)\) の Union Find ができた。
ある種の Union Find っぽい問題設定ではこの計算量が Union Find の最悪計算量を最小化した値として最良であることが示せる。詳しくは参考文献を参照せよ。
参考文献
- Blum, Norbert. “On the single-operation worst-case time complexity of the disjoint set union problem.” SIAM Journal on Computing 15.4 (1986): 1021-1024.
関連記事
branching factor を調節するアイディアは 永続 Union Find や 多分ヒープによるプリム法 でも用いられている。
Comments