洪捷第八版 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)怎做的....