LCA(Lowest Common Ancestor)

트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다.

가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만

최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다.

LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.

그림으로 표현하면 다음과 같다.

(자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.)

알고리즘의 절차는 다음과 같다.

1. 두 노드의 depth가 다르다면 depth를 맞춰준다.

* 이때 일일히 모든 부모노드를 방문하는 것이 아니라, 2^i에 대한 높이의 정보를 이용하면 신속하게 동일한 depth를 가지는 곳으로 이동 할 수 있다.

코드는 다음과 같다.

int adjustDepth(int *a, int *b) { int *up, stay; int ret = 0; int len; if (depth[*a] >= depth[*b]) up = a, stay = *b; else up = b, stay = *a; while (depth[*up] != depth[stay]) { len = 0; while (depth[*up] - (1 << len) >= depth[stay]) len++; len--; ret += (1 << len); *up = parent[*up][len]; }

2. 가장 높은 조상부터 찾도록 하고 두 노드간의 공통조상이 다른 경우에는 그 위치부터 다시 조상을 찾도록 한다.

int i; if (a == b) return a; for (i = K; i>=0; i--) { if (parent[a][i]!=0 && parent[a][i] != parent[b][i]) return LCA(parent[a][i], parent[b][i], i); } return parent[a][0]; }

두 노드가 동일하거나, 두 노드의 공통조상이 모두 동일하다면 가장 낮은 조상을 return한다.

여기서 왜 공통조상이 아닐 때 재귀함수를 부르는지 이해가 가지 않았었다. 그래서 아예 가장 낮은 높이부터 조상들을 비교해 동일한 조상이 나오면 return하도록 했는데 이런경우 문제점은 공통 조상은 찾아주는데 최저 공통조상은 찾아줄 수 없다(높이 자체가 2의 지수 형태로 되어 있기 때문). 이때 찾는 공통 조상은 현재 위치에서 2의 지수 높이에 있는 공통 조상중 가장 낮은 위치에 있는 공통조상을 찾아주게된다.

동일한 level을 맞춰주기 위해 2^i의 형태로 이동했던 것 처럼 위 경우에도 가장 낮은 부분 부터 하나씩 올라가야 한다.

LCA 알고리즘의 가장 키 포인트는

2의 지수승에 해당하는 자료구조를 만들 때 최적화 효과를 볼 수 있다는것.

이런 아이디어는 LCA뿐만 아니라 다른 형태의 문제를 풀 때도 유용하게 사용 할 수 있을 것 같다.