data-structures - 用于快速位置查找的数据结构

Question

寻找逻辑上表示由唯一 id 键控的元素序列的数据结构(为了简单起见，我们将它们视为字符串，或者至少是可散列的对象)。每个元素只能出现一次，没有间隙，第一个位置为0。

应支持以下操作(用单字母字符串演示):

insert(id, position) - 添加由 id 键控的元素进入偏移量 position 处的序列.自然地，序列中后面每个元素的位置现在增加一。示例:[S E L F].insert(H, 1) -> [S H E L F]

remove(position) - 移除偏移量 position 处的元素.将序列中后面每个元素的位置减一。示例:[S H E L F].remove(2) -> [S H L F]

lookup(id) - 找到由 id 键控的元素的位置. [S H L F].lookup(H) -> 1

最简单的实现要么是一个链表，要么是一个数组。两者都会给 O(n) lookup , remove , 和 insert .

在实践中， lookup可能用得最多，用 insert和 remove发生的频率足够高，最好不要是线性的(hashmap + array/list 的简单组合会得到你)。

在一个完美的世界中，它将是 O(1) lookup , O(log n) insert/ remove ，但我实际上怀疑从纯粹的信息论角度来看这行不通(虽然我还没有尝试过)，所以 O(log n) lookup还是不错的。

Answer 1

trie 和哈希映射的组合允许 O(log n) 查找/插入/删除。

trie 的每个节点都包含 id 以及有效元素的计数器，以该节点为根和最多两个子指针。一个位串，由左 (0) 或右 (1) 转决定，同时从根遍历特里树到给定节点，是值的一部分，存储在对应 id 的哈希映射中。

删除操作将树节点标记为无效并更新从删除节点到根的路径上所有有效元素的计数器。它还删除相应的哈希映射条目。

插入操作应该使用每个 trie 节点中有效元素的位置参数和计数器来搜索新节点的前驱和后继节点。如果从前驱到后继的有序遍历包含任何已删除的节点，则选择排名最低的一个并重用它。否则选择前任或后继，并为其添加一个新的子节点(前任的右 child 或后继的左 child )。然后更新从该节点到根的路径上所有有效元素的计数器，并添加相应的哈希映射条目。

查找操作从哈希映射中获取一个位串，并使用它从特里根到相应的节点，同时对这条路径左边的所有有效元素的计数器求和。

如果插入/删除的序列足够随机，则所有这些都允许每个操作的预期时间为 O(log n)。如果不是，则每个操作的最坏情况复杂度为 O(n)。为了让它回到 O(log n) 摊销复杂度，注意树的稀疏和平衡因素，如果删除的节点太多，重新创建一个新的完美平衡和密集的树；如果树太不平衡，则重建最不平衡的子树。

可以使用一些二叉搜索树或任何字典数据结构来代替哈希映射。代替位串，用于标识树中的路径，哈希映射可以存储指向树中相应节点的指针。

在此数据结构中使用 trie 的其他替代方法是 Indexable skiplist .

每个操作的 O(log N) 时间是可以接受的，但并不完美。正如 Kevin 所解释的那样，可以使用具有 O(1) 查找复杂度的算法来换取其他操作的更大复杂度:O(sqrt(N))。但这可以改进。

如果您为每个查找操作选择一定数量的内存访问 (M)，则其他操作可能会在 O(M*N1/M) 时间内完成。这种算法的思想在 this answer to related question 中提出。 .那里描述的 Trie 结构允许轻松地将位置转换为数组索引并返回。该数组的每个非空元素都包含 id，哈希映射的每个元素都将此 id 映射回数组索引。

为了能够将元素插入到这个数据结构中，每个连续数组元素块都应该与一些空白空间交错。当其中一个块耗尽所有可用的空闲空间时，我们应该重建最小的一组块，与树中的某个元素相关，具有超过 50% 的空闲空间。当空闲空间总数小于50%或大于75%时，我们应该重建整个结构。

这种重新平衡方案仅针对随机和均匀分布的插入/删除提供 O(MN1/M) 摊销复杂度。对于 M > 2，最坏情况的复杂度(例如，如果我们总是在最左边的位置插入)要大得多。为了保证 O(MN1/M) 最坏情况，我们需要保留更多内存并更改重新平衡方案，以便它保持不变这:为整个结构保留至少 50% 的空白空间，为与顶级 trie 节点相关的所有数据保留至少 75% 的空白空间，为下一级 trie 节点保留 - 87.5% 等。

当 M=2 时，我们有 O(1) 的查找时间和 O(sqrt(N)) 的其他操作时间。

当 M=log(N) 时，我们对每个操作都有 O(log(N)) 时间。

但在实践中，较小的 M 值(如 2 .. 5)更可取。这可以被视为 O(1) 查找时间，并允许此结构(在执行典型的插入/删除操作时)以缓存友好的方式处理最多 5 个相对较小的连续内存块，并具有良好的矢量化可能性。如果我们需要良好的最坏情况复杂度，这也会限制内存需求。