Алгоритм объединения / поиска без объединения по рангу для структуры данных о лесах с непересекающимся множеством

Question

Вот разбивка алгоритма объединения / поиска для непересекающихся наборов лесов в Википедии:

• Barebone непересекающиеся набор леса... (O(n))
  • ... с объединением по рангу... (теперь улучшено до O(log(n))
    • ... со сжатием пути (теперь улучшено до O(a(n))эффективно O(1))

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

---

Сделан комментарий, который подразумевает, что объединение по рангу без сжатия пути (амортизируется O(log(n) сложность) достаточно для наиболее практического применения. Это правильно. Я спрашиваю об обратном: что если вы пропустите объединение по рангу и ТОЛЬКО вместо этого будете выполнять сжатие пути?

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

---

Было также отмечено, что без объединения по рангу повторяющиеся объединения могут создавать структуру, подобную связанному списку. Это означает, что операция сжатия одного пути может занять O(n) в худшем случае. Это, конечно, повлияет на будущие операции, поэтому то, как это работает, когда амортизируется во многих операциях, меня больше интересует.

Answer 1

Я погуглил "без объединения по рангу", и появилась вторая ссылка:

... Мы закрываем этот раздел анализом объединения-поиска со сжатием пути, но без объединения по рангу...

Структура данных объединения-поиска с сжатием пути, но без объединения по процессам ранга m поиск и n-1 операций связи за время O((m+n) log n)

Answer 2

Сжатие пути выравнивает древовидную структуру. Союз по рангу помогает слиться. Предположим, что вы пропустите последний. Итак, теперь у вас есть лес без информации о ранге, чтобы выбрать способ объединения. Потенциально теперь вы рискуете объединить дерево с большей глубиной в дерево с меньшей глубиной, что приведет к несбалансированной древовидной структуре. В худшем случае вы можете получить связанный список. Амортизированная временная сложность вашего Союза увеличивается, даже если для Find не меняется.

ИМО, было бы лучше пропустить сжатие пути, но не рейтинг.