差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming:algorithm:data_structure:union_find_tree [2017/08/07] – ikatakos | programming_algorithm:data_structure:union_find_tree [2017/10/08] – ↷ programming:algorithm:data_structure:union_find_tree から programming_algorithm:data_structure:union_find_tree へページを移動しました。 ikatakos | ||
---|---|---|---|
行 54: | 行 54: | ||
===経路圧縮=== | ===経路圧縮=== | ||
* 一度調べた経路上にある要素は、全て親を代表に書き換える | * 一度調べた経路上にある要素は、全て親を代表に書き換える | ||
- | * おそい例において、4→3→2→1と調べて1がリーダーだとわかったら、2~4の親を1に書き換える | + | * おそい例において、4→3→2→1と調べて1が代表だとわかったら、2~4の親を1に書き換える |
===ランク=== | ===ランク=== | ||
行 78: | 行 78: | ||
* 例: 要素数100, | * 例: 要素数100, | ||
- | * 深さで考えるとBにAをつなぐことになる | + | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 |
- | * AにBをつなぐと最大深さが5になるとはいえ、影響ある要素は5個 | + | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 |
- | * それより、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方 | + | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方か |
- | * どちらがいいかは場合に依りけり? | + | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, |
=====実装===== | =====実装===== | ||
- | * 要素数$n$の配列{\rm table}を作り、-1で初期化する | + | * 要素数$n$の配列'' |
* ${\rm table}[x]$が負ならば、$x$は代表。絶対値はランクを示す | * ${\rm table}[x]$が負ならば、$x$は代表。絶対値はランクを示す | ||
* ${\rm table}[x]$が非負ならば、$x$は代表でない。値は$x$の親を示す | * ${\rm table}[x]$が非負ならば、$x$は代表でない。値は$x$の親を示す |