Cây Tìm Kiếm Nhị Phân Tối Ưu (Optimal Binary Search Tree)

Giới thiệu

Cho một tập khóa đã sắp xếp và tần suất truy cập tương ứng. Xây dựng cây tìm kiếm nhị phân sao cho chi phí tìm kiếm trung bình (tổng tần suất × độ sâu) là nhỏ nhất.

Đầu vào và Đầu ra

Đầu vào: Keys = {10, 12, 20}, Frequency = {34, 8, 50}
Đầu ra: Chi phí tối thiểu = 142.

Thuật toán Quy hoạch động

Bảng cost[i][j] lưu chi phí tối thiểu cho cây chứa khóa từ i đến j. Thử từng khóa làm gốc và chọn chi phí nhỏ nhất.

optCostBst(keys, freq, n)
Begin
    định nghĩa cost[n][n]
    for i := 0 to n-1 do cost[i][i] := freq[i] done
    for length := 2 to n do
        for i := 0 to n - length do
            j := i + length - 1
            cost[i][j] := ∞
            for r := i to j do
                c := (r > i ? cost[i][r-1] : 0) + (r < j ? cost[r+1][j] : 0) + sum(freq, i, j)
                if c < cost[i][j] then cost[i][j] := c
            done
        done
    done
    return cost[0][n-1]
End

Ví dụ C++

#include <iostream>
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 << "Chi phí Optimal BST: " << minCostBST(keys, freq, n);
    return 0;
}

Kết quả

Chi phí Optimal BST: 142