2

如果我不知道访问每个元素的概率，但我确信某些元素会比其他元素更频繁地被访问，我将使用Splay tree。如果我已经知道所有概率，我应该使用什么？我认为在这种情况下应该有一些比展开树更好的数据结构。

我试图想象我应该在何时何地使用每种类型的搜索树的所有情况。也许有人可以发布一些关于比较所有搜索树和类似结构的文章的链接？

编辑我希望仍然O(log n)是最坏的情况，但总的来说它应该更快。展开树是很好的例子，但我想预定义这棵树的配置。

例如，我有一个要存储的元素数组[a1, a2, .. an]，以及每个元素的概率，这些概率[p1, p2, .. pn]定义了我访问每个元素的频率。我可以创建展开树，将每个元素添加到展开树 ( O(n log n))，然后以给定的概率访问它们以制作所需的树。因此，如果我有概率[1/2, 1/4, 1/4]，我需要展开第一个元素，使其成为第一个元素。所以，我需要按概率对元素进行排序，并按照访问概率从低到高的顺序展开它们。这O(n log n)也需要。因此，构建这种树的总时间是O(n log n)一个很大的常数。我的目标是降低这个数字。

我不介意使用其他东西，但不介意搜索树，但我希望时间低于 Splay 树的情况。我希望搜索、插入和删除都在O(log n)摊销的范围内。

4

3 回答 3

2

编辑：我没有看到您想要动态更新树 - 下面的算法需要提前知道所有元素和概率。我会留下这个帖子，以防遇到这种情况的人。

如果您碰巧拥有Cormen 等人的第三版算法介绍，它描述了一种动态规划算法，用于在您知道所有概率时创建最佳二叉搜索树。

以下是该算法的粗略概述：首先，对元素进行排序（根据元素值，而不是概率）。我们还不知道哪个元素应该是树的根，但我们知道树中根左侧的所有元素都将位于列表中该元素的左侧，反之亦然根右侧的元素。如果我们选择索引k处的元素作为根，我们会得到两个子问题：如何为元素 0 到k-1以及元素k+1到n-1构造一个最优树。递归解决这些问题，以便您知道在根为元素k的树中搜索的预期成本。对所有可能的k选择执行此操作，你会发现哪棵树是最好的。使用动态编程或记忆化以节省计算时间。

于 2012-08-10T09:40:48.380 回答
1

使用哈希表。

您从未提到需要有序迭代，通过牺牲这一点，您可以实现分摊的O(1)插入/访问复杂性，比O(log n).

具体来说，使用带有链表桶的哈希表，并使用前移优化。这意味着每次您搜索包含多个项目的存储桶（链表）时，都会将找到的项目移动到该存储桶的前面。下次访问此元素时，它已经在前面了。

如果您知道访问概率，则可以进一步改进该技术。将新元素插入存储桶时，不要将其插入前面，而是插入以保持最可能优先顺序。请注意，移至前端技术将倾向于隐式执行这种排序，但您可以帮助它更快地引导。

于 2012-08-10T18:16:53.557 回答
0

如果你的树一旦创建就不会改变，你可能应该使用哈希表或探戈树： http ://en.wikipedia.org/wiki/Tango_tree

哈希表在未重载时是 O(1) 查找，在重载时降级为 O(n)。

探戈树，一旦构建，是 O(loglogn) 查找。它们不支持删除或插入。

还有一些被称为“完美哈希”的东西可能对您有用。

于 2012-08-10T19:36:57.813 回答