algorithm - 我应该使用哪种数据结构来进行快速删除/插入和最大(或最小)搜索？

Question

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

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

有什么建议吗？

抱歉，我必须编辑问题...当然，自平衡 BST 可以允许在 log(n) 中搜索最大值和最小值，但我在考虑更接近 O(1) 的东西。

Answer 1

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

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

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

虽然当您收到对其的查询并且自上次查询以来有插入或删除时重新确定最小值或最大值可能是一个更好的主意。

也有可能对此更加明智 - 如果到目前为止您只向左走，那么您处于最小值，如果您只向右走，则您处于最大值。插入时，如果合适，只需替换最小值/最大值。删除时，只需从删除的节点开始在树中环顾四周，找到新的最小值/最大值。