В поисках правильного объединения DST с обратно-аккерманной сложностью

Question

Я говорю о структуре данных union-find-disjoint. В Интернете есть множество ресурсов о том, как это реализовать. До сих пор я узнал о двух методах оптимизации для профсоюзов. Первый - это "балансировка" дерева с помощью переменной Rank, которая говорит о глубине самого глубокого узла и, следовательно, является верхней границей find(). Вторая оптимизация заключается в следующем: установка родительского объекта в качестве главного узла при вызове find() (настройка также включает в себя родительские объекты, поэтому он становится каскадом оптимизаций).

Однако, когда реализации используют два из них одновременно, они обычно объединяют два без особого размышления. В частности, GeeksforGeeks (просто в качестве примера, ничего личного) делает это. Не приведет ли это к тому, что ряды получат "испорченные" и сложность O(log n)?

Например, если у меня есть длинная линия узлов (от 5 до 4 до 3 до 2 до 1 до 0, которая является главой), и я называю find () для 2, ранг остается 5, даже если он должен быть 3.

Answer 1

В таких реализациях ранги все еще являются верхними границами высоты деревьев. Они действительно могут стать неточными верхними границами.

Кажется, что лог * доказательство не основывается на точности этой верхней границы.

В статье Тарьяна 1975 года "Эффективность хорошего, но не линейного алгоритма объединения", приведенной в нижней части вышеприведенной страницы, он, кажется, использует объединение по размеру вместо объединения по рангу. Размер (число вершин), в отличие от точного ранга, легко поддерживать в O(1) операциях на объединение.

Answer 2

Ранг не является строгой мерой глубины. Из Википедии:

Термин ранг используется вместо глубины, поскольку он перестает быть равным глубине, если также используется сжатие пути (...)

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