Усовершенствованная структура данных Union-Find
В структуре данных альтернативной реализации используются указатели. Каждый узел v Ѯ S будет храниться в записи с указателем на имя множества, содержащего v.
Как и прежде, мы будем использовать элементы множества S в качестве имен множеств, а каждое множество будет названо по имени одного из своих элементов.
Для операции MakeUnionFind(S) запись каждого элемента v Ѯ S инициализируется указателем, который указывает на себя (или определяется как null); это означает, что v находится в собственном множестве.
Рассмотрим операцию Union для двух множеств A и B. Предположим, что имя, использованное для множества A, определяется узлом v Ѯ A, тогда как множество B названо по имени узла u Ѯ 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, мы воспользуемся уже знакомой оптимизацией: имя наибольшего множества сохраняется как имя объединения. Чтобы эффективно реализовать этот вариант, необходимо хранить с узлами дополнительное поле: размер соответствующего множества.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу