有很多算法寻找最优二叉搜索树的给定一组密钥和被选择的那些键的相关联的概率。这种方式生产将具有最低的预期时间来查找这些元素的二叉搜索树。然而，这二叉查找树可能不是最佳的问候其他措施。例如，如果试图查找未包含在树的一个键，查找时间可能是非常大的，作为树可能以优化某些元素的查找被不平衡。

There are many algorithms for finding optimal binary search trees given a set of keys and the associated probabilities of those keys being chosen. The binary search tree produced this way will have the lowest expected times to look up those elements. However, this binary search tree might not be optimal with regards to other measures. For example, if you attempt to look up a key that is not contained in the tree, the lookup time might be very large, as the tree might be imbalanced in order to optimize lookups of certain elements.

目前我在看到如何从一组键建立一个二叉搜索树其目的是尽量减少找到的继任者一些特定值所需的时间感兴趣。也就是说，我想树在，给予一定的随机密钥K的方式进行结构化的，我能找到k的后继者尽可能有效。我碰巧知道事先概率给定的随机密钥落入在中间的任意两个键的树是从构建

I am currently interested in seeing how to build an binary search tree from a set of keys where the goal is to minimize the time required to find the successor of some particular value. That is, I would like the tree to be structured in a way where, given some random key k, I can find the successor of k as efficiently as possible. I happen to know in advance the probability that a given random key falls in-between any two of the keys the tree is constructed from.

有谁知道一个算法对于这个问题的？还是我错了，标准算法构建最优二叉搜索树不会产生有效的树这个用例？

Does anyone know of an algorithm for this problem? Or am I mistaken that the standard algorithm for building optimal binary search trees will not produce efficient trees for this use case?

推荐答案

所以，现在我觉得自己很傻，因为有一个简单的回答这个问题。 ： - ）

So now I feel silly, because there's an easy answer to this question. :-)

您使用标准的，现成的现成算法构造最优二叉搜索树构造一个二叉搜索树的组密钥。然后，注释每一个节点，它存储了密钥和面前的键之间的整个范围。这意味着，你可以通过执行上的最佳建造树标准搜索有效地找到了接班人。如果在任何时候，你要寻找的关键是找到被包含在某个节点召开的范围内，那么就大功告成了。换句话说，找到后继相当于只是做了寻找在BST的值

You use the standard, off-the-shelf algorithm for constructing optimal binary search trees to construct a binary search tree for the set of keys. You then annotate each node so that it stores the entire range between its key and the key before it. This means that you can find the successor efficiently by doing a standard search on the optimally-built tree. If at any point the key you're looking for is found to be contained in a range held in some node, then you're done. In other words, finding the successor is equivalent to just doing a search for the value in the BST.