개요
이 튜토리얼에서는 C++를 사용하여 이진 탐색 트리(BST, Binary Search Tree)를 최대 힙(Max Heap)으로 변환하는 프로그램을 구현해 보겠습니다.
목표는 주어진 이진 탐색 트리의 노드 구조를 그대로 유지한 채, 각 노드의 값이 자식 노드의 값보다 크거나 같아지도록(즉, 최대 힙의 조건을 만족하도록) 데이터만 재배치하는 것입니다. 변환 후에는 어떤 노드든 자신의 모든 자손 노드보다 크거나 같은 값을 가져야 합니다.
접근 방법
가장 효율적인 해결 방법은 두 가지 트리 순회 기법을 조합하는 것입니다.
- 중위 순회(Inorder Traversal): BST를 중위 순회하면 항상 오름차순으로 정렬된 값의 배열을 얻을 수 있습니다. 이 배열을 임시로 저장합니다.
- 후위 순회(Postorder Traversal)로 값 채우기: 저장해 둔 정렬된 배열의 값을 트리에 다시 채워 넣습니다. 후위 순회는 '왼쪽 자식 → 오른쪽 자식 → 부모' 순서로 노드를 방문하므로, 정렬된 값을 이 순서대로 대입하면 루트 노드가 항상 가장 큰 값을 갖게 되고, 결과적으로 최대 힙의 조건이 자연스럽게 충족됩니다.
이 방법의 시간 복잡도는 O(n)이며, 정렬된 값을 저장하기 위해 O(n)의 추가 공간이 필요합니다.
예제 코드
#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 postorderTraversal(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);
}
// 후위 순회하며 배열의 값을 노드에 채워 넣음
void convert_BSTHeap(Node* root, vector<int> arr, int* i){
if (root == NULL)
return;
convert_BSTHeap(root->left, arr, i);
convert_BSTHeap(root->right, arr, i);
// 배열의 값을 노드에 복사
root->data = arr[++*i];
}
// 최대 힙으로 변환하는 함수
void convert_maxheap(Node* root) {
vector<int> arr;
int i = -1;
inorderTraversal(root, arr);
convert_BSTHeap(root, arr, &i);
}
// 후위 순회 결과 출력
void postorderTraversal(Node* root) {
if (!root)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
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_maxheap(root);
cout << "Postorder Traversal:" << endl;
postorderTraversal(root);
return 0;
}실행 결과
Postorder Traversal: 1 2 3 4 5 6 7
동작 원리 상세 설명
입력으로 사용된 BST는 다음과 같습니다.
4
/ \
2 6
/ \ / \
1 3 5 7먼저 중위 순회를 수행하면 정렬된 배열 [1, 2, 3, 4, 5, 6, 7]을 얻습니다. 이후 후위 순회 순서(왼쪽 서브트리 → 오른쪽 서브트리 → 루트)로 이 값들을 차례대로 채워 넣으면, 각 서브트리의 루트가 해당 서브트리 내에서 가장 큰 값을 갖는 트리가 됩니다. 즉, 모든 부모 노드가 자식 노드보다 크거나 같은 최대 힙이 완성됩니다.
변환된 트리의 후위 순회 결과가 정확히 정렬된 순서와 일치하는 것을 확인할 수 있으며, 이는 변환이 올바르게 수행되었음을 의미합니다.