이 글에서는 C++을 사용하여 데카르트 트리(Cartesian Tree)를 구현하는 방법을 단계별로 살펴봅니다. 데카르트 트리는 각 노드가 배열의 한 원소에 대응하며, 최소 힙 속성(부모 노드가 자식 노드보다 작은 값)과 중위 순회 시 원래 배열 순서가 그대로 유지된다는 두 가지 특징을 동시에 만족하는 이진 트리입니다.
데카르트 트리의 핵심 개념
데카르트 트리가 되려면 다음 두 조건을 만족해야 합니다.
- 힙 속성: 모든 부모 노드의 값은 자식 노드의 값보다 작습니다(최소 힙 기준).
- 순서 속성: 트리를 중위 순회(inorder traversal)하면 원본 배열과 동일한 순서로 원소가 출력됩니다.
배열로부터 데카르트 트리를 만드는 가장 직관적인 방법은 분할 정복(Divide and Conquer) 기법입니다. 현재 구간에서 최솟값을 찾아 루트로 삼고, 그 왼쪽 부분 배열로는 왼쪽 서브트리를, 오른쪽 부분 배열로는 오른쪽 서브트리를 재귀적으로 생성하면 됩니다.
알고리즘
Begin
CarTree 클래스에 함수 선언:
min() = 배열에서 최솟값의 인덱스를 찾는 함수:
if (arr[i] < min)
min = arr[i]
minind = i
inorder() = 트리의 중위 순회 수행:
트리가 비어 있으면
반환
inorder(node->l)
루트 값 출력 (node->d)
inorder(node->r)
End예제 코드
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct nod // 노드 선언 {
int d;
struct nod* l;
struct nod* r;
};
class CarTree {
public:// 함수 선언
nod *newNode (int);
int min(int [], int, int);
nod *buildTree (int [], int, int);
void inorder (nod* node);
void show(nod *, int);
CarTree()
{}
};
int CarTree::min(int arr[], int s, int e) {
int i, min = arr[s], minind = s;
for (i = s + 1; i <= e; i++) {
if (arr[i] < min) {
min = arr[i];
minind = i;
}
}
return minind;
}
nod *CarTree::buildTree (int inorder[], int s, int e)// 데카르트 트리 생성 {
if (s >e)
return NULL;
int i = min(inorder, s, e);
nod *r = newNode(inorder[i]);
if (s == e)
return r;
r->l = buildTree(inorder, s, i - 1);// 왼쪽 자식을 위해 함수 재귀 호출
r->r = buildTree(inorder, i + 1, e);// 오른쪽 자식을 위해 함수 재귀 호출
return r;
}
void CarTree::inorder (struct nod* node) {
if (node == NULL)
return;
inorder (node->l);
cout<<node->d<<" ";
inorder (node->r);
}
void CarTree::show(nod *ptr, int level)// 트리 구조 출력 {
int i;
if(ptr == NULL)
return;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout<<endl;
for (i = 0;i < level;i++)
cout<<" ";
cout<<ptr->d;
show(ptr->l, level + 1);
}
}
nod *CarTree::newNode (int d)// 새 노드 생성 {
nod* t = new nod;
t->d = d;
t->l = NULL;
t->r = NULL;
return t;
}
int main() {
CarTree ct;
int i, n;
cout<<"삽입할 원소의 개수를 입력하세요: ";
cin>>n;
int a[n];
for (i = 0; i < n; i++) {
cout<<"원소 "<<i + 1<<" : ";
cin>>a[i];
}
nod *r = ct.buildTree(a, 0, n - 1);
cout<<"데카르트 트리 구조: "<<endl;
ct.show(r,1);
cout<<endl;
cout<<"\n 트리의 중위 순회 \n"<<endl;
ct.inorder(r);
cout<<endl;
return 0;
}실행 결과
삽입할 원소의 개수를 입력하세요: 10 원소 1 : 10 원소 2 : 30 원소 3 : 20 원소 4 : 40 원소 5 : 50 원소 6 : 70 원소 7 : 60 원소 8 : 80 원소 9 : 100 원소 10 : 112 데카르트 트리 구조: 112 100 80 60 70 50 40 20 30 10 트리의 중위 순회 10 30 20 40 50 70 60 80 100 112
주요 함수 설명
- min(): 주어진 구간 [s, e]에서 최솟값이 위치한 인덱스를 반환합니다. 데카르트 트리의 루트 후보를 찾는 핵심 역할을 담당합니다.
- buildTree(): 구간의 최솟값으로 루트 노드를 생성한 뒤, 왼쪽 구간과 오른쪽 구간에 대해 각각 재귀 호출을 수행하여 서브트리를 구성합니다.
- inorder(): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 순회하여 원래 배열과 동일한 순서로 값을 출력합니다.
- show(): 트리의 계층 구조를 들여쓰기 형태로 시각화하여 전체 모양을 한눈에 파악할 수 있게 해 줍니다.
시간 복잡도
이 구현 방식은 매 단계마다 구간 내 최솟값을 선형 탐색으로 찾기 때문에, 평균적으로 O(n log n), 최악의 경우(정렬된 배열 입력 등)에는 O(n²)의 시간 복잡도를 가집니다. 더 빠른 성능이 필요하다면 스택을 활용한 O(n) 선형 시간 알고리즘을 고려할 수 있습니다.