Наименьший общий предок ( нижайший общий предок ) вершин 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. // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. — Springer-Verlag, 2000. — Vol. 1776. — P. 88-94. — doi : .

Ссылки

• от