Изменения
Нет описания правки
'''Задача о уровне предка''' — (англ. "Level Ancestor problem") является задачей о превращении данного подвешенного дерева <tex>T</tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дереваэтого узла.
{{Задача
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex>\langle O(n), O(\log n) \rangle</tex>.
В данном примере поступает запрос LA(v,2), на который алгоритм должен дать ответ h.
== Алгоритм лестниц ==
=== Longest path decomposition <ref>[https://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf Longest path decomposition]</ref>===
Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом.
Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
'''function''' LA('''int''' v,'''int''' k):
'''int''' n = h(v); ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''
n = n - k; ''<font color="green">// на столько необходимо подняться до ответа</font>''
i = <tex>\lfloor \log_2 n\rfloor</tex>;
v = p[i][v] ''<font color="green">// делаем максимально большой прыжок вверх</font>''
i = n - i; ''<font color="green">// на столько осталось еще подняться</font>'' '''return''' ladder[way[v]][num[v] - i]; ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</font>''
=== Доказательство корректности ===
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex> >, где <tex>L</tex> это количество листьев.*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
Рассмотрим как можно улучшить данный алгоритм:
В итоге полученный алгоритм действительно работает за <tex>\langle O(n), O(1)\rangle </tex> времени и за <tex>O(n)</tex> памяти.
== Сравнение с наивными другими реализациями ==
Используя DFS посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
что так же в худшем случае работает за <tex>O(n)</tex>.
|-align="center"
!
| <tex>Предподсчет</tex>| <tex>Ответ</tex>на запрос| <tex>Память</tex>
|-align="center"
!Обычный подъем до нужного уровня
|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(n)</tex>
|}
== См. также ==
*[[Метод двоичного подъёма]]
*[[Heavy-light декомпозиция]]
== Примечания ==
<references/>
== Источники информации ==
*[https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf Level Ancestor problem simplified Cai Qi]
*[https://en.wikipedia.org/wiki/Level_ancestor_problem Wikipedia: LA]
[[Категория: Алгоритмы и структуры данных]]
