是否认为找到最小/最大的BST是O(1)时间?

Question

我正在使用BST构建队列，但我意识到最小/最大堆可能更好。然而，BST可能会起作用，因为如果我们在BST中存储对head/tail的引用，那么查找非常接近O(1)。例如:

(5)
/   
(3)   (6)
/      
(2) (4)   (7)
/
(1)

如果有对head element =(1)的引用，则如果(1)没有右子元素，则它的父元素(2)是次小的。否则，如果(1)有右子元素，那么找到右子元素的距离应该只有1或2个元素。

所以我有一些问题:

1. 正在寻找最小/最大的BST考虑O(1)?
2. 用最小堆或最大堆构建队列是否有BST无法完成的优势?
3. 是一个最小最大堆相同的BST?

我有一些要求:

1. 在O(1)
中找到最小的(最好也是最大的)
2. 能够在<= log(n) time
中插入/删除队列

不知何故，堆似乎是用数组来实现的，但我不明白如何在O(1)时间内从结构的中间进行插入/删除。

Answer 1

通过在BST中缓存最小/最大值，find确实是0(1)。它通常不被认为是O(1)的原因是因为我们假设只有一个对根节点的引用。

最小-最大堆非常接近于满足这两个要求，可能除了从中间删除(我不确定在这种情况下树旋转将如何工作)。AVL树肯定能满足需求2。因此，将最小/最大缓存与AVL树相结合将满足这两个需求。

由于AVL树是BST的一种，你确实可以声称最小最大堆与BST在某种意义上是相同的，因为它们在操作中可以实现相同的时间复杂度。