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

Значимость предмета статьи поставлена под сомнение. Пожалуйста, покажите в статье значимость её предмета, добавив в неё доказательства значимости по частным критериям значимости или, в случае если частные критерии значимости для предмета статьи отсутствуют, по общему критерию значимости. Подробности могут быть на странице обсуждения. Кратко: Значимость статьи не показана Дата постановки шаблона: 16 октября 2012

Структура данных для непересекающихся множеств поддерживает набор $S = \{S_1, S_2, \ldots, S_k\}$ непересекающихся динамических множеств. Каждое множество идентифицируется представителем, которые представляет собой некоторый элемент множества. В ряде приложений не имеет значения какой элемент множества используется в качестве представителя; главное, чтобы при запросе представителя множества дважды, без внесения изменений в множество между запросами, возвращался один и тот же элемент.

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

MAKE_SET(x) создает новое множество, состоящее из одного элемента (который соответственно становиться его представителем) x. Поскольку множества непересекающиеся, требуется, чтобы х не входил ни в какой иное множество.

UNION(x, y) объединяет динамические множества, которые содержат x и y (обозначим $S_x$ и $S_y$), в новое множество. Полагается что до выполнения операции указанные множества не пересекались. Представителем образованного в результате множества является произвольный элемент $S_x \cup S_y$. Поскольку необходимо, чтобы множества были непересекающимися, операция UNION должна уничтожать множества $S_x$ и $S_y$.

FIND_SET(x) возвращает указатель на представителя множества, в котором содержится элемент x.

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

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

Ссылки

• Визуализатор работы некоторых структур данных для непересекающихся множеств
• Реализация непересекающихся множеств в коллекции библиотек C++ Boost

Литература

• Томас Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1