Древовидные структуры для задачи «объединить #U2013 найти» (Темы на автомат)

Древовидные структурыдля задачи объединитьнайти••ВН ИМЯ•••Сжатие путей•Покажем что сжатие путей значительно ускоряет работу алгоритмаДля этого введем функции иПокажем что алгоритм быстрогообъединения выполнитпоследовательность σ из операцийОБЪЕДИНИТЬ и НАЙТИ за время небольшее чем сгде с и спостоянные причем с зависит от сОпределим ранг узла относительно последовательности σопераций ОБЪЕДИНИТЬ и НАЙТИ следующим образомУдалить из σ операции НАЙТИВыполнить получившуюся последовательность σ операцийОБЪЕДИНИТЬРанг узла ν это его высота в получившемся лесуРазобьем ранги на группы ранг будем относить к группеН р ранги и к групперанг к групперанги и к групперангик группеЛемма Существует не болееʳ узлов рангаДоказательствоПо предыдущей лемме каждый узел ранга имеет по крайнеймере ʳ потомков в лесу построенном при выполнении σТак как множества потомков любых двух различных узловодинаковой высоты в лесу не пересекаются а общее числонепересекающихся множеств содержащих не менее ʳузлов не превосходитʳ то узлов ранга не может бытьбольшеʳСледствие Ранг любого узла не превосходитЛемма Если в какой то момент выполненияпоследовательности σ узел ω оказалсяподлинным потомком узла ν то его ранг меньшеранга узла νДоказательствоЕсли в какой то момент выполнения последовательности σузел ω стал потомком узла ν то ω будет потомком узла ν и влесу построенном при выполнении σ Поэтому высота узлаω должна быть меньше высоты узла ν так как ранг узла ωменьше ранга узла νИсследуем сложность выполнения δ изОБЪЕДИНИТЬ и НАЙТИоперацийКаждую операцию ОБЪЕДИНИТЬ можно выполнить заединицу времени то все операции ОБЪЕДИНИТЬ изσможно выполнить за время ОСложность операции НАЙТИПусть ν узел на пути из узла представляющего в кореньдерева содержащего1.

Если ν корень или ОТЕЦ ν имеет ранг которыйпринадлежит не той же группе что и ранг узла ν товыполнение НАЙТИ занимает одну единицу времени2. Если ранги узла ν и его отца принадлежат одной группе топеремещение займет одну единицу временивремяНАЙТИПо последней лемме ранг узлов по мере прохождения вверхпо пути монотонно возрастает А так как различных группрангов не большето по правилу никакое выполнениеоперации НАЙТИ не займет болееединиц времени Еслиприменить правило то узел будет перемещен и сделансыном узла с бОльшим рангом чем его предыдущий отецЕсли узел принадлежить группето он можетперемещаться не болеераз прежде чемприобретет отца из более высокой группы Н р если ранг узлапринадлежит группе то он может перемещаться не болееодного раза прежде чем приобретет отца из более высокойгруппы После этого перемещение узла будет иметьсложность согласно правилу операции НАЙТИОценим верхнюю границу времени выполнения Умножимнаибольшее время на число узлов в группе и просуммируем повсем группам рангов Пустьчисло узлов в группеТогдаНаибольшее время выполнения для узла с рангом из группыне превосходитнаибольшее время выполнения дляузлов ранги которых лежат в группе ограничен числом Группрангов не большесуммарное время выполнения непревосходитОбщее время дляоперации НАЙТИ непревосходитвремени выполнения перемещенийПусть для любогодерево в которомГлубина каждого листа равнакаждый узел высоты имеет ʰ сыновей ≥Таким образом корень дереваимет ʰ сыновей каждыйиз которых является корнем дереваЛемма Для каждого ≥ можно построить деревокотороепорождается некоторой последовательностью операцийОБЪЕДИНИТЬ и содержит в качеств подграфа деревопричемпо меньшей мере четверть узловявляется листьямиДоказательство индукцией поверносостоит изодного узла Для построения деревастроим ᵏ экземплярова затем выбираем одино из них и вливаем остальные внего Таким образом корень полученного дерева будет иметь ᵏсыновей каждый их которых является корнем дереваПустьтакое наименьшее значение что если заменитькаждое поддерево вс корнем высоты любым деревомимеющим листьев и высоту не меньше то на каждом листеполученного дерева можно выполнить ЧН длиныЛемма Значениеконечно для всехДоказательство применяется двойная индукция Хотимдоказать утверждение индукции для с но исходя изистинности для с надо провести индукцию посдля всех итак как ЧН длины не перемещаютузловс сПредположим чтоопределено Нужно показать чтоопределено для всех и Делать это будем индукциейпо Для базиса индукции по докажем что≤− ʰ⁺Пустьмножество узлов высоты в деревеВ этомпреобразованном дереве каждый лист является подлиннымпотомком единственного элемента множестваесли бы мымогли выполнить ЧН длины с на всех элементах то смоглиПусть− ʰ⁺По определению индукции для с числосуществует Все узлы высотывимеют по ʰ⁺ сыновейкаждый причем все сыновья принадлежат Если удалить извсех подлинных потомков узлов входящих в то тем самымкаждое дерево с конями на высотезаменится деревом высотыс ʰ⁺ листьями По определения число− ʰ⁺достаточно велико так что операции ЧН длины с можновыполнить на всех листьях т е элементах множестваЧтобы завершить индукция по с осталось сделать шаг индукции поПокажем что дляимеет место неравенствоОбозначимНачнем выполнять операцию ЧН на листьях каждогоподставляемого дерева это можно сделать по предположениюиндукции поВыполнив ЧН на листах находим что й лист каждогоподставляемого дерева теперь имеет отца отличного от го листалюбого другого подставляемого дереваМножество таких отцов обозначим черезПусть поддерево с корнем высоты всодержит ᵏ⁽ᵏ⁺ ⁾ листьев впосле выполнения операцийЧН число узлов в которые также принадлежат непревосходит ᵏ⁽ᵏ⁺ ⁾Множество оставшееся от можнорассматривать как произвольное дерево с ᵏ⁽ᵏ⁺ ⁾ листьямикоторые принадлежат По предположению индукции для инеравенствосправедливоЛемма доказанаТаким образом чтобы показать что сложность алгоритмабольше для любой постоянной с можно предположитьпротивное н выбрави вычисливиспользуядоказанную лемму получим противоречие.