algorithm - 特殊字典的最优数据结构

Question

就计算复杂性而言，哪种数据结构最适合实现(key，val)项的字典，它必须仅以下命令:

1. Insert(key) - 附加 val=1 的项 (key,val)
2. Increment(key) - 增加现有 (key,val) 的 val
3. Find(key) - 返回 (key,val) 的值
4. Select(part_of_key) - 如果 strstr(key,part_of_key)!=NULL 以新字典的形式返回所有项 (key,val) 的列表相同类型(如果可能，不分配新内存)；例如，如果字典是 {(red,3), (blue,4), (green,1)}，则 Select(re)={(red,3), (green,1)}
5. Max(i) - 返回所有项目中第 i 个最大值的项目；例如，如果字典是 {(red,3), (blue,4), (green,1)}，那么 Max(1)=blue, Max(2)=red, Max(3)=green

键是字符串，值是正整数。字典中的项目数量预计会非常大。

我想一定是两种不同数据结构的综合。但是应该是哈希表+二叉树还是trie+排序数组还是别的什么？

Answer 1

平衡树(如红黑树)和后缀树(或后缀数组)的组合。

• 平衡树:操作 1、2(实现为删除 + 插入)、3 和 5。
• 后缀树:操作4。

注意:哈希表将无法有效支持操作 5。

我认为您将很难实现后缀树。你可以使用 Mark Nelson's C++ implementation of Ukkonen's algorithm ，但它存在内存泄漏并且本质上是一个单例，因此您需要在准备好用于生产之前对其进行清理。即使在您修复它之后，您也需要对其进行调整，以便它与您的“其他”数据结构(在我的建议中是平衡树)一起工作，而不是一个大的纯字符串。

如果您执行操作 1 的频率高于操作 4 和/或您可以接受线性操作 4，我建议您跳过使用后缀树的整个复杂操作，只线性遍历您的数据结构。