31. Множества с операторами merge и find

Рассмотрим ситуацию, когда есть совокупность объектов, каждый из которых является множеством.

Основные действия, выполняемые над такой совокупностью, заключаются в объединении множеств в определенном порядке, а также в проверке принадлежности определенного объекта конкретному множеству. Эти задачи решаются с помощью операторов MERGE (Слить) и FIND (Найти).

• Оператор MERGE(A, В, С) делает множество С равным объединению множеств А и В, если эти множества не пересекаются (т.е. не имеют общих элементов); этот оператор не определен, если множества А и В пересекаются.

• Функция FIND(x) возвращает множество, которому принадлежит элемент х; в случае, когда х принадлежит нескольким множествам или не принадлежит ни одному, значение этой функции не определено.

Пример.

Отношением эквивалентности является отношение со свойствами рефлексивности, симметричности и транзитивности. Другими словами, если на множестве S определено отношение эквивалентности, обозначаемое символом "º", то для любых элементов а, b и с из множества S (не обязательно различных) справедливы следующие соотношения.

1. а º а (свойство рефлексивности).

2. Если а º b, то b º а (свойство симметричности).

3. Если а º b и b º с, то а º с (свойство транзитивности).

Отношение равенства (обозначается знаком "=") - это пример отношения эквивалентности на любом множестве S. Для любых элементов а, b и с из множества S имеем 1) а = а; 2) если а = b, то b = а; 3) если а = b и b = с, то а = с.

В общем случае отношение эквивалентности позволяет разбить совокупность объектов на непересекающиеся группы, когда элементы а и b будут принадлежать одной группе тогда и только тогда, когда а = b.

Если применить отношение равенства (частный случай отношения эквивалентности), то получим группы, состоящие из одного элемента.

Более формально можно сказать так:

• если на множестве S определено отношение эквивалентности, то в соответствии с этим отношением множество S можно разбить на непересекающиеся подмножества S₁, S₂, ..., которые называются классами эквивалентности, и объединение этих классов совпадает с S.

• Таким образом, а º b для всех а и b из подмножества S_i, но а не эквивалентно b, если они принадлежат разным подмножествам.

Например, отношение сравнения по модулю n - это отношение эквивалентности на множестве целых чисел:

• а-а=0 (рефлексивность),

• если а-b=dn, то b-а=(-d)n (симметричность),

• если а-b=dn и b-c=en, то а-с=(d+е)n (транзитивность).

Существует n классов эквивалентности, каждое из которых является множеством целых чисел:

• первое множество состоит из целых чисел, которые при делении на n дают остаток 0,

• второе множество состоит из целых чисел, которые при делении на n дают остаток 1

• и т.д.,

• n-е множество состоит из целых чисел, которые дают остаток n-1.

Методы реализации.

Предположим, что мы объявили тип MFSET как массив components (компоненты), предполагая, что components[x] содержит имя множества, которому принадлежит элемент х. При этих предположениях операторы АТД MFSET реализуются легко, что видно из листинга 6.13 с кодом процедуры MERGE. Процедура INITIAL(A, x) просто присваивает components[x] значение А, а функция FIND(x) возвращает значение components[x].

Время выполнения операторов при такой реализации MFSET легко проанализировать:

• время выполнения процедуры MERGE имеет порядок О(n),

• а для INITIAL и FIND время выполнения фиксированно, т.е. не зависит от n.

Применение алгоритма из листинга 6.13 для последовательного выполнения n-1 раз оператора MERGE займет время порядка O(n²). Один из способов ускорения выполнения оператора MERGE заключается в связывании всех элементов компонента в отдельные списки компонентов. Тогда при слиянии компонента В в компонент А вместо просмотра всех элементов необходимо будет просмотреть только список элементов компонента В.

Такое расположение элементов сократит среднее время слияния компонентов.

Другой подход к реализации АТД MFSET применяет деревья с указателями на родителей. Опишем этот подход неформально. Основная идея здесь заключается в том, что узлы деревьев соответствуют элементам множеств и есть реализация, посредством массивов или какая-либо другая, отображения множества элементов в эти узлы.

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

О перация слияния делает корень одного дерева сыном корня другого. Например, при слиянии множеств А и В, когда результат слияния получает имя А, узел 5 становится сыном узла 1.

О днако неупорядоченные слияния могут привести к результату в виде дерева из n узлов, которое будет простой цепью узлов. В этом случае выполнение оператора FIND для любого узла такого дерева потребует времени порядка О(n²). В этой связи заметим, что хотя слияние может быть выполнено за О(1) шагов, но в общей стоимости всех выполняемых операций может доминировать операция поиска. Поэтому, если надо просто выполнить m слияний и n поисков элементов, данный подход может быть не самым лучшим выбором.