C++에서 주어진 중위 순회(Inorder) 배열로 특수 이진 트리 생성하기

문제 개요

이진 트리의 중위 순회(inorder traversal) 결과가 담긴 배열 arr[]가 주어졌을 때, 이 배열로부터 특수 이진 트리(special binary tree)를 구성하는 것이 목표입니다. 여기서 특수 이진 트리란 루트 노드의 가중치(값)가 왼쪽 자식과 오른쪽 자식의 가중치보다 항상 큰 트리를 의미합니다.

예시

입력 1

int arr[] = {10, 20, 28, 40, 32, 31, 30}

출력 1

주어진 중위 순회로 구성되는 특수 이진 트리는 다음과 같습니다.

            40
           /  \
         28    32
        /        \
      20          31
     /              \
   10                30

설명

정수 값으로 이루어진 배열, 즉 트리의 중위 순회 결과가 입력으로 주어집니다. 루트가 항상 자식보다 크다는 조건을 만족하도록 트리를 구성하면, 중위 순회 결과가 10, 20, 28, 40, 32, 31, 30인 특수 트리가 만들어집니다.

입력 2

int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}

출력 2

              40
             /  \
           28    35
          /     /
        25     32
       /         \
     20           31
    /               \
  10                 30

설명

마찬가지로 배열의 최댓값을 루트로 삼고 좌우로 분할하는 과정을 반복하면, 중위 순회 결과가 10, 20, 25, 28, 40, 32, 31, 30, 35인 특수 이진 트리를 얻을 수 있습니다.

접근 방법

이 접근 방식에서는 배열에서 최댓값을 루트 노드로 삼아 특수 이진 트리를 구성합니다. 최댓값을 기준으로 왼쪽에 있는 원소들은 왼쪽 서브트리에, 오른쪽에 있는 원소들은 오른쪽 서브트리에 속하게 됩니다. 이 과정을 재귀적으로 반복하면 전체 트리가 완성됩니다.

중위 순회가 담긴 배열 arr[]를 입력으로 받습니다.
new_node(int data) 함수는 왼쪽·오른쪽 자식 포인터가 NULL인 새 노드를 생성합니다.
total(int arr[], int first, int last) 함수는 주어진 구간에서 최댓값 원소의 인덱스를 반환합니다.
highest = arr[first], lowest = first로 초기화합니다.
first + 1 인덱스부터 last까지 순회하면서 arr[i]가 highest보다 크면 그 인덱스를 lowest에 저장하고 highest를 갱신합니다.
for 루프가 종료되면 lowest에는 해당 구간 최댓값 원소의 인덱스가 들어 있습니다.
create_tree(int arr[], int first, int last) 함수는 arr[]로부터 재귀적으로 특수 이진 트리를 구성합니다.
first > last이면 트리를 만들 수 없으므로 NULL을 반환합니다.
temp = total(arr, first, last)를 호출해 구간 내 최댓값이 위치한 인덱스를 temp에 저장합니다.
arr[temp]를 데이터로 갖는 노드를 생성하고, parent 포인터가 이 노드(트리의 루트)를 가리키도록 합니다.
first == last이면 트리에 노드가 하나뿐이므로 parent를 그대로 반환합니다.
parent->left = create_tree(arr, first, temp - 1); 로 왼쪽 서브트리를 재귀적으로 구성합니다.
parent->right = create_tree(arr, temp + 1, last); 로 오른쪽 서브트리를 재귀적으로 구성합니다.
마지막에 parent를 반환합니다.
Inorder_traversal(tree_node* node) 함수는 앞서 생성한 트리의 중위 순회 결과를 출력합니다.
노드가 NULL이면 아무 작업도 하지 않고 종료하며, 그렇지 않으면 먼저 Inorder_traversal(node->left)로 왼쪽 서브트리를 출력합니다.
그다음 현재 노드의 데이터를 출력합니다.
마지막으로 Inorder_traversal(node->right)로 오른쪽 서브트리를 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
   public:
   int data;
   tree_node* left;
   tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
   if(first > last){
      return NULL;
   }
   int temp = total(arr, first, last);
   tree_node *parent = new_node(arr[temp]);
   if(first == last){
      return parent;
   }
   parent->left = create_tree(arr, first, temp - 1);
   parent->right = create_tree(arr, temp + 1, last);
   return parent;
}
int total(int arr[], int first, int last){
   int highest = arr[first];
   int lowest = first;
   for(int i = first + 1; i <= last; i++){
      if(arr[i] > highest){
         highest = arr[i];
         lowest = i;
      }
   }
   return lowest;
}
tree_node* new_node (int data){
   tree_node* newNode = new tree_node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
void Inorder_traversal(tree_node* node){
   if (node == NULL){
      return;
   }
   Inorder_traversal(node->left);
   cout<<node->data<<" ";
   Inorder_traversal (node->right);
}
int main(){
   int arr[] = {10, 20, 28, 40, 32, 31, 30};
   int size = sizeof(arr)/sizeof(arr[0]);
   tree_node *root = create_tree(arr, 0, size - 1);
   cout<<"Construct Special Binary Tree from given Inorder traversal are: "<<"\n";
   Inorder_traversal(root);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Construct Special Binary Tree from given Inorder traversal are:
10, 20, 28, 40, 32, 31, 30

복잡도 분석

시간 복잡도: 매 단계마다 구간의 최댓값을 찾기 위해 O(n)의 선형 탐색이 수행됩니다. 배열이 이미 정렬되어 있어 트리가 한쪽으로 치우치는 최악의 경우 시간 복잡도는 O(n²)가 됩니다. 세그먼트 트리 등으로 구간 최댓값 쿼리를 O(log n)에 처리하면 O(n log n)까지 개선할 수 있습니다.

공간 복잡도: 트리 노드 저장에 O(n), 재귀 호출 스택에 최대 O(n)이 사용되므로 전체 공간 복잡도는 O(n)입니다.