有很多算法可以找到optimal binary search trees给定一组键和这些键被选中的相关概率。以这种方式生成的二叉搜索树查找这些元素的预期时间最少。然而，这个二叉搜索树对于其他度量可能不是最优的。例如，如果您尝试查找不包含在树中的键，查找时间可能会非常长，因为为了优化某些元素的查找，树可能不平衡。
我目前有兴趣了解如何从一组键构建二叉搜索树，其目标是最大限度地减少查找某个特定值的后继 所需的时间。也就是说，我希望树的构造方式是，给定一些随 secret 钥 k，我可以尽可能高效地找到 k 的后继者。我碰巧事先知道给定的随 secret 钥落在构成树的任意两个 key 之间的概率。
有人知道这个问题的算法吗？还是我误认为构建最优二叉搜索树的标准算法不会为这个用例生成有效的树？
最佳答案
所以现在我觉得很傻，因为这个问题有一个简单的答案。 :-)
您使用标准的现成算法来构造最优二叉搜索树来为键集构造一棵二叉搜索树。然后注释每个节点，以便它存储它的键和它之前的键之间的整个范围。这意味着您可以通过对优化构建的树进行标准搜索来有效地找到后继者。如果在任何时候发现您要查找的 key 包含在某个节点的范围内，那么您就完成了。换句话说，找到后继者相当于只是在BST中搜索值。
关于algorithm - 用于后继查找的最佳二叉搜索树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8662511/