레벨 순서 순회(Level Order Traversal) 결과가 하나 주어졌다고 가정해 보겠습니다. 이 순회 결과만으로 원래의 트리를 복원해야 하는 것이 목표입니다. 예를 들어 순회 결과가 [7, 4, 12, 3, 6, 8, 1, 5, 10]이라면, 최종적으로 만들어지는 트리는 다음과 같은 형태가 됩니다.
접근 방법
이 문제는 재귀적(recursive) 접근 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 첫 번째 요소는 항상 루트(root)가 됩니다.
- 두 번째 요소부터는 기존 BST의 삽입 규칙을 따릅니다. 즉, 값이 현재 노드보다 작거나 같으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 내려가며 빈 자리를 찾아 삽입합니다.
- 이 과정을 모든 요소에 대해 반복하면 레벨 순서 순회와 일치하는 BST가 완성됩니다.
단계별 알고리즘
- 먼저 배열의 첫 번째 요소를 가져와 루트 노드로 만듭니다.
- 그다음 요소를 하나씩 확인합니다. 값이 루트보다 작으면 왼쪽 자식 쪽으로, 크면 오른쪽 자식 쪽으로 배치합니다.
- 나머지 모든 요소에 대해 2번 과정을 재귀적으로 수행하여 BST를 완성합니다.
C++ 구현 코드
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 새로운 값을 BST 규칙에 맞게 재귀적으로 삽입하는 함수
Node *lvlOrd(Node *root, int data) {
if(root == NULL){
root = getNode(data);
return root;
}
if(data <= root->data)
root->left = lvlOrd(root->left, data);
else
root->right = lvlOrd(root->right, data);
return root;
}
// 배열 전체를 순회하며 트리를 구성하는 함수
Node* makeTree(int arr[], int n) {
if(n == 0)
return NULL;
Node *root = NULL;
for(int i = 0; i < n; i++)
root = lvlOrd(root, arr[i]);
return root;
}
// 검증을 위한 중위 순회(Inorder Traversal) 함수
void inord(Node* root) {
if (!root)
return;
inord(root->left);
cout << root->data << " ";
inord(root->right);
}
int main() {
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = sizeof(arr) / sizeof(arr[0]);
Node *root = makeTree(arr, n);
cout << "Inorder Traversal: ";
inord(root);
}실행 결과
Inorder Traversal: 1 3 4 5 6 7 8 10 12
복잡도 분석
각 요소를 삽입할 때 트리의 높이만큼 비교 연산이 발생합니다. 평균적인 경우(균형 잡힌 트리) 시간 복잡도는 O(N log N)이며, 최악의 경우(정렬된 배열처럼 한쪽으로 치우친 트리)에는 O(N²)까지 늘어날 수 있습니다. 공간 복잡도는 재귀 호출 스택 때문에 최대 O(N)입니다.
중위 순회 결과가 오름차순으로 정렬되어 출력되므로, 트리가 올바른 BST로 구성되었음을 손쉽게 검증할 수 있습니다.