trie和哈希映射的组合允许 O(log n) 查找/插入/删除。
trie的每个节点都包含id以及有效元素的计数器，以该节点为根和最多两个子指针。一个位串，由左 (0) 或右 (1) 转决定，同时从它的根遍历trie到给定节点，是值的一部分，存储在对应id的哈希映射中。
删除操作将trie节点标记为无效，并更新从已删除节点到根的路径上的所有有效元素的计数器。它还删除了相应的哈希映射条目。
插入操作应该使用每个trie节点中有效元素的位置参数和计数器来搜索新节点的前任和后继节点。如果从前任到后继的按顺序遍历包含任何已删除的节点，则选择一个排名最低的节点并重用它。否则选择前任或后继，并向其添加一个新的子节点（前任的右子节点或后继的左子节点）。然后更新从该节点到根的路径上所有有效元素的计数器，并添加相应的哈希映射条目。
查找操作从哈希映射中获取一个位字符串，并使用它从特里根到相应的节点，同时对该路径左侧的所有有效元素的计数器求和。
如果插入/删除序列足够随机，所有这些都允许每个操作的 O(log n) 预期时间。如果不是，则每个操作的最坏情况复杂度为 O(n)。为了让它回到 O(log n) 摊销复杂度，注意树的稀疏和平衡因素，如果删除的节点太多，重新创建一个新的完美平衡和密集的树；如果树太不平衡，重建最不平衡的子树。
可以使用一些二叉搜索树或任何字典数据结构来代替哈希映射。代替位串，用于在trie中标识路径，hash map可以存储指向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 个相对较小的连续内存块，并具有良好的矢量化可能性。如果我们需要良好的最坏情况复杂性，这也会限制内存需求。