이진 트리란 무엇인가?
이진 트리(Binary Tree)는 트리를 구성하는 모든 노드가 최대 두 개까지의 자식 노드만 가질 수 있는 특수한 형태의 트리입니다. 이 자식 노드들은 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)이라고 부릅니다.
간단한 이진 트리의 예는 다음과 같습니다.
이진 탐색 트리(BST)란?
이진 탐색 트리(Binary Search Tree, BST)는 다음과 같은 규칙을 따르는 특수한 트리입니다.
왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작습니다.
오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 큽니다.
트리의 모든 노드는 개별적으로도 위 조건을 만족하는 이진 탐색 트리를 이룹니다.
이진 탐색 트리(BST)의 예는 다음과 같습니다.
이진 탐색 트리는 탐색(search)이나 최솟값·최댓값 찾기 같은 연산의 시간 복잡도를 줄이기 위해 고안된 자료구조입니다.
이번 문제에서는 하나의 이진 트리가 주어지며, 이 이진 트리(BT)를 이진 탐색 트리(BST)로 변환해야 합니다. 중요한 점은 변환 과정에서 원본 이진 트리의 구조(노드 간 연결 관계)는 그대로 유지하고, 노드에 저장된 값만 재배치한다는 것입니다.
그럼 예제를 통해 이진 트리를 BST로 변환하는 과정을 살펴보겠습니다.
입력
출력
변환 알고리즘: 3단계
이진 트리를 이진 탐색 트리로 변환하는 작업은 다음 세 단계로 이루어집니다.
1단계 — 이진 트리를 중위 순회(inorder traversal)하면서 데이터를 순서대로 배열 arr[]에 저장합니다.
2단계 — 어떤 정렬 기법이든 활용하여 배열 arr[]을 오름차순으로 정렬합니다.
3단계 — 트리를 다시 한 번 중위 순회하면서 배열의 요소를 트리 노드에 하나씩 차례로 복사합니다.
이 방법이 동작하는 이유
핵심은 '이진 탐색 트리를 중위 순회하면 항상 오름차순으로 정렬된 값이 얻어진다'는 성질입니다. 따라서 중위 순회로 얻은 값을 정렬한 뒤, 다시 중위 순회 순서대로 트리에 채워 넣으면 트리의 구조는 그대로 유지되면서 BST의 조건을 만족하게 됩니다.
C++ 구현 예제
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left;
struct node *right;
};
void Inordertraversal(struct node* node, int inorder[], int *index_ptr){
if (node == NULL)
return;
Inordertraversal(node->left, inorder, index_ptr);
inorder[*index_ptr] = node->data;
(*index_ptr)++;
Inordertraversal(node->right, inorder, index_ptr);
}
int countNodes(struct node* root){
if (root == NULL)
return 0;
return countNodes (root->left) +
countNodes (root->right) + 1;
}
int compare (const void * a, const void * b){
return( *(int*)a - *(int*)b );
}
void arrayToBST (int *arr, struct node* root, int *index_ptr){
if (root == NULL)
return;
arrayToBST (arr, root->left, index_ptr);
root->data = arr[*index_ptr];
(*index_ptr)++;
arrayToBST (arr, root->right, index_ptr);
}
struct node* newNode (int data){
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void printInorder (struct node* node){
if (node == NULL)
return;
printInorder (node->left);
printf("%d ", node->data);
printInorder (node->right);
}
int main(){
struct node *root = NULL;
root = newNode(17);
root->left = newNode(14);
root->right = newNode(2);
root->left->left = newNode(11);
root->right->right = newNode(7);
printf("Inorder Traversal of the binary Tree: \n");
printInorder (root);
int n = countNodes(root);
int *arr = new int[n];
int i = 0;
Inordertraversal(root, arr, &i);
qsort(arr, n, sizeof(arr[0]), compare);
i = 0;
arrayToBST (arr, root, &i);
delete [] arr;
printf("\nInorder Traversal of the converted BST: \n");
printInorder (root);
return 0;
}실행 결과
Inorder Traversal of the binary Tree: 11 14 17 2 7 Inorder Traversal of the converted BST: 2 7 11 14 17
시간 복잡도 분석
- 노드 개수 계산: O(n)
- 중위 순회 후 배열 저장: O(n)
- 배열 정렬: O(n log n)
- 정렬된 값을 트리에 다시 채우기: O(n)
따라서 전체 시간 복잡도는 O(n log n)이며, 중위 순회 값을 담아 두기 위해 O(n)의 추가 공간이 필요합니다.