Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

BST(이진 탐색 트리)의 모든 노드에 더 큰 값 합계 추가하기

BST란 무엇인가?

이진 탐색 트리(BST, Binary Search Tree)는 모든 왼쪽 자식 노드가 부모(루트) 값보다 작고, 모든 오른쪽 자식 노드가 부모 값보다 큰 규칙을 가지는 이진 트리입니다. 이러한 구조 덕분에 탐색, 삽입, 삭제 연산을 평균적으로 O(log n) 시간에 수행할 수 있습니다.

이번 글에서 다룰 문제는 "BST의 모든 노드에 더 큰 값 합계 추가하기"로, BST의 각 노드에 자신보다 큰 값을 가진 모든 노드들의 합을 더해 새로운 트리를 만드는 것입니다.

문제 설명

주어진 이진 탐색 트리(BST)의 각 노드에 대해, 해당 노드보다 큰 값을 가진 모든 노드 값의 합을 원래 노드 값에 더해야 합니다. 즉, 각 노드의 최종 값은 (자신보다 큰 모든 노드의 합) + (원래 노드 값)이 됩니다.

입력 예시

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

출력 결과

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

결과 해석

예를 들어 루트 노드 10의 경우, 자신보다 큰 값은 15, 20, 25이며 그 합은 60입니다. 따라서 10 + 60 = 70이 되어 루트 노드의 값이 70으로 변경됩니다. 마찬가지로 가장 왼쪽 리프 노드 1은 자신보다 큰 모든 값(5, 7, 10, 15, 20, 25)의 합인 82를 더해 83이 됩니다.

즉, 이 프로그램은 BST를 각 노드의 값이 '자신보다 큰 모든 요소의 합 + 원래 노드 값'으로 변환된 이진 트리로 바꾸는 역할을 합니다.

해결 접근 방법: 역중위 순회(Reverse Inorder Traversal)

핵심 아이디어는 역중위 순회를 사용하는 것입니다. 일반적인 중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 방문하지만, 역중위 순회는 오른쪽 서브트리 → 루트 → 왼쪽 서브트리 순서로 방문합니다.

BST에서 역중위 순회를 수행하면 노드들을 내림차순으로 방문하게 됩니다. 이때 지금까지 방문한 노드 값의 누적 합을 저장하는 변수(sum)를 함께 유지하면 다음과 같이 처리할 수 있습니다.

  1. 현재 노드의 값을 누적 합 변수에 더합니다.
  2. 누적 합 변수의 값으로 현재 노드의 값을 교체합니다.
  3. 왼쪽 서브트리에 대해 재귀적으로 같은 과정을 반복합니다.

이 방식은 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 공간 복잡도는 재귀 호출 스택 깊이만큼인 O(h)(h는 트리의 높이)입니다.

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) 시간 안에 해결할 수 있는 대표적인 트리 변환 문제입니다. BST의 정렬된 특성을 중위 순회의 응용으로 활용하는 좋은 예시이므로, 코딩 인터뷰 준비 시 꼭 기억해 두면 유용합니다.