Optimal Binary Search Tree (BST ที่เหมาะสมที่สุด)

กำหนด Keys ที่เรียงลำดับแล้ว และ Frequency ของแต่ละ Key ต้องการสร้าง Binary Search Tree ที่มี Expected Search Cost น้อยที่สุด

Cost = Σ (frequency[i] × depth ของ key[i] ในต้นไม้)

ตัวอย่าง Input และ Output

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

Output: Cost of Optimal BST is: 142

ตัวเลือก BST และ Cost:
Case 1 (Root=10): 34×1 + 8×2 + 50×3 = 200
Case 2 (Root=12): 8×1 + 34×2 + 50×2 = 176
Case 5 (Root=20): 50×1 + 34×2 + 8×3 = 142 ← Minimum

อัลกอริทึม Dynamic Programming (Interval DP)

ฟังก์ชัน optCostBst(keys, freq, n)

กำหนด:

cost[i][j] = minimum cost ของ BST ที่ประกอบด้วย keys[i..j]

Recurrence:

cost[i][j] = min over r (cost[i][r-1] + cost[r+1][j] + sum(freq[i..j])) สำหรับ r = i ถึง j

โดย sum(freq[i..j]) คือผลรวม frequency ทั้งหมดใน subtree (ทุกโหนดลึกขึ้น 1 ระดับ)

ขั้นตอน:

cost[i][i] = freq[i] (โหนดเดียว)
for length = 2 ถึง n:
- for i = 0 ถึง n-length:
  - j = i + length - 1
  - cost[i][j] = INF
  - for r = i ถึง j (ลอง root แต่ละตัว):
    - c = (r>i?cost[i][r-1]:0) + (r


คืน cost[0][n-1]



ตัวอย่างโค้ด C++
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int sum(int freq[], int low, int high) {
    int s = 0;
    for (int k = low; k <= high; k++) s += freq[k];
    return s;
}

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; i++) {
            int j = i + length - 1;
            cost[i][j] = INT_MAX;
            for (int r = i; r <= j; 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);
    return 0;
}

Output
Cost of Optimal BST is: 142

ความซับซ้อน

Time: O(n³) (สามารถลดเป็น O(n²) ด้วย Knuth's Optimization ได้)
Space: O(n²)


Knuth's Optimization (O(n²))
ถ้า cost function ตรงตาม Quadrangle Inequality และ Monotonicity สามารถจำกัดช่วง k ให้แค่ opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]