最优搜索树:计算搜索树的成本，并表明它不是最优的。
考虑以下二进制搜索树，以及以下查找频率：
13 Key | 13 | 11 | 26 | 1 | 12 | 28
/ \ -----------------------------------------
11 26 Frequency | 26 | 5 | 25 | 1 | 3 | 15
/ \ \
1 12 28 我被问到这个问题：
计算给定搜索频率的搜索树的成本，并表明搜索树对于给定的搜索频率不是最优的。
我计算了成本，但我的老师说我做得不对，但没有解释原因。
因此，为了计算成本，我们需要做的是检查第一个节点在哪里。13为1级，13为26。所以我们做26*1=26
节点11和26位于2级，节点1、12和28位于3级。
最后，我们有了成本：26*1 + 5*2 + 25*2 + 1*3 + 3*3 + 15*3。我的老师说这个计算是不正确的，但没有解释原因。
另外，如何证明树不是最优的呢？下面是我从脚本中得到的定义：
让
K是一组键，R是一个工作负载。T在K上的搜索树对于R的P(T) = min{P(T') | T' is search tree for K}是最优的
@templatetypedef非常感谢您的时间和帮助！！你的回答对我很好，我从中了解了很多事情。这是一棵树，我发现它比任务中的树更理想：
26
/ \
13 28
/
11
/ \
1 12上面的树有143的成本，而这个树有138的代价。因此，这个问题实际上更加优化，并且任务得到了解决:)
回答 1
Stack Overflow用户
发布于 2017-09-18 19:36:18
从根本上讲，您正在处理正确计算BST中的总查找时间的问题。您将获取树中的每个节点，使用深度来确定执行以该节点结束的查找所需的比较数，将这些值乘以查找次数，并对结果进行求和。我没有仔细检查你的精确计算结果，所以你有可能漏掉了什么。
第二个问题是确定二进制搜索树对于给定的一组查找是否是最优的。你已经给出了严格的数学定义，但在这种情况下，我认为在更高的层次上解释这个问题可能会容易一些。
您在这里所做的计算是一种以BST和有关将执行什么查找的信息开始的方法，然后计算对应于在执行这些查找过程中将进行的比较数量的数字。这个数字从本质上告诉你这些查找的速度--更高的数字意味着查找所需的时间更长，而较低的数字则意味着查找将花费更少的时间。
现在，假设您想要创建一个BST，它将花费最少的时间来执行有关的查找。换句话说，您需要给定的一组键和查找频率的“最佳”BST。BST将是总查找成本最低的一个，该成本是使用您之前所使用的方法计算的。具有该属性的BST的术语--它对所有可能的BST中的频率具有最佳的查找速度--是最佳的BST。
这里的问题是要证明你拥有的树不是最优的。这意味着你需要证明这不是你能做的最好的树。一种方法是找到一棵更好的树。那么，您能找到另一个BST与相同的键，其中的总查找时间比你给的时间？
祝好运!
https://stackoverflow.com/questions/46285980
复制相似问题
腾讯云开发者
