最优二叉搜索树 图解 最优二叉搜索树？

最优二叉搜索树？

给定n个权重作为n个叶节点，构造一棵二叉树。如果树的加权路径长度达到最小值，这样的二叉树称为最优二叉搜索树，也称为哈夫曼树。哈夫曼树是路径长度最短的树，权重越大的节点越靠近根。

设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为？

最坏的情况是深度为n的单棵树是（n1）/2

最好的情况是形状均匀，半搜索约为log2n

PS:如果构造完成，例如：

则平均搜索长度为：（1×12×23×44×3）/10=2.9

最优二叉搜索树 图解 树高最小的二叉排序树最佳 动态规划最优二叉搜索树例题

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。