4.7. ДРЕВОВИДНЫЕ СТРУКТУРЫ ДЛЯ ЗАДАЧИ ОБЪЕДИНИТЬ — НАЙТИ

В предыдущем разделе мы познакомились со структурой данных для задачи ОБЪЕДИНИТЬ - НАЙТИ, позволяющей выполнить операций ОБЪЕДИНИТЬ и операций НАЙТИ за время . В данном разделе будет описана структура данных, которая состоит из деревьев, образующих лес, и предназначена для представления набора множеств. Эта структура данных позволит выполнить операций ОБЪЕДИНИТЬ и НАЙТИ за почти линейное время.

Допустим, что каждое множество А представлено корневым неориентированным деревом узлам которого поставлены в соответствие элементы из А. Корню этого дерева приписано имя самого множества. Операцию можно выполнить, преобразуя корень дерева в сына корня дерева и заменяя имя в корне дерева на С. Операцию можно выполнить, определяя положение узла, представляющего элемент в некотором дереве из леса, и проходя путь из этого узла в корень дерева где помещено имя множества, содержащего

В такой схеме сложность слияния двух деревьев равна постоянной. Однако сложность выполнения операции имеет порядок длины пути из узла в корень. Эта длина может быть Поэтому сложность выполнения операций ОБЪЕДИНИТЬ, за которыми идут операций НАЙТИ, может достигать Например, вычислим сложность выполнения последовательности операций

Выполнение операций ОБЪЕДИНИТЬ приводит к дереву, изображенному на рис. 4.16. Сложность выполнения операций НАЙТИ пропорциональна

Однако ее можно уменьшить, если проводить балансировку деревьев. Для этого можно в каждом дереве считать число узлов и, сливая два множества, всегда присоединять меньшее дерево к корню большего. Этот способ аналогичен вливанию меньшего множества в большее, которое мы применяли в предыдущем разделе.

Лемма 4.1. Если при выполнении каждой операции ОБЪЕДИНИТЬ корень дерева с меньшим числом узлов (при равенстве узлов берется любое дерево) преобразуется в сына корня дерева с большим числом узлов, то высота дерева в лесу может достичь значения только если оно имеет не менее узлов.

Доказательство. Доказательство проведем индукцией по Для утверждение верно, поскольку каждое дерево имеет

Рис. 4.16. Дерево после выполнения операций ОБЪЕДИНИТЬ.

по крайней мере один узел. Допустим, что утверждение верно для всех значений параметра, меньших Пусть дерево высоты с наименьшим числом узлов. Тогда оно должно было получиться в результате слияния деревьев где дерево высоты него узлов не больше, чем По предположению индукции имеет не менее узлов, и, значит, Та имеет не менее узлов, откуда следует, что имеет не менее узлов.

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

Изложим еще одну модификацию этого алгоритма, называемую сжатием путей. Поскольку в общей сложности преобладает сложность операций НАЙТИ, попробуем уменьшить ее. Всякий раз, когда выполняется операция мы проходим путь от узла до корня Пусть узлы на этом пути. Тогда каждый из узлов делается сыном корня. На рис. 4.17, б отражено влияние операции на дерево, приведенное на рис. 4.17, а.

Рис. 4.17. Результат сжатия путей.

Вся процедура слияния деревьев для задачи ОБЪЕДИНИТЬ - НАЙТИ, включая сжатие путей, выражена в следующем алгоритме.

Алгоритм 4.3. Алгоритм быстрого объединения непересекающихся множеств

Вход. Последовательность а операций ОБЪЕДИНИТЬ и НАЙТИ, выполняемых на наборе множеств, элементы которых представлены целыми числами от 1 до Предполагается, что имена множеств также являются целыми числами от 1 до и вначале множество с именем состоит из единственного элемента — самого числа

Выход. Последовательность ответов на операции НАЙТИ из а. Ответ на каждую операцию НАЙТИ надо получить перед просмотром очередной операции в а.

Метод. Описание алгоритма состоит из трех частей: организация начальной структуры, выполнение операции НАЙТИ и выполнение операции ОБЪЕДИНИТЬ.

1. Организация начальной структуры. Для каждого элемента образуем узел Полагаем Вначале каждый узел сам является деревом. Чтобы можно было определять корень множества образуем такой массив КОРЕНЬ, что указывает на Чтобы определить узел, содержащий элемент образуем массив вначале

2. Выполнение операции Программа приведена на рис. 4.18. Начиная с узла идем по пути, ведущему к корню дерева, и выписываем встретившиеся узлы. По достижении

Рис. 4.18. Выполнение операции

корня выдается имя множества, а каждый узел из пройденного пути делается сыном корня.

3. Выполнение операции С помощью массива КОРЕНЬ находим корни деревьев, представляющих множества Затем делаем корень меньшего дерева сыном корня большего дерева. См. рис.

Покажем, что сжатие путей значительно ускоряет работу алгоритма. Чтобы подсчитать это улучшение, введем функции

Рис. 4.19. Выполнение операции

Рис. 4.20. Несколько значений функции

Пусть

Функция растет очень быстро, как видно из таблицы на рис. 4.20. Функция определяется как наименьшее число для которого Функция растет очень медленно. Действительно, для всех "практических" значений а именно для всех

Теперь покажем, что алгоритм 4.3 выполнит последовательность о из операций ОБЪЕДИНИТЬ и НАЙТИ за время, не большее где с и с — постоянные, причем с зависит от с. Для простоты предположим, что выполнение операции ОБЪЕДИНИТЬ занимает "единицу времени", а операции время, пропорциональное числу узлов, лежащих на пути из узла с меткой в корень дерева, содержащего этот узел.

Определение. Удобно определить ранг узла относительно последовательности о операций ОБЪЕДИНИТЬ и НАЙТИ следующим образом:

1. Удалить из о операции НАЙТИ.

2. Выполнить получившуюся последовательность операций ОБЪЕДИНИТЬ.

3. Ранг узла это его высота в получившемся лесу.

Докажем некоторые важные свойства ранга узла.

Лемма 4.2. Существует не более узлов ранга

Доказательство. По лемме 4.1 каждый узел ранга имеет по крайней мере потомков в лесу, построенном при выполнении Так как множества потомков любых двух различных узлов одинаковой высоты в лесу не пересекаются, а общее число непересекающихся множеств, содержащих не менее узлов, не превосходит то узлов ранга не может быть больше

Следствие. Ранг любого узла не превосходит

Лемма 4.3. Если в какой-то момент выполнения последовательности а узел оказался подлинным потомком узла то его ранг меньше ранга узла

Доказательство. Если в какой-то момент выполнения последовательности узел стал потомком узла то будет потомком узла и в лесу, построенном при выполнении . Поэтому высота узла должна быть меньше высоты узла и, так что ранг узла меньше ранга узла

Разобьем ранги на группы. Отнесем ранг к группе Например, ранги и 1 находятся в группе 0, ранг 2 — в группе 1, ранги 3 и 4 — в группе 2, ранги от 5 до 16 — в группе 3. Для наибольший возможный ранг, т. е. попадает в группу

Исследуем сложность выполнения последовательности из операций ОБЪЕДИНИТЬ и НАЙТИ. Так как каждую операцию ОБЪЕДИНИТЬ можно выполнить за единицу времени, то все операции ОБЪЕДИНИТЬ из а можно выполнить за время Для того чтобы оценить сложность выполнения всех операций НАЙТИ, применим один важный "бухгалтерский" трюк. За каждое выполнение операции НАЙТИ наложим штраф как на само выполнение, так и на некоторые перемещаемые узлы. Искомая общая сложность будет равна сумме всех штрафов, налагаемых на выполнение операций НАЙТИ и на перемещаемые узлы.

Штрафы за выполнение операции налагаются следующим образом. Пусть узел на пути из узла, представляющего I, в корень дерева, содержащего

1. Если корень или имеет ранг, который принадлежит не той же группе, что и ранг узла V, то выполнение штрафуется на одну единицу времени.

2. Если ранги узла и его отца принадлежат одной группе, то на узел налагается штраф в одну единицу времени.

По лемме 4.3 ранг узлов по мере прохождения вверх по пути монотонно возрастает. А так как различных групп рангов не больше по правилу 1 никакое выполнение операции НАЙТИ не

штрафуется более чем на единиц времени. Если применяется правило 2, то узел будет перемещен и сделан сыном узла с большим рангом, чем его предыдущий отец. Если узел принадлежит группе то он может перемещаться и штрафоваться не более раз, прежде чем приобретет отца из группы с более высоким рангом. Если ранг узла принадлежит группе 0, то он может перемещаться не более одного раза, прежде чем приобретет отца из более высокой группы. С этого момента перемещение узла будет штрафоваться по правилу 1 сложностью выполнения операции НАЙТИ.

Чтобы получить верхнюю границу штрафов, налагаемых на узлы, умножим наибольший штраф, который можно наложить на узел с рангом из данной группы, на число узлов в этой группе и просуммируем по всем группам рангов. Пусть число узлов, ранг которых принадлежит группе Тогда по лемме

Наибольший штраф на узел с рангом из группы не превосходит Поэтому наибольший штраф для узлов, ранги которых принадлежат группе ограничен числом Это утверждение, очевидно, верно и для Поскольку групп рангов не больше то суммарный штраф, налагаемый на все узлы, не превосходит Следовательно, общее время, требуемое для выполнения операций НАЙТИ, состоит из времени, не большего на которое оштрафовано выполнение этих операций, и времени, не большего на которое оштрафованы узлы. Таким образом, мы доказали следующую теорему.

Теорема 4.4. Пусть с — произвольная постоянная. Найдется другая постоянная с, зависящая от с и такая, что алгоритм 4.3 выполнит последовательность а из операций ОБЪЕДИНИТЬ и НАЙТИ на элементах не более чем за единиц времени.

Доказательство. Рассуждать, как выше.

В качестве упражнения предлагаем показать, что если в последовательности а наряду с операциями ОБЪЕДИНИТЬ и НАЙТИ допускаются основные операции ВСТАВИТЬ и то ее все равно можно выполнить за время

Неизвестно, точна ли оценка времени работы алгоритма 4.3, даваемая теоремой Однако в оставшейся части раздела мы докажем, поскольку это теоретически интересно, что время работы

Рис. 4.21. Результат операции ЧН.

алгоритма 4.3 нелинейно по Для этого построим конкретную последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, на которой алгоритм 4.3 работает нелинейное время.

Удобно ввести новую операцию над деревьями, которую мы будем называть ЧАСТИЧНО НАЙТИ - сокращенно ЧН. Пусть дерево, в котором узлы образуют путь из узла к его предку не обязательно корень). Операция делает каждый из узлов сыном узла Мы будем говорить, что эта операция ЧН имеет длину (если то длина равна 0). На рис. отражено влияние операции на дерево, приведенное на рис. 4.21, а.

Пусть дана последовательность а операций ОБЪЕДИНИТЬ и НАЙТИ. Когда выполняется данная операция НАЙТИ из мы находим положение узла в некотором дереве и идем по пути из и в корень этого дерева. Теперь предположим, что выполняются только операции ОБЪЕДИНИТЬ из а операции НАЙТИ не выполняются. В результате получается некоторый лес Действие данной операции НАЙТИ из все еще можно уловить, если найти в положение узлов которые должна была использовать эта операция НАЙТИ, и затем выполнить ЧН Заметим, что узел может больше не быть корнем в

Для вывода нижней оценки времени работы алгоритма 4.3 исследуем его поведение на последовательности операций НАЙТИ, за которыми следуют операции ЧН. Эту последовательность можно заменить последовательностью операций ОБЪЕДИНИТЬ и НАЙТИ с тем же временем работы. Из описанных ниже специальных

Рис. 4.22. Дерево

деревьев мы построим последовательности операций ОБЪЕДИНИТЬ и ЧН, на которых время работы алгоритма 4.3 более чем линейно.

Определение. Для пусть дерево, в котором

1) глубина каждого листа равна

2) каждый узел высоты имеет сыновей,

Таким образом, корень дерева имеет 2 сыновей, каждый из которых является корнем экземпляра дерева На рис. 4.22 изображено дерево

Лемма 4.4. Для каждого можно построить дерево которое порождается некоторой последовательностью операций ОБЪЕДИНИТЬ и содержит в качестве подграфа дерево причем по меньшей мере четверть узлов дерева являются листьями в

Доказательство. Доказательство проводится индукцией по Для лемма тривиальна, ибо состоит из одного узла. Чтобы построить для построим сначала экземпляров Образуем дерево выбрав один экземпляр и затем влив в него один за другим каждый из оставшихся экземпляров. Корень полученного дерева имеет (среди других) 2 сыновей, каждый из которых является корнем дерева

Пусть общее число узлов в число листьев в Тогда

и

откуда

Заметим, что для справедливо неравенство поэтому

Комбинируя (4.3) с (4.4), получаем

Лемма доказана.

Мы будем строить последовательность операций ОБЪЕДИНИТЬ и ЧН, которая сначала даст дерево а затем выполнит ЧН на листьях подграфа Сначала покажем, что для каждого найдется такое число что можно выполнить ЧН длины I последовательно на каждом листе дерева

Определение. Пусть такое наименьшее значение что если заменить каждое поддерево в с корнем высоты А любым деревом, имеющим I листьев и высоту не меньше 1, то на каждом листе полученного дерева можно будет выполнить ЧН длины с.

Лемма 4.5. Значение определено (т. е. конечно) для всех больших нуля.

Доказательство. В доказательстве применяется двойная индукция. Мы хотим доказать наше утверждение индукцией по с. Но для доказательства этого утверждения для с, исходя из истинности его для надо провести индукцию по

Базис, т. е. случай доказывается легко. для всех поскольку ЧН длины 1 не перемещает никаких узлов.

Теперь, чтобы провести индукцию по с, предположим, что для всех определено значение Мы должны показать, что определено для всех Это делается индукцией по

Для базиса индукции по I докажем, что

Заметим, что по определению числа при поддеревья в с корнями высоты заменяются деревьями с единственным листом. Пусть множество узлов высоты в дереве Очевидно, что в этом преобразованном дереве каждый лист является подлинным потомком единственного элемента множества Поэтому, если бы мы смогли выполнить операции ЧН длины на всех элементах множества то, конечно, смогли бы выполнить ЧН длины с на всех листьях.

Пусть По предположению индукции для с число существует. Все узлы высоты имеют по сыновей каждый, причем все сыновья принадлежат Если удалить из всех подлинных потомков узлов, входящих в то тем самым каждое поддерево с корнями на высоте заменится деревом высоты 1 с листьями. По определению число достаточно велико, так что операции ЧН длины можно выполнить на всех листьях, т. е. элементах множества

Теперь, чтобы завершить индукцию по с, осталось сделать шаг индукции по В частности, покажем, что для

Чтобы доказать неравенство (4.5), положим и обозначим через его правую часть. Нам надо найти способ заменить каждый узел высоты деревом с листьями, а затем на каждом листе выполнить операцию ЧН длины с. Начнем с выполнения операций ЧН на листьях каждого подставляемого дерева. По предположению индукции по это сделать можно.

Выполнив ЧН на листьях, находим, что 1-й лист каждого подставляемого дерева теперь имеет отца, отличного от отца листа любого другого подставляемого дерева. Множество таких отцов обозначим через Если мы смогли выполнить операции ЧН длины на этих отцах, то можем выполнить ЧН длины с на листьях. Пусть 5 — поддерево с корнем высоты Легко проверить, что 5 содержит листьев в Поэтому после выполнения операций ЧН число узлов в которые также принадлежат не превосходит 2 Множество, оставшееся от 5, можно, следовательно, рассматривать как произвольное дерево с листьями, которые принадлежат По предположению индукции для неравенство (4.5) справедливо.

Теорема 4.5. Временная сложность алгоритма 4.3 больше для любой постоянной с.

Доказательство. Пусть с — такая постоянная, что алгоритм 4.3 выполнит любую последовательность из операций ОБЪЕДИНИТЬ и операций НАЙТИ не более чем за единиц времени. Выберем и вычислим ). Построим с помощью последовательности операций ОБЪЕДИНИТЬ. Так как можно выполнить ЧН длины на каждом листе вложенного дерева листья которого занимают более четверти узлов дерева то эта последовательность операций ОБЪЕДИНИТЬ и ЧН потратит более единиц времени; получили противоречие.