用于后继查找的最佳二叉搜索树？

Question

给定一组密钥并选择这些密钥的相关概率，有许多算法可用于查找optimal binary search trees。以这种方式生成的二叉搜索树将具有查找这些元素的最低预期时间。但是，这种二叉搜索树在其他方面可能不是最优的。例如，如果您尝试查找树中未包含的键，查找时间可能非常大，因为树可能不平衡以优化对某些元素的查找。

我目前有兴趣了解如何从一组键中构建二叉查找树，其目标是最大限度地减少找到具有某种特定价值的后继所需的时间。也就是说，我希望该树的结构可以通过给定一些随机密钥k来尽可能有效地找到k的后继者。我碰巧预先知道给定的随机密钥落入树的任何两个密钥之间的概率。

有没有人知道这个问题的算法？或者我错误地认为，构建最优二叉搜索树的标准算法不会为此用例生成有效的树？

Answer 1

所以现在我觉得很傻，因为这个问题很简单。 :-)

您可以使用标准的现成算法构建最优二叉搜索树，以构建该组键的二叉搜索树。然后，您对每个节点进行注释，以便在其之前存储其密钥和密钥之间的整个范围。这意味着您可以通过对最佳构建的树进行标准搜索来高效地找到后继者。如果在任何时候发现你正在查找的密钥都包含在某个节点的范围内，那么你就完成了。换句话说，找到后继者就相当于只搜索BST中的值。