素集合森
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:02 UTC 版)
素集合森 (disjoint-set forest) はそれぞれの集合を木構造で表したデータ構造で、各ノードには親ノードへの参照がある。1964年、Bernard A. Galler と Michael J. Fischer が考案したが、詳細な解析にはその後何年かかかった。 素集合森では、各集合の代表は木構造の根となる。Findは親ノードへのリンクを根に到達するまでたどっていく。Unionは2つの木構造を1つにする操作であり、どちらかの根が全体の根となる。以下に素集合森の実装例を擬似コードで示す。 function MakeSet(x) x.parent := x function Find(x) if x.parent == x return x else return Find(x.parent) function Union(x, y) xRoot := Find(x) yRoot := Find(y) xRoot.parent := yRoot この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。しかし、これを改善する方法が2つある。 第一の方法は union by rank と呼ばれ、Union操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するにはrank を用いる。これは、1要素の木の rank を 0 とし、同じ rank r の木を連結したとき、全体の根とした方の木の rank を r+1 とするものである。このようにするだけで、MakeSet、Union、Find 操作の償却実行時間は O ( log n ) {\displaystyle O(\log n)} となる。改良した MakeSet と Union の擬似コードは以下のようになる。 function MakeSet(x) x.parent := x x.rank := 0 function Union(x, y) xRoot := Find(x) yRoot := Find(y) if xRoot.rank > yRoot.rank yRoot.parent := xRoot else if xRoot.rank < yRoot.rank xRoot.parent := yRoot else if xRoot != yRoot // x と y が同じ集合にない場合だけマージする。 yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1 第二の改善は path compression と呼ばれ、Find操作を行ったときに構造を平坦化するものである。Findで根ノードまでのリンクをたどっているとき、各ノードは同じ代表を共有しているので、それらを根ノードに直接接続できる。このため、Find は再帰的にたどったノードが全て親ノードとして根ノードを指すように変更する。こうすると木構造はより平坦になり、その後の操作が高速化される。以下に Find の改良版を示す。 function Find(x) if x.parent == x return x else x.parent := Find(x.parent) return x.parent これらの手法は相補的であり、これを共に行うことで各操作の償却実行時間は O ( α ( n ) ) {\displaystyle O(\alpha (n))} となる。ここで α ( n ) {\displaystyle \alpha (n)} は関数 f ( n ) = A ( n , n ) {\displaystyle f(n)=A(n,n)} の逆であり、 A {\displaystyle A} は非常に高速に大きな値になるアッカーマン関数である。 α ( n ) {\displaystyle \alpha (n)} はその逆関数なので、実用的な n {\displaystyle n} の値に対しては常に 5 未満の値になる。したがって、各操作の償却実行時間は事実上非常に小さな定数となる。 実際、これは漸近最良である。Fredman と Saks は1989年、どのような素集合データ構造でも1回の操作あたり平均で Ω ( α ( n ) ) {\displaystyle \Omega (\alpha (n))} のノードにアクセスするとした。
※この「素集合森」の解説は、「素集合データ構造」の解説の一部です。
「素集合森」を含む「素集合データ構造」の記事については、「素集合データ構造」の概要を参照ください。
- 素集合森のページへのリンク
