이 글에서는 C++를 사용하여 이진 탐색 트리(Binary Search Tree, BST)를 최소 힙(min heap)으로 변환하는 프로그램을 다룹니다.
이진 탐색 트리가 하나 주어졌을 때, 목표는 해당 트리를 최소 힙으로 변환하는 것입니다. 단, 변환된 트리도 원본과 동일한 원소 집합을 가져야 하며, 원소들을 비교할 때 이진 탐색 트리의 정렬 조건이 그대로 유지되어야 합니다. 즉, 결과 트리를 중위 순회(inorder traversal)하면 여전히 오름차순으로 정렬된 값이 출력되어야 합니다.
문제 해결 접근 방식
이 문제는 두 단계의 트리 순회를 조합하여 해결할 수 있습니다.
- 중위 순회로 정렬된 배열 생성: BST의 가장 큰 특징은 중위 순회(왼쪽 → 루트 → 오른쪽)를 수행하면 노드 값이 오름차순으로 정렬된다는 점입니다. 이 성질을 이용해 트리의 모든 값을 정렬된 배열에 저장합니다.
- 전위 순회 순서로 값 재배치: 정렬된 배열의 값을 트리에 전위 순회(preorder traversal, 루트 → 왼쪽 → 오른쪽) 순서대로 다시 채워 넣습니다.
전위 순회에서는 항상 부모 노드가 자식 노드보다 먼저 방문되기 때문에, 부모에게 더 작은 값이 먼저 할당됩니다. 그 결과 모든 부모 노드가 자식 노드보다 작거나 같은 값을 갖게 되어 최소 힙의 성질이 자연스럽게 만족됩니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// BST의 노드 구조체
struct Node {
int data;
Node *left, *right;
};
// 새로운 노드 생성
struct Node* getNode(int data) {
struct Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 전위 순회 선언
void preorderTraversal(Node*);
// 중위 순회를 통해 값을 정렬된 상태로 저장
void inorderTraversal(Node *root, vector<int>& arr) {
if (root == NULL)
return;
inorderTraversal(root->left, arr);
arr.push_back(root->data);
inorderTraversal(root->right, arr);
}
// BST를 최소 힙 구조로 변환
void convert_BSPheap(Node *root, vector<int> arr, int *i) {
if (root == NULL)
return;
// 전위 순회 순서대로 정렬된 값을 할당
root->data = arr[++*i];
convert_BSPheap(root->left, arr, i);
convert_BSPheap(root->right, arr, i);
}
// 최소 힙으로 변환하는 메인 함수
void convert_minheap(Node *root) {
// 노드의 값을 저장할 벡터
vector<int> arr;
int i = -1;
// 중위 순회로 정렬된 값 수집 후 재배치
inorderTraversal(root, arr);
convert_BSPheap(root, arr, &i);
}
// 전위 순회 수행 및 출력
void preorderTraversal(Node *root) {
if (!root)
return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
struct Node *root = getNode(4);
root->left = getNode(2);
root->right = getNode(6);
root->left->left = getNode(1);
root->left->right = getNode(3);
root->right->left = getNode(5);
root->right->right = getNode(7);
convert_minheap(root);
cout << "Preorder Traversal:" << endl;
preorderTraversal(root);
return 0;
}실행 결과
Preorder Traversal: 1 2 3 4 5 6 7
출력 결과를 보면 전위 순회 시 값이 1부터 7까지 오름차순으로 나타납니다. 전위 순회에서 값이 정렬된 순서로 배치되었다는 것은 모든 부모 노드가 자식 노드보다 작거나 같은 값을 가진다는 의미이므로, 트리가 성공적으로 최소 힙으로 변환되었음을 확인할 수 있습니다.
복잡도 분석
- 시간 복잡도: 중위 순회와 값 재배치 과정이 각각 트리의 모든 노드를 한 번씩 방문하므로 전체 시간 복잡도는 O(n)입니다.
- 공간 복잡도: 정렬된 값을 저장하기 위한 벡터에 O(n)의 추가 공간이 필요합니다.