Алгоритм Тарьяна поиска LCA за О(1) в оффлайне

Материал из Викиконспекты
Версия от 20:20, 4 июня 2014; 188.227.78.144 (обсуждение) (Новая страница: «Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, есл...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее(offline). Каждый запрос к дереву - это 2 вершины v,u для которых нужно найти такую вершину k, что k-предок вершин v и u, и k имеет максимальную глубину из всех таких вершин. Алгоритм позволяет найти ответы для дерева из n вершин и m запросов за время О(n + m), т.е при достаточно большом m, за О(1) на запрос.

Алгоритм

фывфыв