Level Ancestor problem — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
[[Файл:LevelAncestor.png|120px|thumb|right]]'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
+
'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.
+
 
 
{{Задача
 
{{Задача
 
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.  
 
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.  
 
}}
 
}}
== Наивная реализация и двоичные подъемы ==
+
== Наивная реализациb и двоичные подъемы ==
[[Файл:Двоичные_подъемы.png|200px|thumb|right|Двоичные подъемы]]
+
[[Файл:LevelAncestor.png|200px|right]]
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>, что так же в худшем случае работает за <tex>O(n)</tex>. Получили алгоритм за <tex><O(n),O(n)></tex>, где время ответа на запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]]  , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex><O(n \log n),O(\log n)></tex>.
+
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>, что так же в худшем случае работает за <tex>O(n)</tex>. Получили алгоритм за <tex><O(n),O(n)></tex>, где время ответа на запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]]  , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex><O(n \log n),O(\log n)></tex>. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам алгоритм <tex><O(n^2),O(1)></tex>.
 +
В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.
 
== Использование Heavy-light декомпозиции ==
 
== Использование Heavy-light декомпозиции ==
 
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex><O(n), O(\log n)></tex>.
 
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex><O(n), O(\log n)></tex>.
 
== Алгоритм лестниц ==
 
== Алгоритм лестниц ==

Версия 23:53, 6 мая 2019

Задача о уровне предка (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.


Задача:
Дано корневое дерево [math]T[/math] c [math]n[/math] вершинами. Поступают запросы вида [math]LA(v, k)[/math], для каждого из которых необходимо найти предка вершины [math]v[/math], который находится на расстоянии [math]k[/math] от корня дерева [math]T[/math].

Наивная реализациb и двоичные подъемы

LevelAncestor.png

Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за [math]O(n)[/math]), после чего можем из вершины [math]v[/math] подняться до необходимой глубины вершины [math]k[/math], что так же в худшем случае работает за [math]O(n)[/math]. Получили алгоритм за [math]\lt O(n),O(n)\gt [/math], где время ответа на запрос можно улучшить до [math]O(\log n)[/math] c помощью предподсчета двоичных подъемов , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до [math]\lt O(n \log n),O(\log n)\gt [/math]. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам алгоритм [math]\lt O(n^2),O(1)\gt [/math]. В данном примере поступает запрос [math]LA(v, 2)[/math], на который алгоритм должен дать ответ h.

Использование Heavy-light декомпозиции

Этот алгоритм базируется на различных способах декомпозиции дерева (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины [math]v[/math] мы можем за [math]O(\log n)[/math]. Данное разбиение можно строить за [math]O(n)[/math], что дает нам алгоритм за [math]\lt O(n), O(\log n)\gt [/math].

Алгоритм лестниц