最優(yōu)二叉搜索樹？給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹。如果樹的加權(quán)路徑長度達(dá)到最小值，這樣的二叉樹稱為最優(yōu)二叉搜索樹，也稱為哈夫曼樹。哈夫曼樹是路徑長度最短的樹，權(quán)重越大的節(jié)點(diǎn)越靠近根。設(shè)二叉排

最優(yōu)二叉搜索樹？

給定n個(gè)權(quán)重作為n個(gè)葉節(jié)點(diǎn)，構(gòu)造一棵二叉樹。如果樹的加權(quán)路徑長度達(dá)到最小值，這樣的二叉樹稱為最優(yōu)二叉搜索樹，也稱為哈夫曼樹。哈夫曼樹是路徑長度最短的樹，權(quán)重越大的節(jié)點(diǎn)越靠近根。

設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長度為？

最壞的情況是深度為n的單棵樹是（n1）/2

最好的情況是形狀均勻，半搜索約為log2n

PS:如果構(gòu)造完成，例如：

則平均搜索長度為：（1×12×23×44×3）/10=2.9