agn*_*ter 7 language-agnostic data-structures
寻找逻辑上表示由唯一ID键入的元素序列的数据结构(为了简单起见,我们将它们视为字符串,或至少是可清除对象).每个元素只能出现一次,没有间隙,第一个位置为0.
应支持以下操作(使用单字母字符串演示):
insert(id, position)- 将键入的元素添加id到偏移量的序列中position.当然,序列中稍后的每个元素的位置现在增加1.例:[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 +阵列/列表的简单组合会让你).
在一个完美的世界中,它将是O(1)lookup,O(log n)insert/ remove,但我实际上怀疑从纯粹的信息理论角度来看是不行的(尽管我还没有尝试过),所以O(log n )lookup仍然会很好.
trie和哈希映射的组合允许 O(log n) 查找/插入/删除。
trie的每个节点包含id以及有效元素的计数器，以此节点和最多两个子指针为根。在从根到给定节点遍历trie时，由左 (0) 或右 (1) 轮确定的位字符串是值的一部分，存储在相应id的哈希映射中。
删除操作将trie节点标记为无效，并更新从已删除节点到根的路径上有效元素的所有计数器。它还删除相应的哈希映射条目。
插入操作应使用位置参数和每个trie节点中有效元素的计数器来搜索新节点的前驱节点和后继节点。如果从前驱到后继的中序遍历包含任何已删除的节点，则选择排名最低的节点并重用它。否则，选择前驱或后继，并向其添加一个新的子节点（前驱的右子节点或后继的左子节点）。然后更新从该节点到根的路径上所有有效元素的计数器，并添加相应的哈希映射条目。
查找操作从哈希映射中获取一个位字符串，并使用它从trie根到相应的节点，同时将该路径左侧的所有有效元素的计数器相加。
如果插入/删除的序列足够随机，所有这些都允许每个操作的预期时间为 O(log n)。如果不是，则每个操作的最坏情况复杂度为 O(n)。为了使其恢复到 O(log n) 摊销复杂度，请注意树的稀疏性和平衡因素，如果删除的节点太多，请重新创建一个新的完美平衡和密集的树；如果树太不平衡，则重建最不平衡的子树。
可以使用某种二叉搜索树或任何字典数据结构来代替哈希图。哈希映射可以存储指向trie中相应节点的指针，而不是用于标识trie中路径的位串。
在此数据结构中使用trie 的其他替代方法是Indexable Skiplist。
每个操作的 O(log N) 时间是可以接受的，但并不完美。正如 Kevin 所解释的，可以使用具有 O(1) 查找复杂度的算法来换取其他操作的更大复杂度：O(sqrt(N))。但这是可以改进的。
如果为每个查找操作选择一定数量的内存访问 (M)，则其他操作可能会在 O(M*N 1/M ) 时间内完成。这种算法的思想在相关问题的回答中提出。此处描述的 Trie 结构允许轻松地将位置转换为数组索引并返回。该数组的每个非空元素都包含id，并且哈希映射的每个元素都将该id映射回数组索引。
为了能够向该数据结构插入元素，每个连续数组元素块应该与一些空白空间交错。当其中一个块耗尽所有可用的空白空间时，我们应该重建与 trie 中某个元素相关的最小块组，该组具有超过 50% 的空白空间。当空置空间总数小于50%或大于75%时，应重建整个结构。
此重新平衡方案仅针对随机且均匀分布的插入/删除提供 O(M N 1/M ) 摊销复杂度。对于 M > 2，最坏情况的复杂度（例如，如果我们总是在最左边的位置插入）要大得多。为了保证 O(M N 1/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 个相对较小的连续内存块，并具有良好的矢量化可能性。如果我们需要良好的最坏情况复杂性，这也会限制内存需求。