对于给定一组密钥以及所选密钥的相关概率,有许多算法可用于查找optimal binary search trees。以这种方式生成的二叉搜索树将具有查找这些元素的最低预期时间。然而,这种二叉搜索树对于其他度量可能不是最优的。例如,如果试图查找树中不包含的键,则查找时间可能非常长,因为树可能不平衡,以便优化某些元素的查找。
我现在感兴趣的是如何从一组键中构建一个二叉搜索树,目标是最小化找到某个特定值的后续值所需的时间也就是说,我希望树的结构是这样的,给定一些随机密钥k,我可以尽可能高效地找到k的继承者。我碰巧事先知道一个给定的随机密钥落在树的任意两个密钥之间的概率。
有人知道这个问题的算法吗?或者我是否误解了构建最优二叉搜索树的标准算法不能为这个用例生成有效的树?
最佳答案
所以现在我觉得很傻,因为这个问题有一个简单的答案:-)
您可以使用标准的现成算法来构造最优的二叉搜索树,以构造密钥集的二叉搜索树。然后对每个节点进行注释,使其存储键与之前键之间的整个范围。这意味着您可以通过对优化构建的树进行标准搜索来高效地找到后续的树。如果在任何时候发现您要查找的密钥包含在某个节点中的某个范围内,那么就完成了换句话说,找到继任者就相当于在BST中搜索值。