如果我不知道访问每个元素的概率，但我确信某些元素的访问频率会比其他元素高得多，我将使用 Splay tree 。如果我已经知道所有概率，我应该使用什么？我认为对于这种情况应该有一些比伸展树(Splay Tree)更好的数据结构。
我试图想象我应该在何时何地使用每种类型的搜索树的所有情况。也许有人可以发布一些有关比较所有搜索树和类似结构的文章的链接？
编辑 我希望仍然将 O(log n) 作为最坏的情况，但总的来说它应该更快。拉伸(stretch)树是一个很好的例子，但我想预定义这棵树的配置。
例如，我有一个元素数组来存储[a1, a2, .. an]，以及每个元素的概率[p1, p2, .. pn]，它定义了我访问每个元素的频率。我可以创建伸展树(Splay Tree)，将每个元素添加到伸展树(Splay Tree)中 (O(n log n))，然后以给定的概率访问它们以生成所需的树。因此，如果我的概率为 [1/2, 1/4, 1/4]，我需要展开第一个元素，使其成为第一个元素。因此，我需要按概率对元素进行排序，并按访问概率从最低到最高的顺序排列它们。这也需要O(n log n)。因此，构建这样的树的总时间是O(n log n)，并且是一个很大的常数。我的目标是降低这个数字。
我不介意使用其他东西，但不介意使用搜索树，但我希望时间比 Splay 树的时间短。我希望搜索、插入和删除在 O(log n) 摊销范围内。
最佳答案
编辑:我没有看到您想要动态更新树 - 下面的算法需要提前知道所有元素和概率。如果有人遇到这种情况，我会保留该帖子。
如果您碰巧拥有 Cormen 等人所著的第三版算法简介，它描述了一种动态规划算法，用于在您知道所有概率时创建最佳二叉搜索树.
以下是该算法的粗略概述:首先，对元素进行排序(根据元素值，而不是概率)。我们还不知道哪个元素应该是树的根，但我们知道树中根左侧的所有元素都将位于列表中该元素的左侧，反之亦然根右侧的元素。如果我们选择索引 k 处的元素作为根，我们会遇到两个子问题:如何为元素 0 到 k-1 构建最优树，以及如何为元素 k+1 到 n-1。递归地解决这些问题，以便您知道在根为元素 k 的树中进行搜索的预期成本。对k的所有可能选择执行此操作，您将找到哪棵树是最好的。使用动态编程或内存来节省计算时间。
关于algorithm - 当我知道访问每个元素的所有概率时，我应该使用什么搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11870822/