이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조로, 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분됩니다. 이 글에서는 C++을 사용하여 이진 탐색 트리에서 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 방법을 알아보겠습니다.
알고리즘 개요
이진 탐색 트리의 핵심 성질을 활용하면 LCA를 효율적으로 찾을 수 있습니다. BST에서는 루트를 기준으로 왼쪽 서브트리의 모든 값은 루트보다 작고, 오른쪽 서브트리의 모든 값은 루트보다 큽니다.
알고리즘의 동작 순서는 다음과 같습니다.
- 데이터(d), 왼쪽 자식 포인터(l), 오른쪽 자식 포인터(r)를 가지는 구조체 n을 선언합니다.
- 새로운 노드를 생성하는 newnode 함수를 만듭니다.
- LCA() 함수를 호출하여 두 노드 n1과 n2의 최소 공통 조상을 찾습니다. 이때 두 노드가 트리에 존재한다고 가정합니다.
- 루트가 NULL이면 NULL을 반환합니다.
- 루트가 NULL이 아니라면 다음 두 가지 경우를 확인합니다.
- n1과 n2가 모두 루트의 값보다 작으면 → LCA는 왼쪽 서브트리에 있습니다.
- n1과 n2가 모두 루트의 값보다 크면 → LCA는 오른쪽 서브트리에 있습니다.
- 위 두 경우에 해당하지 않으면 현재 루트가 곧 LCA입니다.
예제 코드
#include<iostream>
using namespace std;
struct n {
int d;
struct n* l, *r;
}*p = NULL;
struct n* newnode(int d) {
p = new n;
p->d = d;
p->l = p->r = NULL;
return(p);
}
struct n *LCA(struct n* root, int n1, int n2) {
if (root == NULL)
return NULL;
if (root->d > n1 && root->d > n2)
return LCA(root->l, n1, n2);
if (root->d < n1 && root->d < n2)
return LCA(root->r, n1, n2);
return root;
}
int main() {
n* root = newnode(9);
root->l = newnode(7);
root->r = newnode(10);
root->l->l = newnode(6);
root->r->l = newnode(8);
root->r->r = newnode(19);
root->r->l->r = newnode(4);
root->r->r->r = newnode(20);
int n1 = 20, n2 = 4;
struct n *t = LCA(root, n1, n2);
cout<<"20과 4의 최소 공통 조상: " <<t->d<<endl;
n1 = 7, n2 = 6;
t = LCA(root, n1, n2);
cout<<"7과 6의 최소 공통 조상: " << t->d<<endl;
}실행 결과
20과 4의 최소 공통 조상: 9 7과 6의 최소 공통 조상: 7
동작 원리 설명
첫 번째 예시: 20과 4의 LCA
루트 값이 9입니다. 20은 9보다 크지만 4는 9보다 작으므로, 두 노드는 서로 다른 방향의 서브트리에 위치합니다. 따라서 재귀 호출 없이 즉시 루트인 9가 LCA로 반환됩니다.
두 번째 예시: 7과 6의 LCA
루트 값이 9이고, 7과 6은 모두 9보다 작습니다. 따라서 왼쪽 서브트리로 이동합니다. 왼쪽 자식 노드의 값이 7인데, 여기서 6은 7보다 작고 7은 자기 자신이므로 두 값이 갈라지는 지점이 바로 이 노드입니다. 결과적으로 7이 LCA가 됩니다.
시간 복잡도
이 알고리즘은 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, 균형 잡힌 BST 기준으로 시간 복잡도는 O(h)입니다(h는 트리의 높이). 일반적인 BST에서는 최악의 경우 O(n)까지 늘어날 수 있으며, 공간 복잡도는 재귀 호출 스택에 의해 O(h)입니다.