전위 순회(preorder traversal) 결과 하나만 주어졌을 때, 이를 바탕으로 이진 탐색 트리(BST)를 복원하는 방법을 알아보겠습니다. 예를 들어 순회 결과가 [10, 5, 1, 7, 40, 50]이라면 아래 그림과 같은 트리가 완성됩니다.
핵심 아이디어: 노드별 값의 범위(min~max) 설정
이 문제를 해결하는 핵심 기법은 각 노드가 가질 수 있는 값의 범위 {min…max}를 지정하는 것입니다. 알고리즘은 다음 순서로 진행됩니다.
먼저 루트 노드의 범위를 {INT_MIN…INT_MAX}로 초기화합니다. 전위 순회의 첫 번째 값은 반드시 이 범위 안에 속하므로, 해당 값으로 루트 노드를 생성합니다.
왼쪽 서브트리를 구성할 때는 범위를 {INT_MIN…루트 값}으로 좁힙니다. 이후에 등장하는 값이 이 범위에 포함된다면, 그 값은 왼쪽 서브트리의 일부입니다.
오른쪽 서브트리를 구성할 때는 범위를 {루트 값…INT_MAX}로 설정합니다. 마찬가지로 이 범위에 속하는 값은 오른쪽 서브트리에 배치됩니다.
이 과정을 재귀적으로 반복하면 전위 순회 배열의 각 원소를 한 번씩만 확인하면서 O(n) 시간 복잡도로 BST를 완성할 수 있습니다.
C++ 구현 예제
#include <iostream>
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* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) {
if( *preord_index >= size )
return NULL;
node* root = NULL;
if( key > min && key < max ){
root = getNode( key );
*preord_index += 1;
if (*preord_index < size){
root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size );
root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size );
}
}
return root;
}
node *makeTree (int pre[], int size) {
int preord_index = 0;
return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size );
}
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 = makeTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
}출력
Inorder traversal: 1 5 7 10 40 50
중위 순회(inorder) 결과가 1, 5, 7, 10, 40, 50처럼 오름차순으로 정렬되어 출력되는 것을 확인할 수 있습니다. 중위 순회가 정렬된 순서로 나타난다는 것은 트리가 올바른 이진 탐색 트리(BST)로 구성되었음을 의미합니다.