algorithm - 2 つの有向木をマージしますか?

Question

ツリーの高さは計算効率の主な障害であるため、短いツリーのルートが長いツリーのルートを指すようにすることをお勧めします。

しかし、これは本当に重要ですか？つまり、逆の方法で実行した場合 (長いツリーを短いツリーにマージする)、ツリーの高さは 1 だけ増加します。どのツリーがどのツリーにマージされますか? または、短いツリーが長いツリーにマージされる別の理由がありますか?

注意: 互いに素な集合について話していることに注意してください。

Answer 1

どの種類のツリーについて話しているのかは明確ではありません (二分探索ツリー、非素集合、または任意の n-ary ツリー)。しかし、いずれにせよ、1 の増加は重要ではありませんが、n 回の合併を行うと n の増加になるからだと思います。これは、多数のマージが必要なデータ構造 (たとえば、互いに素なセット) がある場合に重要です。

Answer 2

引用には文脈がありません。たとえば、一部のツリー構造では、単一の要素を 1 つずつ挿入する必要がある場合があります (たとえば、ツリーのバランスを取り直すことが考えられます。通常、高さ O(log n) のツリーが必要です)。おそらくこれは、より大きなツリーに挿入する要素を少なくする方が簡単であることを意味しています。

明らかに、1 の高さの増加が問題であるかどうかは、高さが 1 増加する頻度に依存します :-)

編集: disjoint setsでは、小さい (下の) ツリーが大きいツリーに追加されることが重要です。