ユニオン/検索構造のクイック ユニオン アルゴリズムを実装しています。「Algorithms in Java」書籍サイト で提供されている実装では、Princeton 実装は (find()メソッド内で) パス圧縮を実装している間、ツリーのサイズ不変を維持できません。これはアルゴリズムに悪影響を与えるべきではありませんか? または私は何かを逃していますか？また、私が正しければ、サイズ配列を変更するにはどうすればよいでしょうか?
質問する
1546 次
1 に答える
3
私が間違っていない限り、このコードは、各ツリーのルートがそのサブツリー内のノードの数を格納するという不変条件を実際に維持していると思います。
sz[i] = 1データ構造が作成されると、フォレスト内の各ノードにコンストラクターが設定されることに注意してください。これは、値が正しく開始されることを意味します。
ユニオン操作中に、データ構造はマージされたツリーのルートのサイズを正しく調整します。したがって、ユニオン操作の後、すべてのツリールートは正しいサイズになります。
検索ステップでのパス圧縮中にサイズが更新されないことは正しいですが、ここでデータ構造がサイズを変更する理由はありません。パス圧縮は、一部のツリーのノードからツリーのルートまでのパスの長さを短くするだけです。そのツリーに格納されているノードの数は変更されません。したがって、パス圧縮を受けているツリーのルートのサイズ情報を変更する必要はありません。一部の内部サブツリーは、ツリーの上位で親が変更されるため、一部の子を失う可能性がありますが、union / find構造は、内部ノードではなく、ツリーのルートでサイズ情報を維持するだけでよいため、これは関係ありません。
全体として、これはデータ構造がサイズ情報を正しく格納することを意味します。実行時間に悪影響はなく、何も修正する必要はありません。
お役に立てれば！
于 2012-12-27T19:08:38.033 に答える