Randomized Algorithm - Lowest Common Ancestor

Lowest Common Ancestor

• LCA
• 노드 a와 b의 공통 조상중 제일 최소 찾기.
• logn

모든 노드가 자신의 부모, 조상, … 을 전부다 가지게 하자.
A[i][j] 를 계산하면 된다.
A[i][j] : 노드 i에서 위로 2^j 만큼 올라간 노드의 번호.
즉, A[i][0] 은 노드 i의 부모이다.

만약 A[i][j] = k가 있다고 가정하면
A[i][j+1] = A[k][j] 이다.
(직접 그려서 확인해보면 맞다는 걸 알 수 있다.)

A 배열의 크기가 i는 1~n 이고, j는 0~logn 이므로 전체 배열의 값을 작성하는데 nlogn이 걸린다.
⇒ 모든 조상노드를 자유롭게 순회할 수 있다.

이후 LCA를 구한다.
만약 a가 b보다 위에 존재한다면 a의 링크를 따라서 b와 같은 레벨의 a’을 찾는다.
이후 a’과 b의 조상을 동시에 따라가본다.
즉, A[a’][j] 와 A[b][j] 를 비교한다.
둘이 다르면 그 조상으로 점프한 뒤 다시 비교한다.

일치하는 조상이 나올 때까지 반복하면 된다.
최악의 경우 트리의 높이(logn)만큼 해야 한다.

따라서 전체 알고리즘 시간복잡도는 nlogn + logn ⇒ O(nlogn)

세그먼트 트리 변형 n + 1 = O(n)

LCA 를 응용하여 All-pairs Shortest Path를 구할 수도 있다.