algorithm - 当我们提前估计时的二叉搜索树插入顺序

Question

我目前正在阅读 Robert Sedgewick 和 Kevin Wayne 合着的“算法第四版”。我有以下问题:

3.2.5 Suppose that we have an estimate ahead of time of how often search keys are to be accessed in a BST, and the freedom to insert items in any order that we desire. Should the keys be inserted into the tree in increasing order, decreasing order of likely frequency of access, or some other order? Explain your answer.

显然，最完美的情况是将最常访问的项目作为根，然后是其直接祖先，根据访问频率等依次类推。然而，这是 BST，因此我们必须根据其具体情况插入它们。我应该在这个任务中考虑所有的组合吗？

例如，如果我们有项目 1(访问 1000 次)、2(999 次)和 3(999)。根为 2 且祖先为 1 和 3 的树是我认为的最佳解决方案。努力拥有平衡的树对我来说听起来合乎逻辑。然而，这又取决于输入。如果我们有最小的项目被访问 10000 次而接下来的 10 个项目只被访问一次，那么最小的应该是根并且树不会完美平衡。

我也会感谢指导，而不是直接的回答。

Answer 1

按可能访问频率的升序或降序插入 key 都不是最佳方法。这个问题被称为创建最优二叉搜索树(最优 BST)。有关详细信息，请参阅 https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter3/section2/Exercise5.txt