C++로 일반 이진 탐색 트리(BST)를 균형 BST로 변환하는 방법

이 튜토리얼에서는 일반 이진 탐색 트리(Binary Search Tree, BST)를 균형 잡힌 이진 탐색 트리(Balanced BST)로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다.

변환 대상은 왼쪽 또는 오른쪽으로 한쪽으로 치우친(skewed) 형태의 이진 탐색 트리입니다. 치우친 BST는 트리의 높이가 노드 수만큼 깊어져 탐색, 삽입, 삭제 연산이 최악의 경우 O(n)까지 느려질 수 있습니다. 따라서 우리의 목표는 정해진 규칙에 따라 이러한 트리를 높이가 최소화된 균형 잡힌 BST로 재구성하는 것입니다.

변환 접근 방법

균형 BST 변환은 크게 두 단계로 진행됩니다.

중위 순회(In-order Traversal): 주어진 BST를 중위 순회하면서 각 노드의 포인터를 벡터에 저장합니다. BST의 성질상 중위 순회 결과는 항상 오름차순으로 정렬되어 있습니다.
재귀적 재구성: 정렬된 노드 배열에서 가운데 원소를 루트로 선택하고, 왼쪽 부분과 오른쪽 부분에 대해 같은 과정을 재귀적으로 반복해 좌우 서브트리를 구성합니다.

이 방식을 사용하면 루트를 기준으로 좌우 노드 수가 절반씩 나뉘기 때문에, 자연스럽게 높이가 log₂(n)에 가까운 균형 잡힌 트리가 만들어집니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 트리 노드 구조체
struct Node{
    int data;
    Node* left, *right;
};

// 트리를 중위 순회하며 노드 포인터를 벡터 nodes에 저장
void store_nodes(Node* root, vector<Node*> &nodes){
    if (root==NULL)
        return;
    store_nodes(root->left, nodes);
    nodes.push_back(root);
    store_nodes(root->right, nodes);
}

// 정렬된 노드 배열로부터 균형 잡힌 이진 트리 구성
Node* construct_tree(vector<Node*> &nodes, int start,
int end){
    if (start > end)
        return NULL;
    // 가운데 원소를 루트로 지정
    int mid = (start + end)/2;
    Node *root = nodes[mid];
    root->left = construct_tree(nodes, start, mid-1);
    root->right = construct_tree(nodes, mid+1, end);
    return root;
}

// 불균형 BST를 균형 BST로 변환
Node* buildTree(Node* root){
    // 주어진 BST의 노드들을 정렬된 순서로 저장
    vector<Node *> nodes;
    store_nodes(root, nodes);
    int n = nodes.size();
    return construct_tree(nodes, 0, n-1);
}

// 새 노드 생성
Node* newNode(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

// 전위 순회(preorder) 수행
void preOrder(Node* node){
    if (node == NULL)
        return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

int main(){
    Node* root = newNode(10);
    root->left = newNode(8);
    root->left->left = newNode(7);
    root->left->left->left = newNode(6);
    root->left->left->left->left = newNode(5);
    root = buildTree(root);
    printf("Preorder traversal of balanced BST : \n");
    preOrder(root);
    return 0;
}

실행 결과

Preorder traversal of balanced BST : 
7 5 6 8 10

동작 원리 살펴보기

예제의 입력 트리는 10 → 8 → 7 → 6 → 5로 이어지는 왼쪽으로 치우친 BST입니다. 중위 순회를 수행하면 노드가 [5, 6, 7, 8, 10] 순서로 저장되고, 가운데 값인 7이 새로운 루트가 됩니다. 이후 왼쪽 부분 [5, 6]에서는 6이, 오른쪽 부분 [8, 10]에서는 8이 각각 서브트리의 루트로 선택되어 좌우 균형이 맞는 트리 구조가 완성됩니다.

시간 복잡도

중위 순회로 모든 노드를 저장하는 데 O(n), 균형 트리를 재구성하는 데에도 O(n)이 소요되므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 노드 포인터를 저장하는 벡터 때문에 O(n)입니다.