設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為？最壞的情況是深度為n的單棵樹(shù)是（n1）/2最好的情況是形狀均勻，半搜索約為log2nPS:如果構(gòu)造完成，例如：那么平均搜索長(zhǎng)度是：（1×12×

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

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

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

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

那么平均搜索長(zhǎng)度是：（1×12×23×4×3）/10=2.9

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