2

我正在寻找一种数据结构，它至少可以确保删除和插入节点的 Log(n) 复杂性以及接近 O(1) 或摊销 Log(n) 的东西来搜索最大值（或最小值）。

我正在考虑使用经过修改的自平衡 BST（哪个？）来记住插入的最大值（或最小值）。

有什么建议吗？

抱歉，我必须编辑问题……当然，自平衡 BST 可以允许在 log(n) 中搜索 max 和 min，但我正在考虑更多关于 O(1) 的东西。

4

5 回答 5

6

您可以使用几乎任何自平衡 BST（例如红黑、AVL）。

如果您跟踪最小值和最大值，则获取它们的查询将花费 O(1)。

由于最小值和最大值只能在插入和删除时改变，因此您基本上可以在执行这些操作时重新确定它（在 O(log n) 中）（它们的运行时间仍然是 O(log n)）。

尽管在收到查询时重新确定最小值或最大值可能是一个更好的主意，并且自上次查询以来存在插入或删除。

也有可能对此更加聪明——如果你到目前为止只向左走，那么你就处于最低限度，如果你只是向右走，那么你就处于最高水平。插入时，只需在适当的情况下替换最小值/最大值。删除时，只需从已删除节点开始在树中四处寻找新的最小值/最大值。

于 2013-10-29T16:33:31.393 回答
1

您可以使用红黑树或AVL 树。

在这里找到最小值-最大值，并删除一个节点O(LogN)。

根据问题的最新编辑，我可以建议您使用可以通过修改的堆栈在 O(1) 中为您提供 O(1) 最小值/最大值、插入和删除的数据结构。如果有兴趣我可以继续。这一切都取决于您的需求，您想要找到最小/最大值的频率，您想要插入的位置，删除所有这些特定元素。

于 2013-10-29T16:23:10.900 回答
1

AVL 适合：搜索 max 和 min 是 O(log n)，因为 min 是最左边的节点，而 max 是最右边的节点，并且树是平衡的。如果您只删除最大/最小节点，这也是 O(log n) 但只有在删除节点时才会使树不平衡。

于 2013-10-29T16:26:39.120 回答
1

我会为此使用跳过列表。您必须稍作修改才能添加尾指针，但除此之外，它可以满足您的所有需求。随着修改：

  • 首先查找是 O(1)
  • 首先删除是 O(1)
  • 查找最后一个是 O(1)
  • 删除最后一个是 O(1)
  • 查找任意节点是 O(log n)
  • 删除任意节点是 O(log n)

跳过列表并不比二叉堆更难实现，而且我记得，它比实现平衡二叉树要容易得多。我能够从原始论文中实现它，它的描述比我见过的大多数学术论文要好得多。

于 2013-10-29T19:08:53.337 回答
0

评论已经讨论了双端堆，并得出结论认为它不适合，因为删除需要知道元素的位置。我相信这可以在许多情况下以合理的成本解决，如下所示：维护两个双端堆，一个（比如 A）条目进入集合，一个（比如 B）条目被删除。

  • 要将元素插入集合中，请将其插入 A。
  • 要从集合中删除元素，请插入 B。
  • 要获取集合的最大值：如果 B 为空，则返回 A 的最大值。否则，令 mA 为 A 的最大值和 B 的 mB。如果 mA > mB，则 mA 未被删除，您可以返回它。如果 mA = mB，则它已被删除，您应该从 A 中弹出 mA，从 B 中弹出 mB，然后从该要点的开头开始。你不能有 mA < mB。
  • 为了得到你的集合中的最小值，以明显的方式调整过程以获得最大值。

这将为您提供 O(log(k)) 插入和删除，并摊销 O(1) 最小/最大计算。但是，在这种情况下，k 是插入到集合中但尚未从 A 和 B 中弹出的元素数；更明显的其他解决方案具有复杂性，具体取决于集合中实际元素的数量（即，已插入但尚未删除的元素） - 我们称这个数字为 n。您可能会想出 k 远大于 n 以至于这与其他解决方案没有竞争力的场景 - 以及 k 和 n 大致相等且此解决方案更快的其他场景。因此，这是否是一个好主意取决于您的应用程序。

于 2013-10-29T19:05:41.890 回答