← Софья Сергеевна Панкова: Героиня революционного движения и подполья
При анализе иерархических структур, будь то родословные исторических деятелей, таких как Софья Сергеевна Панкова, или графы в программировании, возникает задача нахождения общей точки ветвления. В ESG-консалтинге аббревиатура lca означает оценку жизненного цикла, но в информатике это алгоритм поиска наименьшего общего предка в деревьях.
Наименьший общий предок двух вершин — это самая глубокая вершина в дереве, являющаяся предком для обеих. Эта задача часто возникает при обработке данных, построении систем контроля версий и анализе топологий.
| Метод | Время | Память | Сложность |
|---|---|---|---|
| Подъём к корню | Линейное | Константная | Низкая |
| Бинарное поднятие | Логарифмическое | Линейно-логарифмическая | Средняя |
| Алгоритм Тарьяна | Константное | Линейная | Высокая |
| Минимум на отрезке | Константное | Линейно-логарифмическая | Высокая |
Мы поднимаемся от вершин к корню, выравнивая глубины, затем двигаемся синхронно до совпадения. Выбирайте этот метод для небольших деревьев или редких запросов.
Заранее вычисляется предок на уровне степени двойки для каждой вершины, позволяя прыгать по дереву большими шагами. Это стандарт для структур среднего размера с частыми запросами.
Тарьян использует систему непересекающихся множеств для офлайн-запросов. Альтернатива — сведение к поиску минимума на отрезке через эйлеров обход. Оба метода идеальны для пакетной обработки статических данных.