Структура данных для непересекающихся множеств
Структура данных для непересекающихся множеств поддерживает набор Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S = \{S_1, S_2, \ldots, S_k\}} непересекающихся динамических множеств. Каждое множество идентифицируется представителем, которые представляет собой некоторый элемент множества. В ряде приложений не имеет значения какой элемент множества используется в качестве представителя; главное, чтобы при запросе представителя множества дважды, без внесения изменений в множество между запросами, возвращался один и тот же элемент.
Структура данных для непересекающихся множеств требует поддержку следующих операций:
MAKE_SET(x) создает новое множество, состоящее из одного элемента (который соответственно становится его представителем) x. Поскольку множества непересекающиеся, требуется, чтобы х не входил ни в какой иное множество.
UNION(x, y) объединяет динамические множества, которые содержат x и y (обозначим Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_x} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_y} ), в новое множество. Полагается что до выполнения операции указанные множества не пересекались. Представителем образованного в результате множества является произвольный элемент Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_x \cup S_y} . Поскольку необходимо, чтобы множества были непересекающимися, операция UNION должна уничтожать множества Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_x} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle S_y} .
FIND_SET(x) возвращает указатель на представителя множества, в котором содержится элемент x.
Примеры конкретных структур данных для непересекающихся множеств[править]
Литература[править]
- Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS . — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.