データ構造入門：最適二分探索木（Optimal BST）で検索コストを最小化する方法

最適二分探索木とは

ソートされた順序で整数のキー集合が与えられ、同時に各キーの出現頻度を格納した配列 freq も渡されます。この課題は、これらのデータをもとに二分探索木（BST）を構築し、すべての検索にかかるコストの合計を最小にすることです。

検索コストは「キーの深さ × 出現頻度」の総和で表されます。そのため、頻度の高いキーほど根に近い浅い位置へ配置できれば、全体のコストを大きく抑えられます。このような木を最適二分探索木（Optimal BST）と呼びます。

部分問題の解を保存し、ボトムアップ方式で問題を解決するために、補助配列 cost[n][n] を作成します。このコスト行列には、動的計画法によって得られた各区間の最小コストが格納されていきます。

入力と出力の例

入力 − ノードとなるキー値と、それぞれの出現頻度。

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

出力 − 最小コストは 142。

上図は、与えられた値から構築できる二分探索木の一例です。それぞれのケースでコストを計算してみましょう。

• ケース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 を根に配置したケース5が最も効率的であることが分かります。

アルゴリズム

optCostBst(keys, freq, n)
入力: BSTに挿入するキー、各キーの頻度、キーの数
出力: 最適BSTを構築するための最小コスト
Begin
    n × n のコスト行列を定義する
    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, do
                if r > i, then
                    c := cost[i, r-1]
                else
                    c := 0
                if r < j, then
                    c := c + cost[r+1, j]
                c := c + iからjまでの頻度の合計
                if c < cost[i, j], then
                    cost[i, j] := c
            done
        done
    done
    return cost[0, n-1]
End

まず対角成分に単一キーのみの場合のコスト（＝そのキーの頻度）を設定し、次に部分木の長さを 2、3、… と拡張しながら、各区間でどのキーを根にすると最小コストになるかを全通り試します。区間 [i, j] 内のすべてのキーは一段深くなるため、頻度の合計 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++) //キーが1つだけの場合は対角成分に頻度を設定
        cost[i][i] = freq[i];
    for (int length = 2; length <= n; length++){
        for (int i = 0; i <= n-length+1; i++){ //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²) 通りあり、各区間で根の候補を最大 n 回試すため、時間計算量は O(n³) となります。また、コスト行列を保持するため空間計算量は O(n²) です。貪欲法では最適解が保証されないため、最適二分探索木を厳密に求めたい場合には、この手法が標準的な選択となります。