具有摊销O(1)删除和O(log n)搜索的数据结构

它可以是一对数据结构:

• 二进制搜索树,保存值
• 哈希表,包含指向二进制搜索树中节点的指针

要搜索时,请在O(log n)时间内在二进制搜索树中进行搜索。 当您要删除时,首先在哈希表中的摊销O(1)中找到节点,然后在二进制搜索树中的摊销O(1)中删除节点。

如果您的范围合理限制在 m ,您可以实现 Y-fast trie 。这支持在中删除和搜索后续项 O(log log m) 时间和花费 O(n) 空间

您也可以使用 k 尝试使用相同的 m级 作为带偏移量的桶,以表示范围 km 。

如果删除的数量与范围相比较小,则只保存删除的内容,而不保存可用的数量。

另一种解决方案是从最初为空的哈希集开始。当有人请求删除时,将该值添加到哈希集。这就是O(1)。

之后有几种方法可以继续。

1. 搜索项目时,如果遇到值位于哈希集中的节点,请将其标记为已删除,然后继续搜索。您从未从树中删除任何内容,但标记为已删除的节点将不再“找到”您只需返回顺序更高的继承者。
2. 找到已搜索的项目后,请检查哈希集以查看该项目是否应被删除。删除该项并按顺序返回其后续项。
3. 搜索树时,每当遇到值位于哈希集中的节点时,请删除该节点并继续搜索。

当然,只要将节点标记为已删除或从树中删除节点,就可以从哈希集中删除该值。

这三种方法都提供了O(log n)搜索,并在搜索过程中分摊删除成本。