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

Question

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

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

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

---

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

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

---

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

Answer 1

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

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

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

Answer 2

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

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