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

Здесь разбивка алгоритма union/find для непересекающихся лесных массивов на wikipedia:

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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