Наименьший общий предок

Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor.

Алгоритмы

Самый простой, наивный алгоритм для нахождения наименьшего общего предка — вычислить глубину вершин u и v и постепенно подниматься из каждой вершины вверх по дереву, пока не будет найдена общая вершина:

Процедура LCA(u, v):
    h1 := depth(u)          // depth(x) = глубина вершины x
    h2 := depth(v)
  
    while h1 ≠ h2:
       if h1 > h2:
          u := parent(u)
          h1 := h1 - 1
       else:
          v := parent(v)
          h2 := h2 - 1
  
    while u ≠ v:
       u := parent(u)       // parent(x) = непосредственный предок вершины x
       v := parent(v)
  
    return u

Время работы этого алгоритма составляет O(h), где h — высота дерева. Кроме того, может понадобиться препроцессинг, требующий O(n) времени, для нахождения непосредственного предка для всех вершин дерева (но, как правило, эта структура на дереве уже имеется).

Однако, есть более быстрые алгоритмы:

• Алгоритм двоичного подъема, требующий O(n log n) времени на препроцессинг и O(log n) времени на запрос (вычисление наименьшего общего предка двух вершин). Идея заключается в том, чтобы вычислить для каждой вершины предка, удалённого от неё на расстояние 2^k для всех k, и использовать эту информацию для ускорения наивного алгоритма, приведённого выше.
• Алгоритм Тарьяна за время O(n α(n) + m), где m — число запросов. Однако это так называемый offline-алгоритм: он требует, чтобы все запросы были доступны заранее, до начала работы.
• Алгоритм Бендера — Фараха-Колтона, требующий O(n) времени на препроцессинг и O(1) времени на запрос.

Литература

• Bender M., Farach-Colton M. The LCA problem revisited // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. — Springer-Verlag, 2000. — Vol. 1776. — P. 88-94. — doi:10.1007/10719839_9.

Ссылки

• Реализация алгоритма Бендера — Фараха-Колтона от Дэвида Эпштейна