performance - 有没有办法在 O(1) 中找到最大值并在 O(lgN) 中查找？

Question

假设您有很多(键，值)对象要跟踪，有很多插入和删除。

您需要满足 3 个要求:

1. 获取任意时刻恒定时间内的最大 key
2. 以对数时间查找任何键的值。
3. 插入和删除需要对数时间。

是否有一种数据结构可以做到这一点？

我的想法:

优先级队列可以在恒定时间内获得最大值，但我无法查找值。二叉搜索树(2-3 棵树)可以在对数时间内查找，但 max 也需要 O(lgN)。如果我试图跟踪 BST 中的最大值，当我必须删除最大值并找到第二大时，它需要 O(lgN)。

Answer 1

为什么我们需要那些花哨的数据结构？我认为跟踪最大节点的简单二叉搜索树可以很好地满足 OP 的要求。

1. 您可以使用最大键跟踪节点:

   每当你插入一个新节点时，你将key与之前的max key进行比较，以决定这是否是一个新的max节点

   每当删除最大节点时，找到下一个最大节点需要O(logN)

2. 你肯定有 O(logN) 查找时间与 BST 的性质

3. BST 的更新需要 O(logN) 时间