algorithm - 具有最小值、最早值和键频率的数据结构

Question

我正在处理数据结构测试中的一个问题，我需要建议一个符合以下要求的数据结构 S:

注意:S 应允许插入具有相同键的多个值

• INSERT(S, k): 将带有键k的对象随时间插入S 复杂度O(lg n)
• DELETE_OLD(S):删除S中最旧的对象，时间复杂度 O(lg n)
• DELETE_OLD_MIN(S):删除具有最低键的最旧对象 在 S 中，时间复杂度 O(lg n)
• MAX_COUNT(S):返回频率最大的key(most S) 中的公钥，时间复杂度 O(lg n)
• FREQ_SUM(S,z):在 S 中找到两个键(a 和 b)使得 frequency.a + frequency.b = z 时间复杂度 O(lg n)

我尝试了一些想法，但无法通过最后两个。

编辑:问题 A data structure traversable by both order of insertion and order of magnitude不回答我的问题。请不要将其标记为重复。谢谢。

编辑 #2:freq_sum(S,z) 的示例:

假设一个调用 freq_sum(S,5) 的数据结构包含:2, 2, 2, 3, 4, 4, 4, 5, 5

2 和 5 的组合可能是一个可能的答案，因为 2 在结构中存在 3 次而 5 存在 2 次，所以 3+2=z

Answer 1

你可以使用 Red-Black来完成这个。

红黑树是非常快的数据结构，符合您上面所述的要求(最后两个需要对结构进行轻微修改)。

您只需允许重复键，因为红黑树遵循二叉搜索树的属性。 Here is an example允许重复键的 BST

红黑树足以维持运行时间:

• 搜索:O(log N)
• 插入:O(log N)
• 删除:O(log N)
• 空间:O(N)

编辑: 你可以实现一个 Self-Balancing Binary Tree ，经过修改以允许重复键并找到最旧的键(参见上面的引用)。在此基础上，Splay Tree可以通过 O(log N)

的分摊运行时间满足您的所有要求

求FREQ_SUM(S,z):
由于搜索以 O(log N) 的摊销时间运行，并且您正在搜索树中的 2 个节点，因此您最终的运行时间为 O(2*log N)。但是在考虑运行时时，忽略标量常量；您的运行时间为 O (log N)。然后您找到节点 'z'，其运行时间为 O(log N)；

这是使用二叉搜索树进行搜索的基本运行时，Splay 树正是基于二叉搜索树构建的。

通过使用拆分 操作，您可以返回两棵新树:一棵包含所有小于或等于 x 的元素，另一棵包含所有大于 x 的元素。