Union-Find data structure

次の2つの操作を高速で実行することのできるデータ構造にUnion-Findと呼ばれるものがある.

  • Find: どの集合に属しているかを決定する.
  • Union: 2つの集合を1つにする.

聞いたことはあってもきちんと理解していないので少し勉強してみる.

実装

とりあえずjavaで書いてみた.

import static java.util.Arrays.*;
class UnionFind {
    private int[] data;
    public UnionFind(int size) {
        data = new int[size];
        fill(data,-1);
    }
    int find(int x){
        return (data[x]<0)? x : (data[x] = find(data[x]));
    }
    boolean union(int x, int y){
        x = find(x);
        y = find(y);
        if(x!=y){
            if(data[y]<data[x])data[x]=y;
            else if(data[y]>data[x])data[y]=x;
            else data[data[y]=x]--;
        }
        return x!=y;
    }
    int rank(int x){
        return -data[find(x)]-1;
    }
}

かなりシンプルなデータ構造である.
ポイントをまとめると

  • 子が親のノードへのリンクを持つ有向森
  • 根は葉からの高さ(ランク)のマイナスを持つ
  • union/findを行うときに木の高さを低くする

これにより,union/findのならしコストはとなるらしい.
ただし,アッカーマン関数逆関数である.

アッカーマン関数逆関数ってなんぞや

アッカーマン関数の定義式は

とてつもなく大きな数を返す関数として有名である.

この関数は原始帰納的関数ではないが帰納的関数ではある.
この辺りの証明は昔がんばったものがある.

このアッカーマン関数を使って逆関数と定義すると,
一回の操作辺りのならしコストはとなる.
ちなみに,である.

分割統治法

Union-Findの解析の準備として分割倒置法について考える.

典型的な分割倒置法は次のような形である.

  • サイズが1ならば結果は自明
  • サイズが1より大きいとき
    • サイズがf(n)未満の部分問題に分割
    • n/f(n)個の部分問題をそれぞれ再帰的に解く
    • 解を統合する

計算量をX(n)とすると,

これの解の一つとして
を考える.

ただし,

である.


具体的なに対するは次のようになる.

Union-Findの解析

結局,分割統治を行って解析する.
戦略としてはまずUnionだけについて考えて,次にFindを一般化したものを考え解析する.

定義 ランク

ノードxについてランクr(x)を葉からの高さ(の最大値)として定義する.

補題

ランクがrであるようなノードは2^r以上のノードからなる部分木の根である.

証明は帰納法より明らか

定義 rank forest

任意のノードxと任意のi ([tex:0\le i

補題

\mathcal{F}を最大のランクがrであるrank forestとし,Xをそのノードの集合とする.

また,

  • (top)
  • (bottom)

とする.

このとき,はrank forestであり,
である.

証明は,rank forestになるのは自明.
になるのは1段づつしたから削ることを考えればよい.


定義

f(m,n,r)をノード数がnの最大ランクがrのrank forestにおいて,findがm回来るときの最大コストと定義する.

自明な上界として

補題

ならば

証明はとおき,
を変形.


定義

関数g:\mathbb{N}\to\mathbb{N}についてg^\diamond=(\lceil \log_2\rceil\circ g)^*と定義する.

定義

関数 J_k(r)

と定義する.

J_k(r)アッカーマン関数逆関数になっていることに注意!


補題

任意のkについて

証明は上の補題を自明な上界に繰り返し用いればよい.


定理

Union-Findの計算量は

証明は上の補題を適用



まとめ

アルゴリズムは簡単だが解析がやたら難しい.
まだ,完全には理解していないし,間違った記述をしているところがありそうなので,気づいた方はご指摘ください.
(かなり端折った証明をしているからこれだけでは理解できないだろうけど...)