Лес непересекающихся множеств — древовидная структура данных для непересекающихся множеств.
Каждое множество представляется в виде корневого дерева. В лесу непересекающихся множеств каждый узел содержит один элемент множества и указывает только на свой родительский узел. Корень каждого дерева содержит представителя и является родительским для самого себя.
Операции над лесом непересекающихся множеств выполняются следующим образом:
MAKE_SET — создает дерево с одним узлом.
FIND_SET — передвигаемся по родительским ссылкам до корня дерева.
UNION — устанавливает указатель корня одного дерева на корень другого.
Объединение по рангу. Идея эвристики состоит в том, чтобы при выполнении операции UNION высота итогового дерева по возможности не увеличивалась. Для этого используется характеристика ранг для каждого корня, которая представляет собой верхнюю границу высоты узла. Операция MAKE_SET создаёт корень с рангом 0. Операция UNION, которая в этом случае называется объединение по рангу, действует следующим образом:
Сжатие путей. Эвристика в процессе выполнения операции FIND_SET делает каждый узел (которые встретились при передвижении до корня) указывающим непосредственно на корень. Сжатие путей не изменяет ранги узлов.
Рассмотрим пример реализации леса непересекающихся множеств. В массиве p будем хранить ссылку на родительских узел, а в массиве r ранг вершины.
operation MAKE_SET(x) p[x] = x r[x] = 0
operation FIND_SET(x) if x ≠ p[x] then p[x] = FIND_SET(p[x]) return p[x]
operation UNION(x, y) if r[x] > r[y] then p[y] = x else p[x] = y if r[x] = r[y] then r[y] = r[y] + 1
Будучи примененным раздельно, объединение по рангу и сжатие путей приводят к повышению эффективности операций над лесом непересекающихся множеств. Объединение по рангу само по себе дает время работы , где — общее количество операций, а — количество элементов в системе. Сжатие путей само по себе приводит ко времени работы в наихудшем случае , где — количество операций FIND_SET. Применение обеих эвристик дает время работы в наихудшем случае , где — обратная функция Аккермана. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .