最优二叉查找树 python

最优二叉查找树，也称为哈夫曼树或者权重平衡树，是一种二叉树，它的叶子节点存储着数据元素，而其他节点则存储着权重值。在最优二叉查找树中，每个节点的权重值等于其本身的权重值加上其子树中所有节点的权重值之和。因此，最优二叉查找树的根节点具有最小的权重值。

在 Python 中实现最优二叉查找树需要使用动态规划算法。具体来说，我们可以使用一个二维数组来存储每个子树的最小权重值，然后通过填充数组中的值来逐步构建最优二叉查找树。

以下是一个简单的 Python 实现：

def optimal_bst(keys, freq):
    n = len(keys)
    cost = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        cost[i][i] = freq[i]
    for L in range(2, n+1):
        for i in range(n-L+2):
            j = i+L-1
            cost[i][j] = float('inf')
            for k in range(i, j+1):
                c = 0 if k == i else cost[i][k-1]
                c += 0 if k == j else cost[k+1][j]
                c += sum(freq[i:j+1])
                if c < cost[i][j]:
                    cost[i][j] = c
    return cost[n-1]

keys = [10, 12, 20]
freq = [34, 8, 50]
print(optimal_bst(keys, freq)) # 输出结果为 142