Изменения
Нет описания правки
найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация и двоичные подъемы Использование Heavy-light декомпозиции ==
[[Файл:LevelAncestor.png|200px|thumb|right]]
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
что подняться на любую высоту из вершины <tex>v</tex> мы можем за время <tex>O(\log n)</tex>.
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.
В данном примере поступает запрос LA(v,2), на который алгоритм должен дать ответ h.
== Алгоритм лестниц ==
=== [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 ] ===
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> > времени и за <tex>O(n)</tex> памяти.
== Сравнение с наивными реализациями ==
Используя <tex>dfs</tex> посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
что так же в худшем случае работает за <tex>O(n)</tex>.
Получили алгоритм за < <tex>O(n), O(n)</tex> > времени и <tex>O(n)</tex> памяти, где время ответа на
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),
O(\log n)</tex> > времени и <tex>O(n \log n)</tex> памяти. Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику < <tex>O(n^2), O(1)</tex> > времени и <tex>O(n^2)</tex> памяти.
Таким образом, самым оптимальным из описанных как по времени, так и по памяти является алгоритм Macro-Micro-Tree.
== См. также ==
*[[Метод двоичного подъёма]]
*[[Heavy-light декомпозиция]]
== Источники информации ==
*[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]
*[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]
[[Категория: Алгоритмы и структуры данных]]
