이 글에서는 흥미로운 트리 문제를 다뤄보겠습니다. 주어진 이진 탐색 트리(Binary Search Tree, BST)의 모든 노드에, 해당 노드보다 큰 값을 가진 모든 노드의 합을 더해 트리를 변환하는 것입니다.
변환이 완료되면 각 노드의 값은 "자기 자신을 포함하여 자신보다 크거나 같은 모든 노드 값의 누적 합"으로 바뀌게 됩니다. 변환 전과 후의 트리는 아래 그림과 같습니다.
알고리즘
핵심 아이디어는 역중위 순회(Reverse Inorder Traversal)입니다. 일반적인 중위 순회(왼쪽 → 루트 → 오른쪽)와 반대로 오른쪽 → 루트 → 왼쪽 순서로 트리를 방문하면, 노드 값들이 내림차순으로 처리됩니다. 따라서 각 노드를 방문할 때마다 지금까지의 누적 합을 현재 노드에 더해주기만 하면 됩니다.
의사 코드는 다음과 같습니다.
bstUpdate(root, sum) −
Begin
if root is null, then stop
bstUpdate(right of root, sum)
sum := sum + value of root
update root value using sum
bstUpdate(left of root, sum)
End
C++ 구현 예제
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node *getNode(int item) {
Node *newNode = new Node();
newNode->data = item;
newNode->left = newNode->right = NULL;
return newNode;
}
void updateBST(Node *root, int *sum) {
if (root == NULL)
return;
updateBST(root->right, sum); //오른쪽 서브트리부터 먼저 갱신
*sum = *sum + root->data;
root->data = *sum; //루트 노드의 값을 누적 합으로 갱신
updateBST(root->left, sum); //마지막으로 왼쪽 서브트리 갱신
}
void BSTUpdate(Node *root) {
int sum = 0;
updateBST(root, &sum);
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
Node* insert(Node* node, int data) {
if (node == NULL)
return getNode(data);
if (data <= node->data) //값이 작거나 같으면 왼쪽으로 이동
node->left = insert(node->left, data);
else //값이 크면 오른쪽으로 이동
node->right = insert(node->right, data);
return node;
}
int main() {
int data[] = {50, 30, 20, 40, 70, 60, 80};
int n = sizeof(data)/sizeof(data[0]);
Node *root = NULL;
for(int i = 0; i < n; i++) {
root = insert(root, data[i]);
}
BSTUpdate(root);
inorder(root);
}
출력 결과
350 330 300 260 210 150 80
동작 원리와 복잡도
입력 배열 {50, 30, 20, 40, 70, 60, 80}로 구성한 BST를 변환하면 각 노드의 값은 다음과 같이 계산됩니다.
- 80 → 80
- 70 → 70 + 80 = 150
- 60 → 60 + 70 + 80 = 210
- 50 → 50 + 60 + 70 + 80 = 260
- 40 → 40 + 50 + 60 + 70 + 80 = 300
- 30 → 30 + 40 + 50 + 60 + 70 + 80 = 330
- 20 → 20 + 30 + 40 + 50 + 60 + 70 + 80 = 350
변환된 트리를 중위 순회하면 값이 오름차순으로 출력되므로 위와 같은 결과를 얻을 수 있습니다. 이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출에 사용되는 스택 공간 때문에 공간 복잡도는 트리의 높이 h에 비례해 O(h)입니다. 균형 잡힌 BST라면 O(log n), 최악의 경우(편향 트리)에는 O(n)이 됩니다.