Lowest Common Ancestor

트리의 두 노드 a, b의 공통된 조상 중 가장 낮은 노드를 찾는 문제.

가장 생각하기 쉬운 방법은 루트까지 올라가는 길에 있는 노드 중 가장 낮은 것을 찾는 방식이다. 그런데 O(n) 시간이 걸리기 때문에, LCA를 여러 번 구해야 할 때 이 방식은 너무 느리다.

Slow Algorithm

  • Do DFS of BFS from a
  • Takes O(n) time

이 방법 역시 여전히 느림.

Fast Algorithm

  • Preprocessing
    • Each node stores the ID of the ancestor up 2^j levels from itself
    • That is, A[i][j] stores the ID of the ancestor up 2^j levels from node i
    • Range of j will be from 0 to log n
    • Time: O(nlogn)
  • How to calculate?
    • A[i][0] is the ID of the parent
    • A[i][j+1] = A[A[i][j]][j] 1

모든 노드가 log n개의 노드를 갖고 있으므로 계산해야 하는 값들의 전체 개수는 nlogn이고, 실제로 O(nlogn) 시간에 이 값들을 다 계산할 수 있다.

Find LCA

  • Nodes a and b –> Lowest Common Ancestor x
  • Let a be the node at lower level
  • Rise from a to the same level as b
    • eg) Let 01000110(2) be the difference of levels of a and b
    • Bits are numbered from right to left, starting at 0
    • From left to right, if bit j is 1, then jump up to A[i][j] where i is the current node, initially i=a

구하는 두 정점의 높이를 동등하게 맞춰준 다음에 동시에 조상을 탐색하면 된다.

2

From the same level, reach LCA

  • Let a' be the node at the same level as b
  • Initially p=a' and q=b
  • From left to right, jump up to A[p][j] and A[q][j] if A[p][j] != A[q][j]
  • Time: O(logn) per query

Reference