C++ 큐를 활용해 BST(이진 탐색 트리)의 경로 반전하기

이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 특정 키(key) 값까지의 경로에 있는 노드들을 역순으로 뒤집어야 하는 상황을 가정해 보겠습니다. 아래 예시를 통해 어떤 변화가 일어나는지 확인할 수 있습니다.

해결 접근 방법

이 방법의 핵심은 큐(queue)를 하나 준비하고, 루트에서 출발하여 목표 키를 가진 노드를 만날 때까지 경로상의 모든 노드 값을 순서대로 큐에 삽입하는 것입니다. 그런 다음 키 노드를 발견하면, 재귀 호출이 되감기면서 지금까지 쌓아 온 큐의 맨 앞(front) 값부터 차례대로 경로상의 각 노드에 다시 배치함으로써 경로 전체를 반전시킵니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
struct node {
    int key;
    struct node *left, *right;
};
// 새 노드를 생성하는 함수
struct node* newNode(int item){
    struct node* temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
// 중위 순회(inorder)로 트리를 출력하는 함수
void inorder(struct node* root){
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}
// 경로를 반전시키는 함수
void Reversing(struct node** node,
            int& key, queue<int>& q1){
    /* 트리가 비어 있다면 반환 */
    if (node == NULL)
        return;
    if ((*node)->key == key){ // 키를 찾은 경우
        q1.push((*node)->key); // 현재 노드의 값을 큐에 삽입
        (*node)->key = q1.front(); // 큐의 첫 번째 요소와 현재 값을 교체
        q1.pop(); // 첫 번째 요소를 제거
    }
    else if (key < (*node)->key){ // 키가 현재 노드의 값보다 작은 경우
        q1.push((*node)->key); // 현재 노드의 값을 큐에 삽입
        Reversing(&(*node)->left, key, q1); // 재귀 호출로 왼쪽 서브트리 탐색
        (*node)->key = q1.front(); // 노드의 값을 큐의 첫 번째 요소로 교체하여 반전
        q1.pop(); // 첫 번째 요소를 제거
    }
    else if (key > (*node)->key){ // 키가 현재 노드의 값보다 큰 경우
        q1.push((*node)->key); // 현재 노드의 값을 큐에 삽입
        Reversing(&(*node)->right, key, q1); // 재귀 호출로 오른쪽 서브트리 탐색
        (*node)->key = q1.front(); // 노드의 값을 큐의 첫 번째 요소로 교체
        q1.pop(); // 첫 번째 요소를 제거
    }
    return;
}
// BST에 노드를 삽입하는 함수
struct node* insert_node(struct node* node, int key){
    if (node == NULL)
        return newNode(key); // 트리가 비어 있으면 새 노드를 반환
    if (key < node->key) // 그렇지 않으면 트리에 노드를 삽입
        node->left = insert_node(node->left, key);
    else if (key > node->key)
        node->right = insert_node(node->right, key);
    return node; // 노드를 반환
}
int main(){
    struct node* root = NULL;
    queue<int> q1;
    int k = 80;
    /****************BST 생성*************************/
    root = insert_node(root, 50);
    insert_node(root, 30);
    insert_node(root, 20);
    insert_node(root, 40);
    insert_node(root, 70);
    insert_node(root, 60);
    insert_node(root, 80);
    cout << "Before Reversing :" << "\n";
    inorder(root);
    cout << "\n";
    Reversing(&root, k, q1);
    cout << "After Reversing :" << "\n";
    // 반전된 경로 트리의 중위 순회 결과 출력
    inorder(root);
    return 0;
}

실행 결과

Before Reversing :
20 30 40 50 60 70 80
After Reversing :
20 30 40 80 60 70 50

코드 설명

이 접근 방식에서는 주어진 키를 단순히 탐색합니다. 트리를 따라 내려가는 동안 만나는 모든 노드의 값을 큐에 차례로 넣고, 키 값과 일치하는 노드를 찾으면 재귀 호출이 되감기면서 큐의 맨 앞에 저장된 값부터 경로상 노드들의 값과 교체됩니다. 이 과정을 통해 경로가 자연스럽게 반전됩니다.

시간 및 공간 복잡도

루트에서 목표 키까지의 경로 길이를 h라고 하면, 각 노드마다 큐에 한 번씩 삽입하고 한 번씩 꺼내므로 시간 복잡도는 O(h)입니다. 큐에 경로상의 노드 값들이 저장되므로 공간 복잡도 역시 O(h)이며, 균형 잡힌 BST라면 O(log n), 최악의 경우(편향된 트리)에는 O(n)이 됩니다.

마무리

이번 글에서는 큐와 재귀를 활용해 BST의 특정 경로를 반전시키는 문제를 해결해 보았습니다. C++로 작성된 전체 프로그램과 문제 해결에 사용된 기본적인 접근 방식을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.