最优二叉搜索树 - Cormen

Question

我期待到在算法导论最佳二叉搜索树由Cormen等作为参考我附上一个text link。

在399页在这里有贡献的表。我无法理解作者如何计算此列。例如节点k1的贡献是0.30，k4是0.20。作者如何计算这个值？

Answer 1

看公式来获得搜索成本在T =>E [T中搜索成本] = .... （页面398底部）

要K1获得成本：

k1=(depth(k1) + 1) * p1 

看看表，给出了深度（K1）的价值和P1 （页399）。

k1=(1+1)*0.15 
    =2*0.15 
    =0.3 

k2=(0+1)*0.10 
    =1*0.10 
    =0.10 

etc 

我希望我的解释能帮上忙。