Структуры данных и модели вычислений
того подмножества коллекции, которому принадлежит
Имена объединяемых подмножеств указываются в качестве параметров.
НАЙТИ(). Эта операция позволяет определить имя
того подмножества коллекции, которому принадлежит элемент . Если элемент до выполнения операции не входил ни в одно из подмножеств коллекции, то в качестве берется 0.
Последовательность , составленную из операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, назовем корректной, если перед выполнением каждой операции из последовательности соблюдены условия ее применения. Например, перед выполнением очередной операции вида ОБЪЕДИНИТЬ (, ) подмножества с именами и должны быть уже созданы. Перед выполнением операции СОЗДАТЬ() элемент не должен принадлежать ни одному из подмножеств коллекции. Операция НАЙТИ (, ) применима при любом значении аргумента . Следует только помнить, что если не принадлежит ни одному из подмножеств коллекции, то получим .
Мы рассмотрим несколько способов представления коллекции разделенных множеств в памяти компьютера и алгоритмической реализации перечисленных операций. А именно, будут описаны представления
- с помощью массива;
- с помощью древовидной структуры;
- с помощью древовидной структуры с использованием рангов вершин;
- с помощью древовидной структуры с использованием рангов вершин и сжатия путей.
Последний из перечисленных способов является наиболее эффективным по времени выполнения произвольных корректных последовательностей операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ. Строго говоря, во всех перечисленных случаях будут использоваться массивы, но интерпретации их содержимого будут различными. Каждый раз при описании очередной реализации мы будем обсуждать оценки трудоемкости рассматриваемых операций.
