최적의 이진 탐색 트리(Optimal BST) – 개념, 알고리즘, C++ 구현까지

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

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

검색 비용은 '노드의 깊이 × 해당 키의 빈도'로 계산되므로, 자주 검색되는 키일수록 루트에 가까운 위치에 배치하는 것이 유리합니다. 이 문제는 부분 문제의 해를 저장하고 재활용하는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.

이를 위해 크기 n×n의 보조 배열 cost[n][n]을 생성하여 하위 문제들의 해를 저장하고, bottom-up(상향식) 방식으로 전체 문제를 풀어냅니다.

입력 및 출력 예시

입력:
키 값과 각 키의 빈도
Keys = {10, 12, 20}
Frequency = {34, 8, 50}

출력:
최소 비용은 142

주어진 키로 만들 수 있는 대표적인 BST 후보들은 다음과 같습니다.

• 케이스 1의 비용: (34×1) + (8×2) + (50×3) = 200
• 케이스 2의 비용: (8×1) + (34×2) + (50×2) = 176
• 케이스 5의 비용: (50×1) + (34×2) + (8×3) = 142 (최소)

즉, 빈도가 가장 높은 키 20을 루트에 배치하는 구조가 총 검색 비용을 가장 작게 만듭니다.

알고리즘

optCostBst(keys, freq, n)

입력: BST에 삽입할 키 배열, 각 키의 빈도 배열, 키의 개수 n

출력: 최적 BST를 구성할 때의 최소 비용

Begin
    n × 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
                if r > i, then
                    c := cost[i, r-1]
                else
                    c := 0
                if r < j, then
                    c := c + cost[r+1, j]
                c := c + freq[i]부터 freq[j]까지의 빈도 합
                if c < cost[i, j], then
                    cost[i, j] := c
            done
        done
    done
    return cost[0, n-1]
End

핵심 아이디어

cost[i][j]는 '키 i부터 j까지로 구성한 최적 BST의 최소 비용'을 의미합니다. 구간 내의 각 키 r을 루트로 삼았을 때의 비용은 다음과 같이 계산됩니다.

cost[i][r-1] (왼쪽 서브트리) + cost[r+1][j] (오른쪽 서브트리) + sum(freq, i, j)

여기서 빈도의 합을 매번 더해 주는 이유는, 서브트리가 상위 트리에 연결될 때마다 모든 노드의 깊이가 1씩 증가하기 때문입니다. 가능한 모든 루트 후보 r을 시도해 그중 최솟값을 cost[i][j]에 저장하면, 길이가 짧은 구간부터 차례로 확장해 나가며 최종적으로 cost[0][n-1]에 전체 최적 해가 담기게 됩니다.

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++) {    // i는 0행부터 n-length+1행까지
            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²)입니다. 구간 빈도 합을 미리 계산해 두는 누적 합(prefix sum) 배열을 활용하면 sum() 호출을 O(1)로 처리할 수 있어 전체 시간 복잡도를 O(n²)까지 개선할 수 있습니다.