Усовершенствованная структура данных Union-Find

В структуре данных альтернативной реализации используются указатели. Каждый узел v Ѯ S будет храниться в записи с указателем на имя множества, содержащего v.

Как и прежде, мы будем использовать элементы множества S в качестве имен множеств, а каждое множество будет названо по имени одного из своих элементов.

Для операции MakeUnionFind(S) запись каждого элемента v Ѯ S инициализируется указателем, который указывает на себя (или определяется как null); это означает, что v находится в собственном множестве.

Рассмотрим операцию Union для двух множеств A и B. Предположим, что имя, использованное для множества A, определяется узлом v Ѯ A, тогда как множество B названо по имени узла u Ѯ B.

Идея заключается в том, чтобы объединенному множеству было присвоено имя u или v; допустим, в качестве имени выбирается v. Чтобы указать, что мы выполнили объединение двух множеств, а объединенному множеству присвоено имя v, мы просто обновляем указатель u так, чтобы он ссылался на v. Указатели на другие узлы множества B при этом не обновляются.

В результате для элементов w Ѯ B, отличных от u, имя множества, которому они принадлежат, приходится вычислять переходом по цепочке указателей, которая сначала ведет к «старому имени» u, а потом по указателю от u — к «новому имени» v.

Пример такого представления изображен на рис. 4.12. Например, два множества на рис. 4.12 могут представлять результат следующей серии операций Union: Union(w, u),  Union(s, u),  Union(t, v),  Union(z, v),  Union(i, x),  Union(y, j),  Union(x, j) и Union(u, v).

Структура данных с указателями реализует операцию Union за время O(1): требуется лишь обновить один указатель. Но операция Find уже не выполняется за постоянное время, потому что для перехода к текущему имени приходится отслеживать цепочку указателей с «историей» старых имен множества.

Сколько времени может занимать операция Find(u)? Количество необходимых шагов в точности равно количеству изменений имени множества, содержащего узел u, то есть количеству обновлений позиции в массиве Component[u] в нашем представлении в виде массива.

Оно может достигать O(n), если мы не проявим достаточной осторожности с выбором имен множеств.

Для сокращения времени, необходимого для операции Find, мы воспользуемся уже знакомой оптимизацией: имя наибольшего множества сохраняется как имя объединения.  Чтобы эффективно реализовать этот вариант, необходимо хранить с узлами дополнительное поле: размер соответствующего множества.