最优二叉搜索树 java

最优二叉搜索树（Optimal Binary Search Tree，简称OBST）是一种特殊的二叉搜索树，其查询效率最高。在构建OBST时，我们需要考虑节点的访问频率或者概率。下面是一个使用Java实现最优二叉搜索树的示例代码：

public class OptimalBST {

    public static int optimalBST(int[] keys, int[] freq, int n) {
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            cost[i][i] = freq[i];
        }

        for (int L = 2; L <= n; L++) {
            for (int i = 0; i <= n - L + 1; i++) {
                int j = i + L - 1;
                cost[i][j] = Integer.MAX_VALUE;

                int sum = getSum(freq, i, j);
                for (int k = i; k <= j; k++) {
                    int tempCost = sum + ((k > i) ? cost[i][k - 1] : 0) + ((k < j) ? cost[k + 1][j] : 0);
                    cost[i][j] = Math.min(cost[i][j], tempCost);
                }
            }
        }

        return cost[0][n - 1];
    }

    private static int getSum(int[] freq, int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) {
            sum += freq[k];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] keys = {10, 12, 20};
        int[] freq = {34, 8, 50};
        int n = keys.length;

        int cost = optimalBST(keys, freq, n);
        System.out.println("The cost of optimal BST is: " + cost);
    }
}

运行上述代码，将输出最优BST的代价（cost）。