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

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

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

В результате для элементов w B, отличных от u, имя множества, которому они принадлежат, приходится вычислять переходом по цепочке указателей, ко- торая сначала ведет к «старому имени» u, а потом по указателю от и — к «новому имени» v. Пример такого представления изображен на рис. 4.12. Например, два множества на рис. 4.12 могут представлять результат следующей серии операций Union: Uniоn(w, и), Uniоn(s·, и), Uniоn(l, v), Uniоn(z, v), Uniоn(/, x), Uniоn(уj), Union(xj') и Union(и, v).

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

Оно может достигать 0(n), если мы не проявим достаточной осто- рожности с выбором имен множеств. Для сокращения времени, необходимого для операции Find, мы воспользуемся уже знакомой оптимизацией: имя наибольшего множества сохраняется как имя объединения. Последовательность объединений, приведших к структуре на рис. 4.12, подчинялась этому правилу. Чтобы эффектив- но реализовать этот вариант, необходимо хранить с узлами дополнительное поле: размер соответствующего множества.
Множество {i, и, w} сливается с {t, v, z}

Рис. 4.12. Структура Union-Find с указателями. В данный момент структура содержит только два множества, названных по именам элементов v и j. Пунктирные стрелки от и к v представляют результат последней операции Union. Для обработки запроса Find мы перемещаемся по стрелкам, пока не доберемся до узла без исходящих стрелок. Например, для ответа на запрос Find(i) потребуется перейти по стрелке i к х, а затем от x к j


(4.24) Имеется описанная выше реализация структуры данных Union-Find с указателями для некоторого множества S размера n; за объединением сохра- няется имя большего множества. Операция Union выполняется за время 0(1), MakeUnionFind(S) — за время 0(n), а операция Find — за время О(log n).

Доказательство. Истинность утверждений относительно операций Union и MakeUnionFind очевидна. Время выполнения Find(v) для узла v определяется ко- личеством изменений имени множества, содержащего узел v, в процессе. По пра- вилам за объединением сохраняется имя большего из объединяемых множеств, из чего следует, что при каждом изменении имени множества, содержащего узел v, размер этого множества по крайней мере удваивается. Поскольку множество, содержащее v, начинается с размера 1 и никогда не оказывается больше n, его размер может удваиваться не более log2 n раз, а значит, имя может изменяться не более log2 n раз. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Усовершенствованная структура данных Union-Find:

  1. Григорьев Ю.А., Ревунков Г.И.. Банки данных, 2002
  2. Оценка данных о личности.
  3. 18.4. Права субъекта персональных данных
  4. Банк данных
  5. 5.3. Графическое представление данных
  6. Анализ и интерпретация полученных данных
  7. Анализ и интерпретация полученных данных
  8. Подготовка исходных данных
  9. 4.5. Право изготовителя базы данных
  10. 12.4. Анализ эмпирических данных
  11. 3.3.4. Методы обработки и анализа данных
  12. 5.1. Табличное представление данных
  13. 18.7. Уполномоченный по правам субъектов персональных данных
  14. 3.3.2. Обоснование методов сбора эмпирических данных
  15. Глава 9 Создание экспертной базы данных
  16. 2. Регистрация программ, баз данных и охраняемых топологий
  17. 4.1. Общие принципы анализа данных
  18. Практическое использование виктимологических данных.
  19. Количество и тип требуемых данных
  20. ГЛАВА 18 ПРАВОВОЕ РЕГУЛИРОВАНИЕ ИНФОРМАЦИОННЫХ ОТНОШЕНИЙ В ОБЛАСТИ ПЕРСОНАЛЬНЫХ ДАННЫХ