74
правки
Изменения
Нет описания правки
Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее(offline).
Каждый запрос к дереву - это 2 вершины v,u для которых нужно найти такую вершину k, что k-предок вершин v и u, и k имеет максимальную глубину из всех таких вершин.
Алгоритм позволяет найти ответы для дерева из n вершин и m запросов за время О<tex>\mathrm{O(n + m)}</tex>, т.е при достаточно большом m, за <tex>\mathrm{O(1)}</tex> на запрос.
== Алгоритм ==
Запустим обход в глубину из корня в течении которого мы найдём все ответы на наши запросы.Ответ для вершин v,u находится, когда мы уже посетели вершины u, а в v обработали всех сыновей и собираемся выйти из неё.
Она состоит из нескольких оценок.
Во-первых dfs работает О(n).
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных n затрачивают <tex>\mathrm{O(n) }</tex> операций. В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных n выполняется за <tex>\mathrm{O(1)}</tex>. Итоговая асимптотика получается <tex>\mathrm{O(n+m)}</tex>, но при достаточно больших m ответ за <tex>\mathrm{O(1) }</tex> на один запрос.
