Лес непересекающихся множеств - История изменений

Patarakin в 09:59, 19 октября 2022

2022-10-19T09:59:39Z

← Предыдущая версия		Версия от 12:59, 19 октября 2022
Строка 42:		Строка 42:

	Будучи примененным раздельно, объединение по рангу и сжатие путей приводят к повышению эффективности операций над лесом непересекающихся множеств. Объединение по рангу само по себе дает время работы <math>O(m~\lg{n})</math>, где <math>m</math> — общее количество операций, а <math>n</math> — количество элементов в системе. Сжатие путей само по себе приводит ко времени работы в наихудшем случае <math>O(n + f~\log_{2 + f/n}{n})</math>, где <math>f</math> — количество операций FIND_SET. Применение обеих эвристик дает время работы в наихудшем случае <math>O(m\ \alpha(n, m))</math>, где <math>\alpha(n, m)</math> — [[Функция Аккермана\|обратная функция Аккермана]]. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.		Будучи примененным раздельно, объединение по рангу и сжатие путей приводят к повышению эффективности операций над лесом непересекающихся множеств. Объединение по рангу само по себе дает время работы <math>O(m~\lg{n})</math>, где <math>m</math> — общее количество операций, а <math>n</math> — количество элементов в системе. Сжатие путей само по себе приводит ко времени работы в наихудшем случае <math>O(n + f~\log_{2 + f/n}{n})</math>, где <math>f</math> — количество операций FIND_SET. Применение обеих эвристик дает время работы в наихудшем случае <math>O(m\ \alpha(n, m))</math>, где <math>\alpha(n, m)</math> — [[Функция Аккермана\|обратная функция Аккермана]]. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.

	~~== Ссылки ==~~
	* [https://web.archive.org/web/20140924062309/http://rain.ifmo.ru/cat/view.php/vis/unsorted/disjoint-sets-2003 Визуализатор работы структуры данных]

	~~== Литература ==~~
	* {{книга
	~~\|автор = Томас Кормен и др.~~
	~~\|заглавие = Алгоритмы: построение и анализ~~
	~~\|оригинал = INTRODUCTION TO ALGORITHMS~~
	~~\|ссылка =~~
	~~\|издание = 2-е изд~~
	~~\|место = М.~~
	~~\|издательство = [[Вильямс (издательство)\|«Вильямс»]]~~
	~~\|год = 2006~~
	~~\|страницы = 1296~~
	~~\|isbn = 0-07-013151-1~~
	}}

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:42Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Proggga: добавил ссылку на Систему пересекающихся множеств

2021-03-05T15:36:20Z

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

Новая страница

'''Лес непересекающихся множеств''' — [[Дерево (теория графов)|древовидная]] [[система непересекающихся множеств|структура данных для непересекающихся множеств]]. (иногда называют [[Система непересекающихся множеств|Системой непересекающихся множеств]])

== Представление множеств ==
Каждое множество представляется в виде [[Дерево (теория графов)|корневого дерева]]. В лесу непересекающихся множеств каждый узел содержит один элемент множества и указывает только на свой родительский узел. Корень каждого дерева содержит представителя и является родительским для самого себя.

Операции над лесом непересекающихся множеств выполняются следующим образом:

MAKE_SET — создает дерево с одним узлом.

FIND_SET — передвигаемся по родительским ссылкам до корня дерева.

UNION — устанавливает указатель корня одного дерева на корень другого.

== Эвристики для повышения эффективности ==
'''Объединение по рангу.''' Идея эвристики состоит в том, чтобы при выполнении операции UNION высота итогового дерева по возможности не увеличивалась. Для этого используется характеристика '''ранг ''' для каждого корня, которая представляет собой верхнюю границу высоты узла. Операция MAKE_SET создаёт корень с рангом 0. Операция UNION, которая в этом случае называется объединение по рангу, действует следующим образом:
* Если ранги корней различны, корень с меньшим рангом указывает на корень с большим рангом. Ранги корней не меняются.
* Если ранги корней равны, любой из корней указывает на другой. Ранг того корня, на который указывает другой корень, увеличивается на 1.

'''Сжатие путей.''' Эвристика в процессе выполнения операции 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

== Время работы ==

Будучи примененным раздельно, объединение по рангу и сжатие путей приводят к повышению эффективности операций над лесом непересекающихся множеств. Объединение по рангу само по себе дает время работы <math>O(m~\lg{n})</math>, где <math>m</math> — общее количество операций, а <math>n</math> — количество элементов в системе. Сжатие путей само по себе приводит ко времени работы в наихудшем случае <math>O(n + f~\log_{2 + f/n}{n})</math>, где <math>f</math> — количество операций FIND_SET. Применение обеих эвристик дает время работы в наихудшем случае <math>O(m\ \alpha(n, m))</math>, где <math>\alpha(n, m)</math> — [[Функция Аккермана|обратная функция Аккермана]]. Эта оценка является нижней границей времени работы с непересекающимися множествами, поэтому лес непересекающихся множеств является оптимальной структурой для непересекающихся множеств.

== Ссылки ==
* [https://web.archive.org/web/20140924062309/http://rain.ifmo.ru/cat/view.php/vis/unsorted/disjoint-sets-2003 Визуализатор работы структуры данных]

== Литература ==
* {{книга
|автор = Томас Кормен и др.
|заглавие = Алгоритмы: построение и анализ
|оригинал = INTRODUCTION TO ALGORITHMS
|ссылка =
|издание = 2-е изд
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы = 1296
|isbn = 0-07-013151-1
}}

[[Категория:Структуры данных]]