анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 10 Алгоритмы на деревьях У деревьев имеются специальные свойства, благодаря которым алгорит- мы, специализированные для деревьев, работают эффективнее, чем для графов общего вида. В этой главе приведена подборка таких алгоритмов. В разделе 10.1 вводятся общие понятия и алгоритмы, относящиеся к де- ревьям. Центральная задача – найти диаметр дерева, т. е. максимальное расстояние между двумя его вершинами. Мы изучим два алгоритма ее ре- шения с линейным временем. Раздел 10.2 посвящен обработке запросов к деревьям. Мы узнаем, как с помощью обхода дерева обрабатывать различные запросы, касающиеся поддеревьев и путей. А затем обсудим методы нахождения наименьшего общего предка и пакетный алгоритм, основанный на объединении струк- тур данных. В разделе 10.3 представлено два метода обработки деревьев: центроид- ная декомпозиция и heavy-light декомпозиция. 10.1. Базовые понятия Дерево – это связный ациклический граф, содержащий n вершин и n − 1 ребер. Удаление любого ребра разбивает дерево на две компоненты связ- ности, а добавление любого ребра создает цикл. Между любыми двумя вершинами дерева существует единственный путь. Листьями дерева на- зываются вершины, имеющие только одного соседа. Рассмотрим дерево, изображенное на рис. 10.1. В нем 8 вершин и 7 ре- бер, листьями являются вершины 3, 5, 7 и 8. 1 4 2 3 7 5 6 8 Рис. 10.1. Дерево, имеющее 8 вершин и 7 ребер В корневом дереве одна из вершин считается корнем дерева, а все осталь- ные располагаются под ней. Вершины, расположенные непосредственно 158 Глава 10. Алгоритмы на деревьях под некоторой вершиной, называются ее дочер- ними вершинами, а вершина, расположенная не- посредственно над некоторой вершиной, – ее родителем. У каждой вершины, кроме корня, имеется ровно один родитель. У корня родителя нет. Корневое дерево имеет рекурсивную струк- туру: каждая вершина играет роль корня подде- рева, содержащего эту вершину и все вершины, принадлежащие поддеревьям ее дочерних вер- шин. На рис. 10.2 показано корневое дерево с кор- нем в вершине 1. Дочерними для вершины 2 яв- ляются вершины 5 и 6, а родителем вершины 2 – вершина 1. Поддерево вершины 2 состоит из вершин 2, 5, 6 и 8. 10.1.1. Обход дерева Для обхода вершин дерева применимы общие алгоритмы обхода гра- фов. Однако обход дерева реализовать проще, чем в общем случае, по- скольку в нем нет циклов и невозможно попасть в вершину с нескольких направлений. Чаще всего для обхода дерева применяют поиск в глубину, начиная с произвольной вершины. Можно использовать следующую рекурсивную функцию: void dfs(int s, int e) { // обработать вершину s for (auto u : adj[s]) { if (u != e) dfs(u, s); } } Функции передаются два параметра: текущая вершина s и предыду- щая вершина e. Параметр e гарантирует, что далее будут просматриваться только еще не посещенные вершины. При таком вызове поиск начинается с вершины x: dfs(x, 0); При первом вызове функции e = 0, поскольку предыдущей вершины еще нет, и, следовательно, разрешено двигаться по дереву в любом направле- нии. Динамическое программирование можно использовать для вычис- ления некоторой информации в процессе обхода дерева. Показанный 1 4 2 3 7 5 6 8 Рис. 10.2. Корневое дере- во, в котором вершина 1 является корнем 10.1. Базовые понятия 159 ниже код для каждой вершины s вычисляет count [ s] – количество вершин в ее поддереве. Поддерево содержит саму вершину и все вершины, принад- лежащие поддеревьям ее дочерних вершин, поэтому количество вершин можно вычислить рекурсивно: void dfs(int s, int e) { count[s] = 1; for (auto u : adj[s]) { if (u == e) continue; dfs(u, s); count[s] += count[u]; } } Обход двоичного дерева. В двоичном дереве каждая вершина имеет левое и правое поддеревья (возможно, пустые). Существует три распро- страненных способа обхода двоичных деревьев: • прямой порядок: сначала обрабатывается корневая вершина, после чего обходится левое, а затем правое поддерево; • внутренний порядок: сначала обходится левое поддерево, затем об- рабатывается корневая вершина, потом обходится правое поддере- во; • обратный порядок: сначала обходится левое поддерево, затем пра- вое поддерево, потом обрабатывается корневая вершина. Для дерева на рис. 10.3 прямым порядком будет [1, 2, 4, 5, 6, 3, 7], внут- ренним – [4, 2, 6, 5, 1, 3, 7], а обратным – [4, 6, 5, 2, 7, 3, 1]. Если известны последовательности посеще- ния вершин в прямом и внутреннем порядке, то можно реконструировать его структуру. Напри- мер, единственное дерево с прямым порядком вершин [1, 2, 4, 5, 6, 3, 7] и внутренним порядком [4, 2, 6, 5, 1, 3, 7] показано на рис. 10.3. Обратный и внутренний порядок также однозначно опре- деляют структуру дерева. Но деревьев с одними и теми же прямым и обратным порядками вершин может быть несколько. 10.1.2. Вычисление диаметра Диаметром дерева называется максимальная длина пути между двумя его вершинами. На рис. 10.4 изображено дерево диаметра 4, которому со- ответствует путь длины 4 между вершинами 6 и 7. Отметим, что в этом дереве есть и другой путь длины 4 между вершинами 5 и 7. 1 2 3 4 5 6 7 Рис. 10.3. Двоичное дерево 160 Глава 10. Алгоритмы на деревьях Ниже мы обсудим два алгоритма вычисле- ния диаметра дерева с временной сложно- стью O(n). Первый основан на динамическом программировании, во втором используется поиск в глубину. Первый алгоритм. Общий подход к зада- чам о деревьях заключается в том, чтобы сначала произвольным образом выбрать корень, а затем решить задачу отдельно для каждого поддерева. На этой идее основан первый алгоритм вычисле- ния диаметра. Сделаем важное наблюдение: на каждом пути в корневом дереве имеется высшая точка. Таким образом, для каждой вершины x мы можем вы- числить длину самого длинного пути с высшей точкой x. Один из таких путей соответствует диа- метру дерева. На рис. 10.5 высшей точкой пути, соответствующей диаметру, является вершина 1. Для каждой вершины x мы вычислим два зна- чения: • toLeaf (x): максимальная длина пути от x до листа; • maxLength (x): максимальная длина пути с высшей точкой x. На рис. 10.5 toLeaf (1) = 2, поскольку существует путь 1 → 2 → 6, и maxLength (1) = 4, поскольку существует путь 6 → 2 → 1 → 4 → 7. В данном случае maxLength (1) равно диаметру. Чтобы вычислить эти значения для всех вершин за время O(n), можно воспользоваться динамическим программированием. Сначала для вы- числения toLeaf (x) мы переберем дочерние вершины x, выберем из них вершину c с максимальным значением toLeaf (c) и прибавим к этому зна- чению 1. Затем для вычисления maxLength (x) мы выберем две различные дочерние вершины a и b – такие, что сумма toLeaf (a)+ toLeaf (b) макси- мальна, и прибавим к этой сумме 2. (Случаи, когда у x меньше двух дочер- них вершин, особые, но они легко разбираются.) Второй алгоритм. Еще один эффективный способ вычислить диаметр дерева основан на поиске в глубину. Сначала выберем в дереве произволь- ную вершину a и найдем вершину b, самую далекую от a. Затем найдем вершину c, са- мую далекую от b. Диаметр дерева равен рас- стоянию между b и c. На рис. 10.6 показан один из способов вы- бора вершин a, b и c при вычислении диамет- ра дерева. 1 4 2 3 7 5 6 Рис. 10.4. Дерево диаметра 4 1 4 2 3 7 5 6 Рис. 10.5. Вершина 1 – высшая точка на пути, реализующем диаметр 1 4 2 3 7 5 6 a b c Рис. 10.6. Вершины a, b и c в процессе вычисления диаметра 10.1. Базовые понятия 161 Это элегантный метод, но почему он дает правильный результат? По- лезно нарисовать дерево так, чтобы путь, реализующий диаметр, был рас- положен горизонтально, а остальные вершины «свисали» с него (рис. 10.7). Буквой x обозначено место, в котором путь из вершины a соединяется с путем, реализующим диаметр. Самая далекая от a вершина – это b, c или еще какая-то вершина, отстоящая от x на такое же или большее расстоя- ние. Таким образом, эту вершину всегда можно выбрать в качестве конеч- ной точки пути, реализующего диаметр. 1 4 2 3 7 5 6 a b c x Рис. 10.7. Почему этот алгоритм работает 10.1.3. Все максимальные пути Наша следующая задача – для каждой вершины дерева x вычислить значение maxLength (x): максимальную длину пути, начинающегося в x. На рис. 10.8 показаны дерево и значения maxLength для него. Это можно рассматривать как обобщение задачи о диаметре дерева, поскольку наи- большая из этих длин равна диаметру. Эту задачу также можно решить за время O(n). 1 4 2 3 6 5 maxLength (1) = 2 maxLength (2) = 2 maxLength (3) = 3 maxLength (4) = 3 maxLength (5) = 3 maxLength (6) = 3 Рис. 10.8. Вычисление длин максимальных путей И снова выберем какую-то вершину в качестве корня. Первая часть задачи – для каждой верши- ны x вычислить максимальную длину пути, про- ходящего вниз через дочернюю вершину x. Так, самый длинный путь из вершины 1 проходит че- рез ее дочернюю вершину 2 (рис. 10.9). Эту часть легко решить за время O(n), воспользовавшись динамическим программированием, как и выше. Вторая часть задачи – для каждой вершины x вычислить путь, проходящий вверх, через ее ро- 1 4 2 3 5 6 Рис. 10.9. Самый длин- ный путь, начинающийся в вершине 1 162 Глава 10. Алгоритмы на деревьях дителя p. Например, самый длинный путь из вер- шины 3 проходит через ее родителя 1 (рис. 10.10). На первый взгляд, достаточно сначала перейти в p, а затем выбрать самый длинный путь(вверх или вниз) из p. Однако это не всегда правильно, потому что такой путь может проходить через x (рис. 10.11). И тем не менее вторую часть задачи можно решить за время O(n), если хранить дли- ны двух максимальных путей для каждой верши- ны x: • maxLength 1 (x): длина максимального пути из x в листовую вершину; • maxLength 2 (x):длина максимального пути из x в листовую вершину, следующего в другом направлении, нежели первый путь. Так, на рис. 10.11 maxLength 1 (1) = 2 для пути 1 → 2 → 5 и maxLength 2 (1) = 1 для пути 1 → 3. Наконец, чтобы определить длину максималь- ного пути из вершины x, проходящего вверх че- рез ее родителя p, рассмотрим два случая: если путь, соответствующий maxLength 1 (p), проходит через x, то длина максимального пути равна maxLength 2 (p)+ 1, в противном случае длина мак- симального пути равна maxLength 1 (p)+ 1. 10.2. Запросы к деревьям В этом разделе мы будем рассматривать запросы к корневым деревьям. Обычно они относятся к поддеревьям и путям в дереве и могут быть обра- ботаны за постоянное или логарифмическое время. 10.2.1. Нахождение предков k-м предком вершины x корневого дерева называется вершина, в которую мы попадем, поднявшись на k уровней вверх от x. Обозна- чим ancestor (x, k) k-го предка вершины x (или 0, если такого предка не сущест вует). На рис. 10.12 ancestor (2, 1) = 1, а ancestor (8, 2) = 4. Вычислить ancestor (x, k)проще всего, после- довательно выполнив k шагов по дереву. Но вре- менная сложность этого метода равна O(k), что может оказаться медленно, поскольку в дереве с n вершинами может встретиться путь длины n. 1 4 2 3 5 6 Рис. 10.10. Самый длин- ный путь, начинающийся в вершине 3 и проходящий через ее родителя 1 4 2 3 5 6 Рис. 10.11. В этом случае следует выбрать второй по длине путь из роди- теля 1 2 4 5 6 3 7 8 Рис. 10.12. Нахождение предков вершин 10.2. Запросы к деревьям 163 К счастью, значение ancestor (x, k)для любой вершины x можно вы- числить за время O(log k) после предобработки. Как и в разделе 7.5.1, идея заключается в том, чтобы предварительно вычислить все значения ancestor (x, k)для случаев, когда k – степень двойки. Для дерева, изобра- женного на рис. 10.12, получаем: х 1 2 3 4 5 6 7 8 ancestor(x ,1) 0 1 4 1 1 2 4 7 ancestor(x ,2) 0 0 1 0 0 1 1 4 ancestor(x ,4) 0 0 0 0 0 0 0 0 … Поскольку у любой вершины заведомо меньше n предков, достаточно вычислить O(log n) значений для каждой вершины, так что предобработка займет время O(n log n). После этого любое значение ancestor (x, k)можно будет вычислить за время O(log k), представив k в виде суммы степеней двойки. 10.2.2. Поддеревья и пути Массив обхода дерева содержит вершины корневого дерева в порядке их посещения в процессе поиска в глубину из корня. На рис. 10.13 показаны дерево и массив обхода для него. 1 2 3 4 5 6 7 8 9 1 2 6 3 4 7 8 9 5 Рис. 10.13. Дерево и массив его обхода У массива обхода дерева есть важное свойство: каждому поддереву со- ответствует его подмассив, первым элементом которого является корень этого поддерева. На рис. 10.14 показан подмассив, соответствующий под- дереву вершины 4. 1 2 6 3 4 7 8 9 5 Рис. 10.14. Поддерево вершины 4 в массиве обхода дерева 164 Глава 10. Алгоритмы на деревьях Запросы о поддеревьях. Предположим, что каждой вершине дерева сопоставлено некоторое значение, и наша задача – обработать запросы двух типов: изменить значение в вершине и вычислить сумму значений в поддереве вершины. Для решения этой задачи мы построим массив об- хода дерева, содержащий три значения для каждой вершины: ее иденти- фикатор, размер поддерева и значение в вершине. На рис. 10.15 показаны дерево и соответствующий ему массив. 1 2 3 4 5 6 7 8 9 2 3 5 3 1 4 4 3 1 node id subtree size node value 1 2 6 3 4 7 8 9 5 9 2 1 1 4 1 1 1 1 2 3 4 5 3 4 3 1 1 ИД вершины Размер поддерева Значение в вершине Рис. 10.15. Массив обхода дерева для вычисления суммы по поддереву Пользуясь этим массивом, мы можем вычислить сумму значений в любом поддереве. Для этого нужно сначала определить размер поддере- ва, а затем просуммировать значения в соответствующих вершинах. На рис. 10.16 показано, к каким значениям мы обращаемся при вычислении суммы значений в поддереве вершины 4. Из последней строки массива видно, что сумма значений равна 3 + 4 + 3 + 1 = 11. node id subtree size node value 1 2 6 3 4 7 8 9 5 9 2 1 1 4 1 1 1 1 2 3 4 5 3 4 3 1 1 ИД вершины Размер поддерева Значение в вершине Рис. 10.16. Вычисление суммы значений в поддереве вершины 4 Для эффективного ответа на такие запросы достаточно сохранить по- следнюю строку массива в двоичном индексном дереве или в дереве от- резков. После этого мы сможем изменять значение и вычислять сумму значений за время O(log n). Запросы о путях. С помощью массива обхода дерева мы можем эф- фективно вычислять суммы значений на путях из корня в любую вершину 10.2. Запросы к деревьям 165 дерева. Рассмотрим, например, обработку запросов двух типов: измене- ние значения в вершине и вычисление суммы значений на пути из корня в вершину. Для решения этой задачи мы построим массив обхода дерева, в котором для каждой вершины будут храниться ее идентификатор, размер подде- рева и сумма значений на пути от корня к этой вершине (рис. 10.17). Если значение в некоторой вершине увеличивается на x, то суммы для всех вер- шин, принадлежащих ее поддереву, тоже увеличиваются на x. На рис. 10.18 показано, как будет выглядеть массив после увеличения значения в вер- шине 4 на 1. 1 2 3 4 5 6 7 8 9 4 5 3 5 2 3 5 3 1 node id subtree size path sum 1 2 6 3 4 7 8 9 5 9 2 1 1 4 1 1 1 1 4 9 12 7 9 14 12 10 6 ИД вершины Размер поддерева Сумма по пути Рис. 10.17. Массив обхода дерева для вычисления сумм по путям node id subtree size path sum 1 2 6 3 4 7 8 9 5 9 2 1 1 4 1 1 1 1 4 9 12 7 10 15 13 11 6 ИД вершины Размер поддерева Сумма по пути Рис. 10.18. Увеличение значения в вершине 4 на 1 Чтобы поддержать обе операции, мы должны уметь увеличивать все значения в диапазоне и получать одно значение. Это можно сделать за время O(log n)с помощью двоичного индексного дерева или дерева отрез- ков (см. раздел 9.2.3). 10.2.3. Наименьшие общие предки Наименьшим общим предком двух вершин корневого дерева называет- ся самая низко расположенная вершина, поддерево которой содержит обе эти вершины. Так, на рис. 10.19 наименьшим общим предком вершин 5 и 8 является вершина 2. 166 Глава 10. Алгоритмы на деревьях Эффективный поиск наименьшего общего предка двух вершин – часто встречающаяся за- дача. Мы обсудим два способа ее решения. Первый метод. Поскольку мы умеем эффек- тивно находить k-й предок любой вершины де- рева, то можем воспользоваться этим для раз- биения задачи на две части. Нам понадобятся два указателя, первоначально направленных на вершины, для которых мы ищем наименьший общий предок. Сначала проверим, что вершины, на которые направлены указатели, расположены на одном уровне дерева. Если это не так, сдвинем один из указателей вверх. После этого определим, какое минимальное число сдвигов обоих указателей вверх необходимо, чтобы они оказались направлены на одну и ту же вершину. Эта вершина и будет наименьшим общим предком. Поскольку обе части алгоритма можно вы- полнить за время O(log n), если воспользоваться предварительно вычис- ленной информацией, то наименьший общий предок любых двух вершин можно найти за время O(log n). На рис. 10.20 показано, как найти наименьший общий предок вершин 5 и 8 в рассматриваемом примере. Сначала мы сдвигаем второй указатель на один уровень вверх, так что вершина 6, на которую он указывает, нахо- дится на том же уровне, что и вершина 5. Затем после сдвига обоих указа- телей на один шаг вверх они указывают на вершину 2, которая и является наименьшим общим предком. 1 4 2 3 7 5 6 8 1 4 2 3 7 5 6 8 Рис. 10.20. Два шага для нахождения наименьшего общего предка вершин 5 и 8 Второй метод. Другой способ решения этой задачи был предложен в ра- боте Bender, Farach-Colton [3]. Он основан на расширенном массиве обхода дерева, который всегда называют эйлеровым обходом дерева. Для постро- 1 4 2 3 7 5 6 8 Рис. 10.19. Наименьшим общим предком вершин 5 и 8 является вершина 2 10.2. Запросы к деревьям 167 ения массива мы обходим вершины дерева, применяя поиск в глубину, и добавляем вершину в массив при каждом ее прохождении (а не только при первом посещении). Поэтому вершина, имеющая k дочерних вершин, встретится в массиве k + 1 раз, а всего в нем будет 2n − 1 элементов. В каж- дом элементе массива хранятся два значения: идентификатор вершины и ее глубина в дереве. На рис. 10.21 показан массив, соответствую щий дере- ву из рассматриваемого примера. node id depth 1 2 5 2 6 8 6 2 1 3 1 4 7 4 1 1 2 3 2 3 4 3 2 1 2 1 2 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ИД вершины Глубина Рис. 10.21. Эйлеров обход дерева для обработки запросов о наименьшем общем предке Теперь можно найти наименьший общий предок вершин a и b, отыскав вершину с минимальной глубиной, находящуюся между вершинами a и b в массиве. На рис. 10.22 показано, как ищется наименьший общий пре- док вершин 5 и 8. Вершина с минимальной глубиной, находящаяся между ними, – это вершина 2 глубины 2, поэтому она и является наименьшим общим предком. node id depth ↑ 1 2 5 2 6 8 6 2 1 3 1 4 7 4 1 1 2 3 2 3 4 3 2 1 2 1 2 3 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ИД вершины Глубина Рис. 10.22. Нахождение наименьшего общего предка вершин 5 и 8 Отметим, что поскольку одна вершина может встречаться в массиве несколько раз, возможно несколько способов выбрать промежуток между вершинами a и b. Но при любом выборе наименьший общий предок опре- деляется правильно. При использовании этой техники для нахождения наименьшего общего предка двух вершин достаточно обработать запрос о минимуме по диапа- зону. Стандартный способ обработки таких запросов с помощью дерева отрезков имеет временную сложность O(log n). Но, поскольку массив ста- тический, мы можем отвечать на них и за время O(1) после предобработки, занимающей время O(n log n). Вычисление расстояний. Наконец, рассмотрим задачу о вычислении расстояния между вершинами a и b (т. е. длины пути между ними). Ока- зывается, что ее можно свести к задаче о нахождении наименьшего об- 168 Глава 10. Алгоритмы на деревьях щего предка. Сначала произвольным образом выберем корень дерева. Тогда расстояние меж- ду вершинами a и b можно будет вычислить по формуле depth (a)+ depth (b)− 2 · depth (c), где c – наименьший общий предок a и b. Чтобы вычислить расстояние между верши- нами 5 и 8 на рис. 10.23, мы сначала находим их наименьший общий предок – вершину 2. Затем, поскольку глубины вершин depth (5) = 3, depth (8) = 4 и depth (2) = 2, то расстояние между вершинами 5 и 8 равно 3 + 4 − 2 · 2 = 3. 10.2.4. Объединение структур данных До сих пор мы рассматривали оперативные алгоритмы обработки за- просов к дереву. Они позволяют обрабатывать запросы один за другим, так что ответ на предыдущий запрос дается до получения следующего. Но существует много задач, когда свойство оперативности необязательно и можно воспользоваться пакетными алгоритмами. Такому алгоритму пере- дается весь набор запросов, и он вправе обрабатывать их в любом порядке. Зачастую спроектировать пакетный алгоритм проще, чем оперативный. Один из способов проектирования пакетного алгоритма состоит в том, чтобы выполнить обход дерева в глубину и создать в вершинах некоторые структуры данных. В каждой вершине s создается структура данных d [ s], основанная на структурах данных в дочерних вершинах s. Эта структура данных позволяет обрабатывать все запросы, относящиеся к s. В качестве примера рассмотрим следующую задачу: дано корневое де- рево, с каждой вершиной которого ассоциировано некоторое значение. Требуется отвечать на запросы о том, сколько вершин со значением x име- ется в поддереве вершины s. На рис. 10.24 поддерево вершины 4 содержит две вер- шины со значением 3. Для ответа на такие запросы можно воспользоваться структурой отображения (значения на число вершин с таким значе- нием). На рис. 10.25 показаны отображения для вершины 4 и ее дочерних вершин. Соз- дав такую структуру данных для каждой вершины, мы легко сможем обработать все запросы, поскольку на запрос, отно- сящийся к определенной вершине, можно 1 4 2 3 7 5 6 8 Рис. 10.23. Вычисление расстояния между вершинами 5 и 8 1 2 3 4 5 6 7 8 9 2 3 5 3 1 4 4 3 1 Рис. 10.24. Поддерево вершины 4 содержит две вершины со значением 3 10.3. Более сложные приемы 169 отвечать сразу после создания структуры данных для нее. Но создавать все структуры с нуля было бы слишком медленно. Вместо этого мы создадим в каждой вершине s начальную структуру данных d [ s], содержащую только значение, ассоциированное с s. После этого мы пробежимся по дочерним вершинам s и объединим d [ s] и все структуры d [ u], где u – дочерняя верши- на s. Например, в дереве из нашего примера отображение для вершины 4 создано путем объединения отображений на рис. 10.26, где первое ото- бражение – начальная структура данных для вершины 4, а остальные три соответствуют вершинам 7, 8 и 9. 4 1 3 1 1 1 1 3 4 1 2 1 Рис. 10.25. Обработка запросов с помощью отображений 4 1 3 1 1 1 3 1 Рис. 10.26. Объединение отображений в вершине Объединение в вершине s выполняется следующим образом: перебира- ем все дочерние вершины s и в каждой вершине u объединяем d [ s] с d [ u]. Мы всегда копируем содержимое d [ u] в d [ s]. Но предварительно содержи- мое d [ s] и d [ u] обменивается, если d [ s] меньше d [ u]. В результате каждое значение копируется всего O(log n)раз в процессе обхода дерева, что га- рантирует эффективность алгоритма. Для эффективного обмена структур данных a и b можно использовать такой код: swap(a,b); Гарантируется, что он работает за постоянное время, если a и b – струк- туры данных из стандартной библиотеки C++. 10.3. Более сложные приемы В этом разделе мы рассмотрим еще два метода работы с деревьями. Центро- идная декомпозиция заключается в разбиении дерева на меньшие подде- ревья и их рекурсивной обработке. При разновесной декомпозиции (heavy- light decomposition) дерево представляется в виде множества специальных путей, что позволяет эффективно обрабатывать запросы о путях. 170 Глава 10. Алгоритмы на деревьях 10.3.1. Центроидная декомпозиция Центроидом дерева с n вершинами называется такая вершина, удаление которой разбивает дерево на поддеревья, каждое из которых содержит не более ⌊n/2⌋ вершин. В каждом дереве существует центроид; чтобы его най- ти, нужно выбрать произвольный корень и всегда переходить в поддере- во с максимальным числом вершин до тех пор, пока текущая вершина не окажется центроидом. В методе центроидной декомпозиции мы сначала находим центроид дерева и обрабатываем все проходящие через него пути. После этого цент- роид удаляется, а оставшиеся поддеревья обрабатываются рекурсивно. Поскольку удаление центроида оставляет поддеревья, размер которых не превосходит половины размера исходного дерева, временная сложность такого алгоритма равна O(n log n), при условии что время обработки каж- дого поддерева линейно. На рис. 10.27 показан первый шаг алгорит- ма центроидной декомпозиции. В этом дере- ве вершина 5 является единственным цент- роидом, поэтому сначала обрабатываются пути, проходящие через вершину 5. Затем эта вершина удаляется из дерева, и рекурсивно обрабатываются три поддерева: {1, 2}, {3, 4} и {6, 7, 8}. С помощью центроидной декомпозиции мы, например, можем эффективно вычис- лить количество путей длины x в дереве. Для этого мы сначала находим центроид и вычисляем количество путей, про- ходящих через него. Это можно сделать за линейное время. Затем удаляем центроид и рекурсивно обрабатываем меньшие деревья. Временная слож- ность алгоритма равна O(n log n). 10.3.2. Heavy-light декомпозиция При heavy-light декомпозиции (heavy-light decomposition) 1 множество вершин дерева разбивается на множество тяжелых (heavy) путей. Тяже- лые пути создаются таким образом, что на пути между любыми двумя вершинами находится O(log n)подпутей, являющихся тяжелыми путями. Благодаря этой технике мы можем манипулировать вершинами на путях между вершинами дерева почти как элементами массива, добавляя лишь коэффициент порядка O(log n). Для построения тяжелых путей мы сначала произвольным образом вы- бираем корень дерева. Первый тяжелый путь начинается в корне и всегда 1 В работе Sleator, Tarjan [33] эта идея введена в контексте динамических деревьев с операциями link и cut. 1 2 3 4 5 6 7 8 Рис. 10.27. Центроидная декомпозиция 10.3. Более сложные приемы 171 идет в вершину, для которой размер поддерева максимален. Затем рекурсивно обрабатываются остальные поддеревья. На рис. 10.28 показано четыре тяжелых пути: 1–2–6–8, 3, 4–7 и 5 (два из них состоят всего из одной вершины). Теперь рассмотрим какой-нибудь путь между двумя вершинами дерева. Поскольку при созда- нии тяжелых путей всегда выбиралось поддерево максимального размера, то мы заведомо сможем разбить путь на O(log n) подпутей, каждый из ко- торых является подпутем единственного тяже- лого пути. На рис. 10.28 путь между вершинами 7 и 8 можно разбить на два тяжелых подпути: 7–4, затем 1–2–6–8. Достоинство heavy-light декомпозиции состоит в том, что каждый тяже- лый путь можно рассматривать как массив вершин. Например, с каждым тяжелым путем можно сопоставить дерево отрезков и поддержать слож- ные запросы о путях, например вычисление максимального значения вершины на пути или увеличение значения, ассоциированного с каждой вершиной на пути. Такие запросы можно обработать за время O(log 2 n) 2 , поскольку каждый путь состоит из O(log n)тяжелых путей, а каждый тяже- лый путь можно обработать за время O(log n). Хотя с помощью heavy-light декомпозиции можно решить много задач, следует помнить, что часто существует другое решение, реализовать кото- рое проще. В частности, вместо heavy-light декомпозиции нередко можно использовать методы, описанные в разделе 10.2.2. 2 log k n – то же самое, что (log n) k 1 4 2 3 7 5 6 8 Рис. 10.28. Разновесная декомпозиция |