Наименьший общий предок
Также: Lowest common ancestor · LCA · двоичный подъём · binary lifting · jump pointers · офлайн-алгоритм Тарьяна · Tarjan's off-line LCA · least common ancestor
Самая глубокая вершина дерева, которая лежит над обеими данными. Найти её можно, поднимаясь по одному шагу, но на глубоких деревьях это долго. Двоичный подъём прыгает вверх на 1, 2, 4, 8… шагов и отвечает за O(log n); обход Эйлера с разреженной таблицей — за O(1); офлайн-алгоритм Тарьяна отвечает на все вопросы разом.
Кто человеку родственнее — мышь или корова? Ответ лежит в дереве: у каждой пары видов есть самая глубокая общая ветвь, от которой их линии разошлись, и чем она глубже, тем ближе родство. Ниже — дерево жизни из таксономии NCBI: все 5931 вид млекопитающих с их предками и дюжина ориентиров из остальной жизни, 7865 вершин. Выберите пару — дерево покажет общего предка.
У человека и мыши общий предок — эуархонтоглиры, глубина 21. У человека и коровы — бореоэутерии, глубина 20, на ступень выше. Мышь человеку родственнее, хотя по дереву до обеих ровно 18 шагов. Кит ближе к корове, чем к лошади: общий предок кита и коровы — китопарнокопытные, кита и лошади — лавразиатерии. Латимерия ближе к человеку, чем к рыбке данио, а пекарские дрожжи — ближе к человеку, чем к любому растению: их общий предок с нами — заднежгутиковые, а с резуховидкой — только эукариоты.
Идея
Наименьший общий предок двух вершин корневого дерева — самая глубокая вершина, которая лежит на путях от корня к обеим. Вершина считается предком самой себя, так что общий предок вершины и её потомка — она сама. Определение и первое применение — в статье о разреженной таблице; здесь — как его искать.
Самое простое: поднять более глубокую вершину на уровень другой, а потом поднимать обе по шагу, пока не совпадут. Это O(h) на вопрос, где h — высота дерева. Для дерева жизни h = 38, и наивный подъём отвечает почти мгновенно. Но деревья бывают глубокими: цепочка коммитов, дерево разбора длинного выражения, дерево рекурсии. На пути длиной миллион каждый вопрос стоит миллион шагов.
Запомним для каждой вершины не только родителя, но и предков на 2, 4, 8, … шагов выше: up[k][v] — предок на 2k шагов. Таблицу легко заполнить: прыжок на 2k — два прыжка на 2k−1. Любое расстояние вверх — сумма степеней двойки, по прыжку на каждый единичный бит. Чтобы найти общего предка, поднимем глубокую вершину до уровня другой, а потом будем пробовать прыжки от самых длинных к коротким и прыгать обеими, только если они попадают в разные вершины. Так обе остановятся прямо под общим предком.
Этот приём называют двоичным подъёмом. В научных работах ту же таблицу называют указателями-прыжками, jump pointers.
Как это работает по шагам
Две цепочки предков — человека и дрозофилы — от «клеточных организмов». Общая часть идёт по середине, дальше цепочки расходятся. Человек на глубине 30, дрозофила на 38.
Разница глубин — 8, в двоичной записи 1000, и дрозофила прыгает один раз, сразу на 8 ступеней. Теперь обе на глубине 30. Прыжок на 32 увёл бы обеих выше корня — там один и тот же корень, и такой прыжок отвергается. Прыжок на 16 приводит в разные вершины — значит, общий предок выше, прыгаем. Ещё раз 8 — снова разные, прыгаем. Прыжки на 4, 2 и 1 приводят в одну и ту же вершину: это общий предок, но, может быть, не самый низкий, поэтому не прыгаем. В конце обе вершины стоят на глубине 6, и над ними один и тот же родитель — двусторонне-симметричные, глубина 5. Три прыжка и семь проверок вместо 58 шагов по одному.
Почему прыжки находят именно его
Пусть вершины a и b на одной глубине и различны, и c — их наименьший общий предок. Если перебрать k от большего к меньшему и прыгать обеими на 2k, когда up[k][a] ≠ up[k][b], то в конце a и b окажутся детьми c.
Пусть d — расстояние от a до c; до ребёнка c над a тогда d − 1 шагов. Предки a и b на одном и том же расстоянии s совпадают ровно тогда, когда s ≥ d: выше c пути общие, ниже — разные, иначе c не был бы наименьшим. Значит, прыжок на 2k разрешён, когда он не длиннее, чем осталось до ребёнка c. Перебор от больших k к меньшим — это запись числа d − 1 в двоичной системе, разряд за разрядом: прыгаем, если разряд помещается в остаток, иначе пропускаем. После младшего разряда остаток равен нулю, и обе вершины стоят на ребёнке c. Их общий родитель up[0][a] и есть c.
Первая часть — подъём глубокой вершины на разницу глубин — устроена так же: разница раскладывается по битам, и каждый единичный бит — один прыжок. Если после подъёма вершины совпали, одна была предком другой, и ответ — она сама.
Две ловушки
Расстояние — не родство. Число шагов по дереву между двумя видами — сумма глубин минус две глубины общего предка — легко принять за меру родства. На таксономии это неверно: ступени таксономии неравны, у одних ветвей промежуточных рангов много, у других мало. До мыши и до коровы от человека одинаково, по 18 шагов, а мышь ближе. Кит от коровы в 12 шагах, от лошади в 11, а ближе корова. Сравнивать нужно глубину общего предка, а лучше — время расхождения из молекулярных часов, которого в таксономии нет вовсе.
Прыжок выше корня. Таблице нужно куда-то вести прыжок, который выходит за корень. Если записать туда −1, первая же проверка up[k][-1] в Python молча возьмёт последний элемент списка, а в Go упадёт. Проще всего считать корень собственным предком: прыжок выше корня приводит в корень, у обеих вершин он одинаковый, и такой прыжок просто отвергается.
Код
Вершины дерева жизни лежат в прямом порядке обхода: родитель всегда раньше ребёнка. Поэтому глубины и таблица считаются одним проходом по массиву, без всякого поиска в глубину. Уровней таблицы — сколько бит в наибольшей глубине: для глубины 38 это шесть, прыжки на 1, 2, 4, 8, 16 и 32.
Homo sapiens + Mus musculus: Euarchontoglires at depth 21, 18 steps apart Homo sapiens + Bos taurus: Boreoeutheria at depth 20, 18 steps apart Balaenoptera musculus + Bos taurus: Artiodactyla at depth 22, 12 steps apart Balaenoptera musculus + Equus caballus: Laurasiatheria at depth 21, 11 steps apart
Ещё два способа
Обход Эйлера и минимум на отрезке. Обойдём дерево в глубину и будем записывать вершину каждый раз, когда в неё входим или возвращаемся: получится последовательность длины 2n − 1. Между первыми появлениями двух вершин обход проходит через их общего предка и не поднимается выше, поэтому общий предок — самая неглубокая вершина на этом отрезке. Минимум на отрезке неизменного массива разреженная таблица отдаёт за O(1) после подготовки O(n log n). Подробно — в той статье, вместе с задачей об общей папке двух файлов этого сайта.
Офлайн-алгоритм Тарьяна. Если все вопросы известны заранее, их можно задать дереву во время одного обхода. Идём в глубину; когда поиск закрывает вершину, её поддерево вливается в множество родителя системой непересекающихся множеств, а у каждого множества помнится его верхняя ещё открытая вершина. Закрывая вершину v, смотрим на вопросы (v, u), где u уже закрыта: множество u висит как раз на той открытой вершине, где пути к u и к v расходятся, — это и есть ответ.
Ответы те же, что у двоичного подъёма. Почему верхняя открытая вершина множества u — общий предок: открытые вершины в момент закрытия v — это путь от корня к v. Поддерево каждой из них, кроме уже открытых веток, вливалось в неё по мере закрытия, поэтому закрытая u лежит в множестве той открытой вершины, под которой она висит, — самой глубокой из открытых, общей с путём к u.
Сколько это стоит
| Способ | Подготовка | Вопрос | Память | Когда удобен |
|---|---|---|---|---|
| подъём по одному шагу | O(n) | O(h) | O(n) | неглубокие деревья: таксономия, файловая система |
| двоичный подъём | O(n log n) | O(log n) | O(n log n) | вопросы приходят по одному; нужен ещё и предок на k шагов выше |
| обход Эйлера и разреженная таблица | O(n log n) | O(1) | O(n log n) | очень много вопросов по неизменному дереву |
| Тарьян офлайн | O((n + q) α(n)) на всё | O(n + q) | все вопросы известны заранее | |
Замер на глубоких случайных деревьях: каждая вершина висит на одной из трёх предыдущих, высота около n/2, вопросов столько же, сколько вершин. Время включает подготовку.
Подъём по шагу растёт как квадрат: на 10 000 вершин в Python он медленнее остальных в 22–37 раз, на 30 000 в Go — в 13–26 раз. Три быстрых способа идут рядом, и порядок между ними решает не O, а память. На трёхстах тысячах вершин в Go двоичный подъём проигрывает обходу Эйлера почти втрое: его таблица — 18 массивов по 300 000 чисел, и каждый прыжок — обращение в случайное место памяти, мимо кэша. У разреженной таблицы на вопрос всего два обращения.
Где работает
Слияние веток. Git сливает две ветки трёхсторонним слиянием: сравнивает обе с их общим предком. Команда git merge-base ищет лучшего общего предка двух коммитов; по документации git, один общий предок лучше другого, если тот — его предок, а лучший — тот, лучше которого нет. История коммитов — не дерево, а граф без циклов, и лучших общих предков может быть несколько, когда ветки сливали крест-накрест; документация прямо об этом предупреждает.
Документ в браузере. Выделение текста на странице задаётся двумя концами в дереве документа, и браузер отдаёт Range.commonAncestorContainer — самый глубокий узел, содержащий оба конца.
Компиляторы. В простом алгоритме доминаторов Купера, Харви и Кеннеди 2001 года функция intersect поднимает два «пальца» по строящемуся дереву доминаторов, пока они не встретятся, — это наивный поиск общего предка, и на деревьях доминаторов, обычно неглубоких, его хватает.
Деревья жизни. Ближайший общий таксон, общий предок в филогенетическом дереве, расстояние между видами — одни и те же запросы к дереву. А ещё общий предок даёт расстояние в любом дереве: глубина u плюс глубина v минус две глубины их общего предка.
История
Задачу о наименьшем общем предке поставили Альфред Ахо, Джон Хопкрофт и Джеффри Ульман в 1973 году (журнальная версия статьи вышла в 1976-м) и решили её офлайн почти за линейное время. Офлайн-алгоритм на системе непересекающихся множеств описал Роберт Тарьян в 1979 году, в работе о применениях сжатия путей. Ответ на вопрос за O(1) после линейной подготовки получили Дов Харел и Тарьян в 1984 году; их метод упрощали Барух Шибер и Узи Вишкин, а в 2000 году Майкл Бендер и Мартин Фарах-Колтон свели всё к минимуму на отрезке обхода Эйлера — об этом в истории разреженной таблицы. Таблица прыжков на степени двойки — одна из ступеней их же алгоритма для предка на заданном уровне (2004); в олимпиадном программировании она известна как двоичный подъём.
Задачи
В первой задаче нужно пройти по дереву жизни от одного вида к другому и назвать таксон на k-м шаге — двоичный подъём нужен и для общего предка, и для самого шага. Во второй — по линиям между городами найти самый длинный пролёт на пути: та же таблица, только вместе с предком в ней хранится максимум на прыжке.
Экскурсия по дереву жизни Самый длинный пролётДанные: Дерево жизни: таксономия NCBI, выгрузка 16.10.2026