特殊字典的最佳数据结构

Question

哪个数据结构在计算复杂性方面最佳,以实现(key,val)项的字典,这些项必须仅支持以下命令:

1. Insert(key) - 附加val = 1的项目(key,val)
2. Increment(key) - 增加现有的val(key,val)
3. Find(key) - 返回(key,val)的val
4. Select(part_of_key)- 如果strstr(key,part_of_key)!=NULL以相同类型的新字典的形式返回所有项目(key,val)的列表(如果可能的话,不分配新的内存); 例如,如果字典是{(红色,3),(蓝色,4),(绿色,1)},则选择(重新)= {(红色,3),(绿色,1)}
5. Max(i) - 返回所有项目中具有第i个最大值的项目; 例如,如果字典是{(红色,3),(蓝色,4),(绿色,1)},则Max(1)=蓝色,Max(2)=红色,Max(3)=绿色

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

我认为它必须是两种不同数据结构的综合.但它应该是哈希表+二叉树或trie +排序数组还是其他什么？

Answer 1

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

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

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

我认为你很难实现后缀树.您可以使用Mark Nelson的Ukkonen算法的C++实现,但它有内存泄漏并且本质上是一个单例,因此您需要在准备好生产之前将其清理干净.即使你修复它之后,你也需要调整它以使它适用于你的"其他"数据结构(我的提议中是平衡树),而不是一个大的普通字符串.

如果您比操作4更频繁地进行操作1和/或您可以使用线性操作4,我建议您使用后缀树跳过整个复杂功能并直接遍历数据结构.

Answer 2

虽然确切的答案取决于您的操作频率，但您的选项列表应包含后缀数组