[Tech, etc.] Lowest Common Ancestor(LCA, 최소 공통 조상)

GeeksforGeeks에 따르면 Lowest Common Ancestor(LCA)의 정의는 아래와 같다.

: The lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants, where n1 and n2 are the nodes for which we wish to find the LCA. Hence, the LCA of a binary tree with nodes n1 and n2 is the shared ancestor of n1 and n2 that is located farthest from the root. 

: LCA는 트리에서 n1과 n2를 자손(descendants)으로 가지는 가장 낮은 높이의 조상(ancestor) 노드이고, 여기서 n1과 n2는 우리가 찾고자 하는 노드다. 그러므로 이진 트리(binary tree)에서 LCA는 n1과 n2를 자손으로 갖는 조상 중에서 root 노드에서 가장 먼 노드다.

GeeksforGeeks는 두 가지 접근법을 제시하고 있다.

 

 첫 번째 방법은 root에서 n1과 n2까지 도달하는 경로를 각각 저장한 후 이를 비교하는 방법이다. 예를 들어 위 그림에서 n1과 n2를 각각 노드 5와 6으로 가정해보자. root에서 노드 5와 6까지 도달하는 경로는 각각 {1, 2, 5}와 {1, 3, 6}이다. 두 경로를 처음부터 비교해 가장 처음 달라지는 곳(노드 2와 3}을 찾고 그 바로 전에 기록된 노드(노드 1)가 노드 5와 6의 LCA가 된다.

 

 두 번째 방법은 root부터 n1과 n2와 값이 일치하는지 찾아 내려간다. root와 일치하지 않으면 왼쪽과 오른쪽으로 내려가면서 일치하는지 찾는 것을 반복한다. n1과 n2와 일치하는 노드가 왼쪽 하위 트리에 존재한다면 왼쪽 하위 트리가 LCA가 되고, 오른쪽 하위 트리에 존재한다면 LCA는 오른쪽 하위 트리가 된다. 여기서 이용하는 방법은 전위 순회(pre-order traversal)이다. 또한 첫 번째 방법에선 n1과 n2까지 도달하는 경로를 저장해야 되는 자료 구조가 필요한데 반해 두 번째 방법엔 부차적인 저장 공간이 필요하지 않아 첫 번째 방법에 비해 Time Complexity에서 우위를 갖는다.

 

참고

 

- https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/