C++ STL set을 활용해 이진 트리를 이진 검색 트리(BST)로 변환하는 방법

주어진 이진 트리(Binary Tree)를 원래 트리의 구조는 그대로 유지한 채 이진 검색 트리(Binary Search Tree, BST)로 변환해야 하는 경우가 있습니다. 이 글에서는 배열 기반 방식 대신 C++ STL의 set 컨테이너를 활용하는 해결 방법을 소개합니다.

예제

예제 1

입력

      11
     /  \
    3    8
   /      \
  9        5

출력

      9
     /  \
    5    11
   /       \
  3         8

예제 2

입력

       11
      /  \
    31    16
   /        \
 21          6

출력

       16
      /  \
    11    21
   /        \
  6          31

풀이 접근 방식

• 중위 순회(inorder traversal)를 수행하면서 이진 트리의 모든 노드 값을 set에 복사합니다. 이 과정에는 O(n log n)의 시간이 소요됩니다. 참고로 C++ STL(표준 템플릿 라이브러리)의 set은 레드-블랙 트리(Red-Black Tree), AVL 트리 등과 같은 자가 균형 이진 검색 트리(Self-Balancing BST)를 기반으로 구현되어 있습니다.
• set에 대해 별도의 정렬 작업은 필요하지 않습니다. C++의 set은 자가 균형 이진 검색 트리로 구현되어 있어 삽입, 탐색, 삭제 등 모든 연산이 O(log n)의 시간 안에 처리되며, 항상 내부적으로 정렬된 상태를 유지하기 때문입니다.
• 이제 트리를 중위 순회하면서 set의 요소를 시작부터 차례대로 트리에 복사하면 됩니다. 이때 주의할 점은, set의 각 요소를 복사할 때 먼저 중위 순회 도중 해당 값을 트리에 대입한 뒤, 그 요소를 set에서 반드시 삭제해야 한다는 것입니다.
• 현재 소개한 방식은 배열 기반의 이진 트리 → BST 변환 방법보다 더 간단하고 구현하기 쉽다는 장점이 있습니다.

다음은 set을 사용하여 이진 트리를 이진 검색 트리(BST)로 변환하는 전체 프로그램입니다.

예제 코드

/* set을 컨테이너로 사용하여 이진 트리를 BST로 변환하는 C++ 프로그램 */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
    int data;
    struct Node1 *left, *right;
};

// 중위 순회를 수행하며 노드들을 set에 저장하는 함수
void storeinorderInSet(Node1* root1, set<int>& s){
    if (!root1)
        return;
    // 왼쪽 서브트리를 먼저 방문
    storeinorderInSet(root1->left, s);
    // set에 대한 삽입 연산은 O(log n)의 시간이 소요됨
    s.insert(root1->data);
    // 오른쪽 서브트리를 방문
    storeinorderInSet(root1->right, s);
}
// 시간 복잡도 = O(n log n)

// 중위 순회를 수행하며 set의 요소를 하나씩 트리에 복사하는 함수
void setToBST(set<int>& s, Node1* root1){
    // 기저 조건(base condition)
    if (!root1) return;
    // 먼저 왼쪽 서브트리로 이동하며 값을 갱신
    setToBST(s, root1->left);
    // set의 시작 위치를 가리키는 반복자
    auto it = s.begin();
    // set(정렬된 상태)의 첫 번째 요소를 트리에 복사
    root1->data = *it;
    // set에서 해당 요소를 삭제
    s.erase(it);
    // 오른쪽 서브트리로 이동하며 값을 갱신
    setToBST(s, root1->right);
}
// 시간 복잡도 T(n) = O(n log n)

// 이진 트리를 BST로 변환하는 함수
void binaryTreeToBST(Node1* root1){
    set<int> s;
    // 트리의 중위 순회 결과로 set을 채움
    storeinorderInSet(root1, s);
    // set은 자가 균형 BST로 구현되어 기본적으로 정렬된 상태를 유지함
    // 중위 순회하면서 set의 요소를 트리에 복사하면 BST가 완성됨
    setToBST(s, root1);
}
// 시간 복잡도 = O(n log n)
// 보조 공간(Auxiliary Space) = set을 위한 O(n)

// 노드를 생성하는 헬퍼 함수
Node1* newNode(int data){
    // 동적 메모리 할당
    Node1* temp = new Node1();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// 중위 순회를 수행하는 함수
void inorder(Node1* root1){
    if (!root1)
        return;
    inorder(root1->left);
    cout << root1->data << " ";
    inorder(root1->right);
}

int main(){
    Node1* root1 = newNode(6);
    root1->left = newNode(8);
    root1->right = newNode(10);
    root1->right->left = newNode(11);
    root1->left->left = newNode(2);
    root1->left->right = newNode(7);
    root1->right->right = newNode(12);
    /* 아래 그림과 같은 트리를 생성
          6
         / \
        8  10
       /\  /\
      2  7 11 12 */
    // 위의 이진 트리를 BST로 변환
    binaryTreeToBST(root1);
    cout << "Inorder traversal of BST is: " << endl;
    inorder(root1);
    return 0;
}

출력

Inorder traversal of BST is:
2 6 7 8 10 11 12

BST의 중위 순회 결과는 항상 오름차순으로 정렬된 값들이 출력되므로, 변환이 올바르게 수행되었음을 손쉽게 확인할 수 있습니다.

시간 복잡도: O(n log n)
보조 공간(Auxiliary Space): O(n)