动态规划练习题-最优二分查找树

2019-09-12

问题描述:最优二叉查找树: 给定n个互异的关键字组成的序列K=<k1,k2,...,kn>,且关键字有序(k1<k2<...<kn),我们想从这些关键字中构造一棵二叉查找树。对每个关键字ki,一次搜索搜索到的概率为pi。可能有一些搜索的值不在K内,因此还有n+1个“虚拟键”d0,d1,...,dn,他们代表不在K内的值。具体:d0代表所有小于k1的值,dn代表所有大于kn的值。而对于i = 1,2,...,n-1,虚拟键di代表所有位于ki和ki+1之间的值。对于每个虚拟键,一次搜索对应于di的概率为qi。要使得查找一个节点的期望代价(代价可以定义为:比如从根节点到目标节点的路径上节点数目)最小,就需要建立一棵最优二叉查找树。 举例说明: n=5的关键字集合以及如下的搜索概率,构造二叉搜索树。 clipboard.png

clipboard.png

期望搜索代价的计算公式: clipboard.png下图中图a显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图b就是在这种情况下一棵最优二叉查找树。

clipboard.png

输入:p序列:表示对每个关键字ki,一次搜索搜索到的概率为pi; q序列:表示对每个虚拟键di,一次搜索搜索到的概率为qi。

输出:关键字和虚拟键的中序遍历结果

思路:

1 拆分子问题

2 计算

3 代码

4 时间复杂度

原文链接:segmentfault.com

上一篇:CSS改变图片颜色的filter(滤镜)属性
下一篇:使用VS code 插件debugger for chrome 调试react源码
相关教程
关注微信

扫码加入 JavaScript 社区

相关文章

首次访问,需要验证
微信扫码,关注即可
(仅需验证一次)

欢迎加入 JavaScript 社区

号内回复关键字:

回到顶部