선순회 결과로 BST 구성하기
선순회(preorder traversal) 결과가 하나 주어졌다고 가정해 보겠습니다. 이 순회 결과만으로 원래의 이진 탐색 트리(Binary Search Tree, BST)를 복원해야 합니다. 예를 들어 순회 결과가 [10, 5, 1, 7, 40, 50]과 같다면, 구성되는 트리는 다음과 같은 형태가 됩니다.
접근 방법: 스택 활용
선순회의 첫 번째 값은 항상 트리의 루트라는 성질을 이용하면, 스택(stack)을 사용해 O(n) 시간 복잡도로 트리를 구성할 수 있습니다. 알고리즘은 다음과 같습니다.
빈 스택을 하나 생성합니다.
첫 번째 값을 루트 노드로 만들고, 이를 스택에 push합니다.
스택이 비어 있지 않고 다음 값이 스택 최상단(top) 요소보다 큰 동안 계속 pop을 수행합니다. 반복이 끝나면 마지막으로 pop된 노드의 오른쪽 자식으로 새 노드를 연결하고, 새 노드를 스택에 push합니다.
다음 값이 스택 최상단 요소보다 작다면, 최상단 요소의 왼쪽 자식으로 새 노드를 연결한 뒤 새 노드를 스택에 push합니다.
선순회 배열의 모든 요소를 처리할 때까지 위 과정을 반복합니다.
핵심 아이디어는 다음과 같습니다. 값이 작아지는 동안에는 왼쪽 자식으로 내려가고, 더 큰 값이 나타나면 스택에 쌓아둔 조상 노드들을 되돌아가며(pop) 오른쪽 자식이 될 위치를 찾는 것입니다. 이 덕분에 각 노드는 정확히 한 번씩 push되고 pop됩니다.
C++ 구현 예제
#include <iostream>
#include <stack>
using namespace std;
class node {
public:
int data;
node *left;
node *right;
};
node* getNode (int data) {
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
node* constructTree ( int pre[], int size ) {
stack<node*> stk;
node* root = getNode( pre[0] );
stk.push(root);
int i;
node* temp;
for ( i = 1; i < size; ++i ) {
temp = NULL;
while ( !stk.empty() && pre[i] > stk.top()->data ) {
temp = stk.top();
stk.pop();
}
if ( temp != NULL) {
temp->right = getNode( pre[i] );
stk.push(temp->right);
} else {
node* peek_node = stk.top();
peek_node->left = getNode( pre[i] );
stk.push(stk.top()->left);
}
}
return root;
}
void inord (node* node) {
if (node == NULL)
return;
inord(node->left);
cout << node->data << " ";
inord(node->right);
}
int main () {
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
node *root = constructTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
}
실행 결과
Inorder traversal: 1 5 7 10 40 50
중위 순회(inorder traversal) 결과가 오름차순으로 정렬되어 출력되므로, 트리가 올바른 이진 탐색 트리로 구성되었음을 확인할 수 있습니다.
복잡도 분석
시간 복잡도: O(n) — 각 노드가 정확히 한 번 push되고 한 번 pop됩니다.
공간 복잡도: O(n) — 최악의 경우(오른쪽으로 치우친 트리) 스택에 모든 노드가 저장될 수 있습니다.