数据结构：在这些情况下我应该使用哪种？

Question

6

这不应该是一个难题，但在继续之前我想找个人来讨论一下。根据以下预期的活动，我只需要决定使用哪种数据结构：

顺便说一下，这是在Java中。

我最好的猜测是，我要么将滚动一些自定义的Linked Hash Set（以按排序顺序排列链接），要么可能只使用Tree Set。但我还不完全确定。有什么建议吗？

编辑：我想因为任意的删除/恢复，我应该坚持使用Tree Set，对吧？

实际上不一定。嗯...

- Daddy Warbox

请将主要标签保留在标题的开头，谢谢。 - Daddy Warbox

2个回答

3

在理论上，我会说正确的数据结构是一棵多路树 - 最好是类似于B+树的结构。传统上，这是一种基于磁盘的数据结构，但现代主存储器由于层层缓存和虚拟内存的特性，也有很多相似之处。

B+树的中序遍历非常高效，因为（1）你只需要遍历叶节点的链表 - 不需要分支节点，（2）你可以获得极好的局部性。

查找、删除和插入任意元素的时间复杂度都是log(n)，与任何平衡树一样，尽管常数因子不同。

在树内重新排序主要是选择一种算法，在操作块（叶节点）的链接列表时具有良好的性能，最小化使用叶节点的需求 - 快速排序或归并排序的变体似乎是合适的候选。一旦分支节点中的项目排序完成，只需将摘要信息传播回叶节点即可。

但是 - 实际上，只有在非常确定需要时才会这样做。很可能最好使用一些标准容器。算法/数据结构优化是最好的优化方式，但仍可能过早。

- user180247

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Roman · Accepted Answer

如果您希望数据结构存储非唯一值，可以使用标准的LinkedHashSet或Google Collections中的LinkedMultiset。