algorithm - 创建最佳二叉搜索树，与创建霍夫曼树一样吗？

Question

很快就在这里学习期末考试，我想知道在下面的问题中创建一个最佳二叉搜索树是否与在给定符号和频率的情况下创建一个霍夫曼树相同。

用键 K1 < K2 < K3 < K4 计算最优二叉搜索树的概率：

p1 = .1  p2 = .2   p3 = .3  p4 = .1   
q0 = .15 q1 = .05  q2 = 0   q3 = .1

所以在这里我们将配对最低的两个概率并创建一个概率 = n1 + n2 的内部节点，然后将下一个最低的两个概率配对，等等？

Answer 1

它们实际上是两个不同的问题。霍夫曼树生成不需要保留密钥顺序，而 BST 生成则需要。此外，Huffman 树的生成需要额外的节点来“加入”其他节点，而 BST 中并非如此（您将节点与已经存在的节点连接起来）。

对于“最佳”BST 生成，您希望最小化所有节点深度的加权和（权重是节点的频率）。在这种情况下，p3 应该是 p2 和 p4 的父级，而 p2 应该是 p1 的父级。这会生成一个“加权和”：

Node Probability Depth Product Parent
K1   .1          2     .2      K2
K2   .2          1     .2      K3
K3   .3          0     0       None (root)
K4   .1          1     .1      K3
                       .5 (total, smaller than all other configurations)

不清楚你的意思q0to q3，但如果这些也是所需 BST 中的节点，你仍然会尝试优化深度的加权总和。