Union-Find の経路圧縮とサイズによる重み付け：α(n) はどの実装に付く計算量か

Union-Find（素集合データ構造）の計算量は「ほぼ O(1)」「1 操作あたり O(α(n))」と紹介されることがよくあります。ただ、これには条件があります。サイズ（またはランク）による重み付けと経路圧縮を両方使う実装であること、そして対象が 1 回の操作ではなく、空の状態から始めた操作列全体であることです。Sedgewick・Wayne『Algorithms, 4th Edition』の公式サイト（algs4）にある実装のドキュメントには、両方を使った実装でも union と find の 1 回は最悪の場合 Θ(log n) 時間かかると書かれています。

以下では algs4 の 4 つの実装を基準に、それぞれの手法が parent 配列をどう変え、どの計算量の記述がどの実装に付いているのかを分けて見ていきます。

parent 配列と find

quick-union 系の実装では、要素ごとに parent[i] へ同じ集合の別の要素（または自分自身）を記録します。parent[i] == i の要素が根で、find はリンクをたどって根まで上ります。2 つの要素の根が同じなら同じ集合です。union は 2 つの根を求め、一方の根をもう一方の下につなぎます。

そのため find のコストは、出発したノードの深さで決まります。algs4 の 1.5 節はコストを配列アクセスの回数で数えており、quick-union の find は 1 にノードの深さの 2 倍を足した回数だけ配列にアクセスするという命題を置いています。この先の手法はどれも、この深さを抑えるためのものです。

サイズによる重み付け：小さい木を大きい木の下へ

重み付けのない quick-union は、どちらの根をどちらの下につなぐかを選びません。n 要素に対して union(i, i+1) を i = 0 から順に呼ぶと、algs4 の QuickUnionPathCompressionUF（id[rootP] = rootQ）は 0 → 1 → … → n−1 とつながる鎖を作ります。この間の find は毎回根から出発するので圧縮する経路がなく、0 の深さは n−1 になります。

WeightedQuickUnionUF は木ごとの要素数を size[] に記録し、小さい木の根を大きい木の根の下につなぎます。

if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; }
else                           { parent[rootQ] = rootP; size[rootP] += size[rootQ]; }

サイズが同じときは else 側に進み、q の根が p の根の下に入ります。同じ union(i, i+1) の列をこの実装に渡すと、すべての要素が 0 の直下に付き、最大の深さは 1 です。

algs4 は重み付き quick-union について、n 要素から作った森ではどのノードの深さも lg n を超えないという命題と、その結果 find・connected・union の最悪コストの増加オーダーが log n になるという系を示しています。これは経路圧縮のない実装についての記述で、個々の操作の最悪ケースです。

要素 8 個（0〜7）で確かめます。

呼び出し	parent[0..7]	変わった size
初期状態	0 1 2 3 4 5 6 7	すべて 1
union(0,1)	0 0 2 3 4 5 6 7	size[0]=2
union(2,3)	0 0 2 2 4 5 6 7	size[2]=2
union(0,2)	0 0 0 2 4 5 6 7	size[0]=4
union(4,5)	0 0 0 2 4 4 6 7	size[4]=2
union(6,7)	0 0 0 2 4 4 6 6	size[6]=2
union(4,6)	0 0 0 2 4 4 4 6	size[4]=4
union(0,4)	0 0 0 2 0 4 4 6	size[0]=8

最後の size 配列は 8 1 2 1 4 1 2 1 です。7 から根までは 7 → 6 → 4 → 0 でリンク 3 本、ちょうど lg 8 です。毎回同じサイズの木どうしを合わせたので、この例は上限にぴったり届きます。この 7 回の union の中の find はどれも根から出発しているため、経路圧縮を有効にした実装で同じ呼び出しをしても配列はまったく同じになります。

経路圧縮：通ったノードを根に直接つなぐ

algs4 の 1.5 節は、すべてのノードが根に直接つながっているのが理想だが、多くのリンクを一度に書き換えるコストは払いたくない、と述べたうえで、find が実際に調べたノードだけを根に直接つなぐ方法を紹介しています。WeightedQuickUnionPathCompressionUF の find は 2 回走査します。1 回目で根を求め、2 回目で経路上のノードを 1 つずつ根につなぎ直します。

int root = p;
while (root != parent[root]) root = parent[root];
while (p != root) { int newp = parent[p]; parent[p] = root; p = newp; }
return root;

上の状態で find(7) を呼ぶと、1 つ目のループがリンクを 3 本たどって根 0 を見つけ、2 つ目のループが 7、6、4 を 0 に直接つなぎます。

	parent[0..7]
find(7) の前	0 0 0 2 0 4 4 6
find(7) の後（完全な圧縮）	0 0 0 2 0 4 0 0

いくつか補足します。

この find もリンクを 3 本たどっています。圧縮は次の find を安くするだけで、今の find は短くなりません。algs4 のドキュメントがこの実装でも union と find を最悪 Θ(log n) と書いている理由がここに表れています。
根は変わりません。algs4 のドキュメントは、集合の代表元が変わりうるのは union で集合そのものが変わるときだけで、find では変わらないと書いています。圧縮が変えるのは木の形だけです。
size[] は更新されません。圧縮の後、4 の下には 5 しか残っていませんが、size[4] は 4 のままです。ソースのコメントにも、根でない i の size は正しいとは限らないと書かれています。union が比べるのは size[rootP] と size[rootQ]、つまり根の値だけなので、動作に問題はありません。圧縮は要素を別の木へ移さないので、根の size は引き続きその集合の要素数です。

経路半減：1 回の走査で祖父へ

1.5 節で main() から動的連結性の問題を解いているクラス UF は、別の組み合わせを使っています。サイズの代わりにランクで重み付けし、経路圧縮は半減（halving）方式です。

while (p != parent[p]) {
    parent[p] = parent[parent[p]];
    p = parent[p];
}
return p;

1 回の走査で、通るノードを祖父につなぎ、次はその祖父へ飛びます。そのため経路上のノードは 1 つおきにしか書き換えません。先ほどの 7 回の union を UF に渡すと、この例ではすべての union が同じランクどうしなので parent 配列はサイズで重み付けしたときと同じになり、ランクは 3 0 1 0 2 0 1 0 です。ここで find(7) を呼ぶと結果が変わります。

	parent[0..7]
find(7) の前	0 0 0 2 0 4 4 6
find(7) の後（経路半減）	0 0 0 2 0 4 4 4

7 は祖父の 4 へ移り、4 はすでに祖父が 0 なのでそのまま、6 は飛ばされるので手を付けられません。完全な圧縮のように一度で平らにはなりませんが、もう一度 find(7) を呼べば 7 は 0 に移ります。その代わり根を探すループ 1 つで済み、1.5 節の Web 演習は経路半減をより単純な戦略として紹介しています。

どの記述がどの実装に付くのか

次の表は、algs4 のソースにあるクラスドキュメントと 1.5 節本文の記述をそのまま整理したものです。

実装	重み付け	経路圧縮	1 回の操作（最悪）	操作列全体
`WeightedQuickUnionUF`	サイズ	なし	union・find Θ(log n)。深さ ≤ lg n は本文の命題	記述なし
`QuickUnionPathCompressionUF`	なし	完全な圧縮	記述なし	union・find・connected が償却で対数時間
`WeightedQuickUnionPathCompressionUF`	サイズ	完全な圧縮	union・find Θ(log n)	m 回の操作で O(m α(n))
`UF`	ランク	経路半減	union・find Θ(log n)	m 回の操作で O(m α(n))

O(m α(n)) の正確な条件はこうです。n 要素の空のデータ構造から始めて、union と find を任意の順に混ぜて m 回行うと合計 O(m α(n)) 時間かかる、というもので、α(n) はアッカーマン関数の逆関数です。「1 操作あたり α(n)」はこの合計を m で割った償却コストです。入力がランダムだという仮定も入っていません。償却という考え方になじみがなければ、動的配列の追加が O(1) になる理由で同じ形の計算を追えます。

出典が述べている範囲

これらの数字が algs4 の資料でどういう形で出てくるのかも分けておきます。

深さ ≤ lg n と最悪 log n のコストは、1.5 節本文の命題と系です。
重み付けなしの経路圧縮の償却コストが対数であること、重み付けと経路圧縮を併用したときの償却コストが逆アッカーマン関数で抑えられることは、演習 1.5.12 と 1.5.13 に付いた注（Note）に「知られている」と書かれているだけです。1.5.13 の注は、実際に現れうるどんな n でもこの値は 5 未満だと付け加えています。
O(m α(n)) は WeightedQuickUnionPathCompressionUF と UF のクラスドキュメントにある記述です。

この記事で開いた資料には α(n) の上限の証明はなく、元の論文も確認していません。そのため、ランクとサイズのどちらが良いか、経路半減と完全な圧縮のどちらが実際に速いかといった比較はしていません。上の表は、それぞれの実装について algs4 のドキュメントが書いている範囲までしか述べていません。

確認した資料

いずれも 2026-10-18 に確認しました。

Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, 1.5 Case Study: Union-Find
WeightedQuickUnionUF.java
QuickUnionPathCompressionUF.java
WeightedQuickUnionPathCompressionUF.java
UF.java