Как правильно реализовать операцию объединения в структуре данных с несвязными множествами?
Существует множество различных описаний и примеров структуры несвязных множеств, доступных в режиме онлайн.
В некоторых случаях для каждого набора хранится "ранг". Когда набор объединяется в другой набор, ранг первого увеличивается на 1, если они имеют одинаковый ранг.
В других случаях для каждого набора хранится его размер. Когда набор объединяется с другим, их размеры добавляются.
Здесь он хранит ряды.
В статье в Википедии хранятся ранги.
В записках лекций Корнелльского университета хранятся звания.
В примере из "Алгоритмов" Седжвика и Уэйна он хранит размеры.
Здесь также хранятся размеры ( основной сайт).
Cormen et al. записывать:
Очевидный подход заключается в том, чтобы корень дерева с меньшим количеством узлов указывал на корень дерева с большим количеством узлов. Вместо того, чтобы явно отслеживать размер поддерева, укорененного в каждом узле, мы будем использовать подход, который облегчает анализ. Для каждого узла мы поддерживаем ранг, который является верхней границей высоты узла. При объединении по рангу корень с меньшим рангом указывает на корень с большим рангом во время операции UNION.
Что лучше / правильнее?
1 ответ
Весь анализ (есть?) Показывает, что оба метода обеспечивают оптимальную O(альфа) сложность в сочетании с техникой коллапса дерева.
Тогда единственное отличие, зависящее от реализации, заключается в размере, который принимают переменные размера или ранга. Размер может быть до size_t но ранг может быть закодирован всегда в трех битах.
Иногда эти три бита могут быть закодированы в неиспользуемые биты в данных / узлах для обработки, что приводит к лучшей производительности (скорости и размеру).