最優二叉搜索樹 - 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 

我希望我的解釋能幫上忙。