Почему в объединении несвязанных множеств (DSU) мы делаем подмножество меньшего размера дочерним для подмножества большего размера при выполнении операции объединения?

Question

Недавно я наткнулся на DSU и его приложения на дереве. По мере того, как я решал связанные с этим проблемы, в некоторых я получал ошибку Time Limit Exceeded, поэтому я снова прочитал учебник, и там я обнаружил, что импровизированная версия нормального объединения взвешенный-соединение. В этой операции взвешенного объединения мы делаем подмножество меньшего размера root дочерним по отношению к подмножеству большего размера (среди двух) root. Как это нам выгодно? Ссылка на Учебник

Answer 1

Не имеет значения в правильности точки зрения, но обычно это быстрее.

Проверьте этот пример:

В первом случае вы ставите самый большой набор как потомок самого маленького. Вы можете видеть, что в этом случае, если вы попробуете метод find в самом глубоком узле, он выполнит 3 шага. Во втором случае этого не происходит.

Это не правило, а практически то, что происходит.

Answer 2

Вы должны осознать цель / логи c, стоящую за взвешенным союзом-находкой.

Во-первых, зачем нам взвешенный союз-поиск? Это потому, что простой неэффективный поиск объединения может привести к несбалансированному дереву. В худшем приведен связанный список. В чем сложность обхода связанного списка? O(N). Это наихудшая сложность при использовании простого объединения-поиска.

Наша цель - сбалансировать сформированное дерево.

Как и почему работает взвешенный поиск союза? Это простая оптимизация, просто сохраняющая размер каждого подмножества и делающая меньший подмножество дочерним по отношению к большому подмножеству при выполнении объединения двух.

Почему это работает? Потому что, как уже упоминалось, наша цель - сбалансировать дерево при объединении, а не разбалансировать его. Если вы сделаете меньшее подмножество дочерним по отношению к большому подмножеству, высота всего дерева не увеличится (очевидно, что при равных размерах мы обрабатываем это по-разному: /). С другой стороны, если вы сделаете большее подмножество дочерним по отношению к меньшему дереву, вы знаете, что произойдет.

Используя только эту оптимизацию, мы улучшаем сложность времени наихудшего случая с O(N) до O(log2(N)) - потому что высота дерева никогда не будет go выше log2(N)

Есть еще одна оптимизация это может быть сделано вместе с этим, что еще больше снизит сложность. Ваша ссылка, вероятно, имеет это.