최소 공통 조상 찾기(Lowest Common Ancestor)

최소 공통 조상 찾기(LCA)

 

LCA란?

 

 - 트리에서 두 노드 u, v가 가지는 최소 공통 조상을 찾는 알고리즘

 

 - 최소 공통 조상을 이용하여 해당 정점들 간의 최단 거리를 빠르게 계산할 수 있다.

 

 

---

 

LCA 동작 방식

 

 - 0. 각 정점마다 부모의 정보를 가진 배열, 정점의 높이를 저장한 배열을 만든다.

 

 - 1. 두 정점 u, v의 높이 Hu, Hv를 구한다. 

 

 - 2. 두 정점의 높이가 다르다면 더 큰 높이의 정점은 현재 정점을 부모의 정점으로 변경하여 높이를 낮춘다.

      이 과정을 높이가 같아질 때 까지 반복한다.

 

 - 3. 정점들의 높이가 같아지면, 하나씩 부모로 이동하며 같은 원소가 나오는지 판단한다.

      이 과정을 같은 정점이 될 때 까지 반복한다.

 

 - 4. 3번까지의 과정을 통해 얻은 정점이 두 정점 u, v의 최소 공통 조상이 된다.

 

 

1. 기본 트리

 

2. 두 노드 7, 6의 공통 조상을 찾는다. 두 노드의 높이가 다르기 때문에 이동이 필요.

3. 노드 7의 높이를 노드 6의 높이와 맞추기 위해 이동.

4. 높이가 같기 때문에 둘 다 부모를 방문한다.

5. 부모를 하나씩 올라가며 같은 노드가 나오면 그 노드가 LCA이다.

 

 

---

 

 

LCA 개선

 

 - LCA는 기본적으로 노드는 자신의 부모만 알고 있다.

 

 - 트리가 편향되어 있다면, 미리 부모를 저장해 둔 의미가 없어진다.

 

 - 노드의 부모뿐만 아니라, 그 위의 조상들도 미리 저장하여 바로 찾을 수 있게 개선할 수 있다.

 

 - 모든 조상을 저장하는 것이 아닌, $2^i$ 번쨰 노드만 저장한다.

 

 

 

[ 추가 예정 ]