데이터 구조에서 최적 이진 탐색 트리(Optimal BST) 구하기

최적 이진 탐색 트리(Optimal Binary Search Tree)란?

정렬된 순서로 주어진 정수 집합(keys)과 각 키의 검색 빈도를 저장한 배열(freq)이 있을 때, 이 데이터로 이진 탐색 트리(Binary Search Tree, BST)를 구성하여 모든 검색에 드는 총비용을 최소화하는 것이 이 문제의 목표입니다.

검색 비용은 노드의 깊이(루트는 1)에 해당 키의 빈도를 곱한 값으로 계산됩니다. 따라서 자주 검색되는 키일수록 루트에 가깝게 배치하는 것이 유리합니다.

이 문제는 부분 문제의 해를 저장하고 활용하는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 크기 n×n의 보조 배열 cost[n][n]을 생성하여 하위 문제들의 최소 비용을 저장하고, 바닥업(bottom-up) 방식으로 전체 문제의 해를 구합니다.

문제 예시

입력 − 키 값과 각 키의 빈도:

Keys = {10, 12, 20}
Frequency = {34, 8, 50}

출력 − 최소 비용은 142입니다.

주어진 값들로 만들 수 있는 여러 가지 BST 중 일부를 살펴보겠습니다.

케이스 1: 10이 루트인 경우 → (34×1) + (8×2) + (50×3) = 200
케이스 2: 10과 20이 위쪽에 위치한 경우 → (8×1) + (34×2) + (50×2) = 176
케이스 5: 20이 루트인 경우 → (50×1) + (34×2) + (8×3) = 142 (최솟값)

빈도가 가장 높은 50을 루트에 배치했을 때 총비용이 가장 작아지는 것을 확인할 수 있습니다.

알고리즘

핵심 아이디어는 다음과 같습니다. 구간 [i, j]의 키들로 만드는 서브트리에서 r을 루트로 선택하면, 그 비용은 왼쪽 서브트리 cost[i][r-1]과 오른쪽 서브트리 cost[r+1][j]의 비용에 구간 전체 빈도의 합을 더한 값입니다. 모든 가능한 루트 후보 r을 시도해 그중 최솟값을 선택합니다.

optCostBst(keys, freq, n)
입력: BST에 삽입할 키들, 각 키의 빈도, 키의 개수
출력: 최적 BST를 만들기 위한 최소 비용
Begin
    n x n 크기의 cost 행렬 정의
    for i in range 0 to n-1, do
        cost[i, i] := freq[i]   // 키가 하나뿐인 경우
    done
    for length in range 2 to n, do   // 구간 길이
        for i in range 0 to (n-length+1), do
            j := i + length – 1
            cost[i, j] := ∞
            for r in range i to j, done   // r을 루트로 시도
                if r > i, then
                    c := cost[i, r-1]
                else
                    c := 0
                if r < j, then
                    c := c + cost[r+1, j]
                c := c + sum of frequency from i to j
                if c < cost[i, j], then
                    cost[i, j] := c
            done
        done
    done
    return cost[0, n-1]
End

알고리즘 핵심 포인트

초기화: 대각선 요소 cost[i][i]는 키가 하나만 있는 서브트리의 비용으로 freq[i]를 저장합니다.
구간 확장: 길이 2부터 n까지 구간을 점차 넓혀가며 최적해를 계산합니다.
빈도 합산: 서브트리가 한 단계 깊어질 때마다 구간 내 모든 빈도가 한 번씩 추가되므로, 매 단계 sum(freq, i, j)를 더해줍니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int sum(int freq[], int low, int high){ //low부터 high까지 빈도의 합
   int sum = 0;
   for (int k = low; k <=high; k++)
      sum += freq[k];
   return sum;
}
int minCostBST(int keys[], int freq[], int n){
   int cost[n][n];
   for (int i = 0; i < n; i++) //키가 하나뿐일 때 대각선 요소 처리
      cost[i][i] = freq[i];
   for (int length=2; length<=n; length++){
      for (int i=0; i<=n-length+1; i++){ //0행부터 n-length+1행까지 i 사용
         int j = i+length-1;
         cost[i][j] = INT_MAX; //처음에는 무한대로 초기화
         for (int r=i; r<=j; r++){
            //r이 서브트리의 루트일 때의 비용 계산
            int c = ((r > i)?cost[i][r-1]:0)+((r < j)?cost[r+1][j]:0)+sum(freq, i, j);
            if (c < cost[i][j])
               cost[i][j] = c;
         }
      }
   }
   return cost[0][n-1];
}
int main(){
   int keys[] = {10, 12, 20};
   int freq[] = {34, 8, 50};
   int n = 3;
   cout << "Cost of Optimal BST is: "<< minCostBST(keys, freq, n);
}

실행 결과

Cost of Optimal BST is: 142

이 알고리즘의 시간 복잡도는 세 겹의 반복문으로 인해 O(n³)이며, 공간 복잡도는 cost 행렬 때문에 O(n²)입니다. 단순히 모든 BST 조합을 완전 탐색하는 지수 시간 방법보다 훨씬 효율적입니다.