最佳搜索树:计算搜索树的成本，并表明它不是最佳的

Question

考虑以下二进制搜索树，以及以下查找频率：

       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工作负载。K上的搜索树T对于R是最佳的IFF P(T) = min{P(T') | T' is search tree for K}

@templatetypedef非常感谢您花时间和帮助！您的答案对我来说非常好，我从中了解很多事情。这是我发现从任务中的树比这棵树最佳的树：

        26
       /  
      13   28
     /
    11
   /  
  1    12

上面的树的成本为143，并且具有138。因此，这个确实更为最佳，并且解决了任务：）

Answer 1

从根本上讲，您正在处理正确计算BST中总查找时间的问题。您正在将每个节点在树中使用，使用深度来确定执行该节点结束的查找所需的比较数，将这些值乘以查找的数量，并汇总结果。我并没有仔细检查您的确切计算，因此您可能错过了一些东西。

您的第二个问题是要确定二进制搜索树是否适用于给定的一组查找。您已经给出了严格的数学定义，但是在这种情况下，我认为在更高级别上解释这一点可能会更容易。

您之前进行的计算是从BST开始的一种方法，以及有关将执行哪些查找的信息，然后计算与在执行这些查找过程中最终会做出的比较数量相对应的数字。该数字本质上告诉您这些查找的速度 - 较高的数字意味着查找需要更长的时间，较低的数字意味着查找的时间更少。

现在，想象一下您想制作一个BST，这将花费最少的时间来执行相关查找。换句话说，您想要给定的键和查找频率的"最佳" BST。该BST是总查找成本最低的，其中该成本是使用您早些时候使用的方法来计算的。该属性的BST的术语 - 它在您可以制作的所有可能的BST中具有最佳的查找速度 - 是最佳的BST。

这里的问题是证明您拥有的树不是最佳的。这意味着您需要证明这不是您可以制造的最好的树。做到这一点的一种方法是找到一棵更好的树。那么，您能找到另一个带有相同键的BST，其中总查找时间低于您的给予时间？

祝你好运！