이 튜토리얼에서는 BST(이진 탐색 트리)를 이진 트리로 변환하는 프로그램을 다룹니다. 변환된 트리에서는 각 노드의 키 값에 자신보다 큰 모든 키의 합이 더해지도록 만듭니다.
즉, 하나의 BST가 주어졌을 때, 각 노드의 값을 '현재 노드를 포함하여 자신보다 크거나 같은 모든 노드의 합'으로 변경하는 것이 목표입니다. 이 작업은 주어진 BST를 역중위 순회(reverse inorder)하면서 지나온 노드들의 누적 합을 유지하고, 그 합을 현재 노드에 더하는 방식으로 수행할 수 있습니다.
접근 방법
일반적인 중위 순회가 왼쪽 → 루트 → 오른쪽 순서로 방문한다면, 역중위 순회는 오른쪽 → 루트 → 왼쪽 순서로 방문합니다. BST에서 역중위 순회를 수행하면 노드를 내림차순으로 방문하게 되므로, 순회 도중 누적합을 계속 갱신하면서 현재 노드에 더해주면 원하는 결과를 얻을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// BST의 노드 구조체
struct node{
int key;
struct node* left;
struct node* right;
};
// 자식이 없는 새 노드 생성
struct node* newNode(int key){
struct node* node = (struct node*)malloc(sizeof(struct node));
node->key = key;
node->left = NULL;
node->right = NULL;
return (node);
}
// 역중위 순회하면서 누적 합 계산
void reverse_BST(struct node *root, int *sum_ptr){
if (root == NULL)
return;
reverse_BST(root->right, sum_ptr);
// 순회하면서 요소들을 누적
*sum_ptr = *sum_ptr + root->key;
root->key = *sum_ptr;
reverse_BST(root->left, sum_ptr);
}
// 누적 합을 이용해 트리의 값 갱신
void change_greater(struct node *root){
int sum = 0;
reverse_BST(root, &sum);
}
// 중위 순회 결과 출력
void printInorder(struct node* node){
if (node == NULL)
return;
printInorder(node->left);
cout << node->key << " " ;
printInorder(node->right);
}
int main(){
node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(13);
cout << "원본 트리 :" << endl;
printInorder(root);
change_greater(root);
cout << endl;
cout << "변경된 트리 :" << endl;
printInorder(root);
return 0;
}실행 결과
원본 트리 : 2 5 13 변경된 트리 : 20 18 13
동작 원리
위 예제에서 가장 큰 값인 13은 자신보다 큰 노드가 없으므로 그대로 13이 됩니다. 다음으로 방문되는 5는 5 + 13 = 18이 되고, 마지막으로 방문되는 2는 2 + 18 = 20이 됩니다.
- 시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택으로 트리의 높이(h)만큼 추가 공간이 필요합니다.
이처럼 역중위 순회와 누적합 포인터를 활용하면 단 한 번의 순회로 문제를 해결할 수 있어 매우 효율적입니다.