C++에서 주어진 BST의 모든 노드에 더 큰 값 추가하기

BST(이진 탐색 트리)란 무엇인가?

BST(Binary Search Tree, 이진 탐색 트리)는 모든 왼쪽 노드가 루트 값보다 작고, 모든 오른쪽 노드가 루트 값보다 큰 값을 가지는 이진 트리의 한 형태입니다. 이 문제에서는 이진 트리를 받아 현재 노드보다 큰 값을 가진 모든 노드의 합을 해당 노드에 더하는 작업을 수행합니다. 즉, "BST의 모든 노드에 더 큰 값 추가하기" 문제는 BST에서 현재 노드 값보다 큰 모든 노드 값을 그 노드의 값에 더하는 것으로 단순화할 수 있습니다.

문제 정의

이진 탐색 트리(BST)가 주어졌을 때, 각 노드에 자신보다 큰 값을 가진 모든 노드 값의 합을 더해야 합니다.

예를 들어 다음과 같은 BST가 있다고 가정해 보겠습니다.

        10
       /  \
      5    20
     / \   / \
    1   7 15  25

변환이 완료되면 각 노드는 "자신보다 큰 모든 노드 값의 합 + 자기 자신의 원래 값"을 가지게 됩니다.

        70
       /  \
      82   45
     / \   / \
    83 77 60  25

접근 방식: 역 중위 순회(Reverse Inorder Traversal)

이 프로그램은 BST를 각 노드의 값이 자신보다 큰 모든 요소의 합에 원래 노드 값을 더한 형태의 이진 트리로 변환합니다.

핵심 해결 방법은 역 중위 순회입니다. 일반적인 중위 순회가 왼쪽 → 루트 → 오른쪽 순서로 진행하는 것과 달리, 역 중위 순회는 오른쪽 서브트리를 먼저 재귀 호출하므로 노드를 내림차순으로 방문하게 됩니다. 동시에 지금까지 순회한 노드 값들의 누적 합을 저장하는 변수를 하나 유지합니다.

각 노드를 방문할 때 다음 순서로 처리합니다.

오른쪽 서브트리를 먼저 순회합니다.
현재 노드의 값을 누적 합 변수에 더합니다.
현재 노드의 값을 업데이트된 누적 합으로 대체합니다.
마지막으로 왼쪽 서브트리를 순회합니다.

이렇게 하면 각 노드는 자기 자신을 포함하여 자신보다 크거나 같은 모든 노드 값의 합을 갖게 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;
struct node{
    int data;
    node *left;
    node *right;
};
node *newNode(int key){
    node *temp=new node;
    temp->left=NULL;
    temp->right=NULL;
    temp->data=key;
    return temp;
}
void Inorder(node *root){
    if(!root)
    return;
    Inorder(root->left);
    cout<<root->data<<" ";
    Inorder(root->right);
}
node *Insert(node *root,int key){
    if(!root)
    return newNode(key);
    if(key<root->data)
        root->left=Insert(root->left,key);
    else
        root->right=Insert(root->right,key);
    return root;
}
void RevInorderAdd(node *root,int &sum){
    if(!root)
    return;
    RevInorderAdd(root->right,sum);
    sum+=root->data;
    root->data=sum;
    RevInorderAdd(root->left,sum);
}
void AddGreater(node *root){
    int sum=0;
    RevInorderAdd(root,sum);
}
int main() {
    /* 다음과 같은 BST를 생성합니다
    10
    / \
    5 20
    / \ / \
    1 7 15 25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
    Inorder(root);
    cout<<endl;
    AddGreater(root);
    Inorder(root);
    cout<<endl;
    return 0;
}

실행 결과

1 5 7 10 15 20 25
83 82 77 70 60 45 25

첫 번째 줄은 원본 BST의 중위 순회 결과(오름차순)이고, 두 번째 줄은 변환된 트리의 중위 순회 결과입니다. 각 값이 자신보다 크거나 같은 모든 노드 값의 누적 합으로 바뀐 것을 확인할 수 있습니다.

복잡도 분석

이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다(n은 노드 개수). 공간 복잡도는 재귀 호출 스택 때문에 트리의 높이 h에 비례하여 최악의 경우 O(h), 즉 편향된 트리에서는 O(n)입니다.