差分
このページの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: | ||
| ===経路圧縮=== | ===経路圧縮=== | ||
| * 一度調べた経路上にある要素は、全て親を代表に書き換える | * 一度調べた経路上にある要素は、全て親を代表に書き換える | ||
| - | * おそい例において、４→３→２→１と調べて１がリーダーだとわかったら、２～４の親を１に書き換える | + | * おそい例において、４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える |
| ===ランク=== | ===ランク=== | ||
| 行 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, 『データ構造とアルゴリズム』, |
| =====実装===== | =====実装===== | ||
