Алгоритм Шибера-Вишкина — различия между версиями
(→Идея алгоритма) |
(→Подготовка) |
||
Строка 16: | Строка 16: | ||
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем, | Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем, | ||
что вершина является и своим предком, и своим потомком. | что вершина является и своим предком, и своим потомком. | ||
+ | |||
+ | {{Определение | ||
+ | |definition=<tex>u \in S(v)</tex> {{---}} вершина <tex>v</tex> находится в поддереве вершины <tex>v</tex> | ||
+ | }} | ||
{{Утверждение | {{Утверждение | ||
− | |statement=Пусть <tex>u | + | |statement=Пусть <tex>u \in S(v)</tex>. Тогда |
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex> | <tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex> | ||
|proof= | |proof= | ||
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют | По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют | ||
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с | отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с | ||
− | <tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> | + | <tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> лежит в отрезке <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>. |
}} | }} | ||
Строка 45: | Строка 49: | ||
'''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex> | '''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex> | ||
− | Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое. | + | Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{order} u</<tex>tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое. |
}} | }} | ||
Версия 19:26, 23 июня 2012
Алгоритм Шибера-Вишкина применяется для нахождения наименьшего общего предка двух вершин в дереве. Он использует
времени на подготовку и затем отвечает на каждый запрос за .Содержание
Идея алгоритма
Основная идея алгоритма следующая.
- Если бы дерево, в котором нужно искать было бы цепочкой, можно было бы найти просто взяв ту вершину, которая находится в дереве ближе к корню.
- Если дерево — полное двоичное дерево высоты , то можно сопоставить каждой вершине битовый вектор длиной (целое число от до ) и с помощью битовых операций над этими векторами найти
Тогда, представив данное дерево как полное двоичное дерево, в некоторых вершинах которого находится цепочка, можно научиться искать
в нем за .Подготовка
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем — поддеревья. Пусть
— такой порядок обхода.Обозначим за
количество вершин в поддереве вершины . Здесь и далее считаем, что вершина является и своим предком, и своим потомком.
Определение: |
— вершина находится в поддереве вершины |
Утверждение: |
Пусть . Тогда
|
По определению , вершин из поддерева образуют отрезок натуральных чисел длиной . Так как этот отрезок начинается с , то лежит в отрезке . |
Покроем дерево путями. А именно, сопоставим каждой вершине
число такое, что прообраз каждого в связен и является простым путем от какой-то вершины вниз до листа.Утверждение: |
В качестве можно выбрать , кратное максимальной степени двойки, где . |
Пусть , — максимально. Пусть есть вершина такая, что . Так как в отрезке, соответствующем вершине есть два числа, кратных , то там есть и число, кратное . Но тогда выбран неверно. Значит, в поддереве есть только одна такая вершина , что .Рассмотрим два случая. Первый случай Других таких вершин , что дает такую же степень двойки, нет. Значит, во всех поддеревьях значения отличаются от .Второй случай Так как в поддереве , представлены все -ы из отрезка , то рассмотрим того потомка вершины , что . Тогда, так как степень двойки у максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то — потомок , что в поддереве есть вершина с такой же степенью двойки. Значит, все вершины , у которых находятся в поддереве . Проведя аналогичное доказательство для , получим требуемое. |
Утверждение: |
, где |
Посмотрим на . Посмотрим на позицию самой правой единицы в .Так как в там еще , а в — уже единица, то в отрезке есть число, кратное .Докажем, что нет чисел, кратных . Пусть такое число нашлось. Тогда -й бит менялся хотя бы два раза, а значит, менялся -й бит. А значит, самый значащий отличающийся бит в и в больше, чем -й.Заметим, что функция просто выделяет номер самого значашего единичного бита.Функция Чтобы получить из отрезка число, кратное обнуляет все биты младше -го. , будучи уверенными, что оно там есть, достаточно обнулить битов в правой границе отрезка. |
Каждое значение
соответствует вершине в полном двоичном дереве высоты . В двоичном дереве будем нумеровать вершины в инфиксном порядке: обойдем левое поддерево, занумеруем вершину, обойдем правое поддерево. В двоичном дереве будет ребро между вершинами и , если в начальном дереве есть ребро . Стандартных для двоичного дерева ребер не будет. Они нужны только для того, чтобы занумеровать вершины и для следующего утверждения.Утверждение: |
Если в начальном дереве есть ребро ( ), то в построенном двоичном дереве
|
Посчитаем для каждого
множество всех его потомков в двоичном дереве. Заметим, что для хранения одного потомка достаточно хранить только его высоту в дереве. Чтобы восстановить его значение, нужно просто подняться на вверх от вершины . Поэтому, все это множество можно уместить в число: -й бит будет единицей, если есть потомок на высоте . Назовем это число .В дальнейшем
поможет в поиске . Также, нам понадобится еще следующая информация. — самая не глубокая вершина такая, что .Обработка запроса
Пусть
, — вершины в исходном дереве которых необходимо найти. Если , то они принадлежат одному простому пути, а следовательно ответом на запрос является , если , и , в противном случае. Теперь рассмотрим случай, когда , то есть и принадлежат разным простым путям. Найдем .Утверждение: |
, где |
Пусть | — индекс самой правой единицы в двоичном представлении . Из того, что общий предок и в полном двоичном дереве следует, что левых бит, совпадающих в и , должны быть такими же и в , а так как наименьший общий предок, то — минимальный такой индекс. То есть самый левый бит, в котором различаются и . А двоичное представление состоит из левых бит (или ), единички и нулей.
Найдем вершину
, где . На прошлом шаге была найдена вершина . Если бы в двоичном дереве были представлены все вершины, то это и было бы ответом. Но такой вершины может не оказаться. Воспользуемся значениями и . Они характеризуют пути из вершин и к корню. С их помощью (с помощью операции логическое и), можно получить список вершин, через которые проходят оба эти пути и взять с пересечения самую низкую посещаемую обоими.Для этого можно воспользоваться описанным при построении методом для нахождения
. После этих действий нами был получен путь, в котором находится ответ. Осталось посмотреть на точки входа и на путь . Это можно сделать с помощью посчитанной функции : найти , где — вершина предпоследнего пути в пути. Тогда, поднявшись от нее на один вверх по начальному дереву, получим искомую точку входа.Имея две точки входа, можно, как и в первом случае, сравнить их по высоте и выбрать более высокое из них.
Оценка сложности
Построение
Подсчет каждого из массивов занимает
. Это можно сделать, например, обходом в глубину.Запрос
Здесь нужно сделать
действий для ответа на запрос.