Disjoint Sets (Cousera Data Structure week3)
CouseraのData Strucureコースのweek3の内容です。
www.coursera.org
前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com
Disjoint-set
Disjoint-setは以下の操作を持つデータ構造である
- MakeSet(x)：集合{x}を作る
- Find(x)：xを含む集合のIDを返す
- もしxとｙが同じ集合に属していればFind(x)==Find(y)
- Union(x, y)：ｘとｙを含む２つの集合を結合する
単純な実装
- 集合の最も小さい値の要素をその集合のIDとして使う
- smallest[1...n]のような配列を使う
- smallest[i]にiが所属する最小の要素の値を入れる
効率的な実装
- 単純な実装のボトルネックはUnion操作である。
- Linked listを使うことでより効率的な実装が可能。
- 集合をLinked listで表し、listの末尾を集合のIDとして使う
↓
- メリット
- Unionの実行時間がO(1)
- デメリット
- 末尾を探すためにリストを走査する必要があるため、Findの実行時間がO(1)
- ｘのリストの末尾とｙのリストの先頭を定数時間で取得できる場合のみUnionの実行時間はO(1)
木構造を用いたさらに効率的な実装
- 集合を一つの木で表す
- IDはその木構造のルート
- parent[1...n]という配列を使う
- parent[i]はiの親もしくはiがルートであるならばi自身
- どのように２つの木をマージさせるか？
- 片方の木をもう片方のルートノードの下にぶら下げる
- 木を浅くしておくため、短い木をぶら下げる
- 木の高さを素早く見つけるために各サブツリーの高さを配列rank[1...n]に保持しておく
- rank[i]はルートがiであるサブツリーの高さを表す
- 高い木の下に短い木をぶら下げることをunion by rank heuristicと呼ぶ
まとめ
union by rank heuristicを使うことでUnionとFindの実行時間がO(log n)になる
Path Compression
木の高さを短くする方法。例えば以下の図の例でFind(6)を実行する場合、ノード6からルートノードまで親を辿っていく必要があるが、その際12と3もルートノードも同時にわかるので以下の様に木を変形できる。
O(log n)の操作をn回繰り返すときの計算量をlog*nと定義する。
つまり一回の操作の時間計算量は漸近的にO(log*n)となり、実質的にlog*n < 5のときは定数時間とみなせる。
まとめ
- 各集合を木構造で表現する
- ルートノードをその集合のIDとする
- Union by rank heuristic
- 高い木のルートの下に短い木を吊り下げる
- Path Compresion heuristic
- ある特定のノードのルートを見つけるときに、走査したノードをルートの下に吊り下げる
- 償却的時間計算量はO(log*n)
- 現実的なｎの値でほぼ定数時間
