[알고리즘] LCA

LCA알고리즘

LCA는 Lowest Common Ancestor의 약자로 번역하면 최소 공통 조상이라는 뜻이다.

트리구조에서 임의의 두 점이 갖게되는 가장 가까운 조상을 찾는 알고리즘이다.

 

우선 최소 공통 조상에 대해서 알아보면

위와 같은 트리가 있다고 했을 때 

6번 노드와 9번 노드의 최소 공통 조상은 1이고

11번 노드와 14번 노드의 최소 공통 조상은 6이다.

4번 노드와 8번 노드의 최소 공통 조상은 4이다.

 

이렇게 각각 정점에서 출발해서 하나씩 부모노드로 올라가면서 가장 처음 만나는 정점을 찾으면

그 점이 최소 공통 조상이다.

 

그런데 이 방식은 문제점이 있다.

이처럼 9번과 12번의 최소 공통 조상을 찾으면

이처럼 레벨이 다른 두 정점을 기준으로 탐색했을 때 노드를 하나씩 올라가면서

탐색하면 잘못된 정점을 찾게된다.

 

따라서 탐색을 진행하기전 레벨을 같게 만들어주는 작업이 필요하다.

12번 노드를 부모노드인 8번노드, 또 그 부모노드인 4번노드로 탐색을 진행하면 

4번과 9번 노드가 레벨이 같아지므로 한 단계씩 올라가며 조상노드를 찾는 것이 가능해진다.

 

[ 알고리즘과 문법을 공부한 내용을 정리해보는 공간입니다. 부족한 부분이나 잘못된 부분 지적해주시면 감사하겠습니다.]