Несвязанный набор DS

Question

Я изучал непересекающиеся наборы структур данных.

У меня есть запрос, что при использовании объединения по рангу и сжатию путей вместе, если мы пропустим использование объединения по рангу и назначим приоритет (родительский) без сравнения рангов (рангов корней / репрезентативного элемента) двух множеств (деревьев) влияет на время работы.

Хотя при объединении двух наборов требуется эвристика с взвешенным объединением, чтобы добавить меньший набор к большему, чтобы сделать как можно меньше обновлений, чтобы указать на репрезентативный элемент.

Объединение по рангу (аналогично взвешенному объединению) используется при объединении двух наборов. Но если мы пропустим сравнение рангов и случайным образом назначим приоритет, это не повлияет на время выполнения. Тогда зачем нам его использовать.. Я не могу ясно видеть это, пожалуйста, помогите мне понять, если я ошибаюсь.

// нет сравнения рангов

СОЕДИНЕНИЕ (х, у)

x.parent = у;

обобщенный код

union(x,y){

if(x.rank>y.rank)
    y.parent=x;
else
    x.parent=y;

if(x.rank==y.rank)
    y.rank=y.rank+1;
 }

Answer 1

Если мы рассмотрим n непересекающихся элементов сиглета и применим к ним функцию объединения таким образом, чтобы корень одного множества (т. Е. Дерева, образованного в представлении множества) всегда объединялся с единичным элементом, то во всех этих объединениях Сжатие путей в случаях не имеет никакого эффекта, и мы можем в конечном итоге создать связанный список.

В таких наихудших случаях сложность одной находки может быть θ(n), в то время как объединение, исключающее поиск для двух множеств, все еще равно θ(1), как и при включении объединения по рангу. Таким образом, в худшем случае сложности отдельных запросов на множестве улучшаются с помощью объединения по рангу, которое сохраняет его θ(lgn).

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