洪捷第八版 3-58頁 範例3 (d)小題
If there are n records and every node has the identical access probability,
the cost for the optimal binary is Θ(nlogn).
答案此選項是正確的
請問一下這題是要怎麼算？謝謝

如果access到的機會一樣 , 最理想的cost就是讓樹長的矮如果要讓樹長的矮(平均)就想到AVL tree , n個點建構AVLtree就是 nlogn , 只是想法 , 不確定對不對

其實可以直接建一個balanced tree，O(n)應該做得到..只是不懂他的cost是指建樹的cost還是access的cost..如果本來record已經有順序了才有辦法O(n) 不然就是O(nlgn)

QQ,本來很好奇O(n)怎做的....