binary-search-treemin-heapmax-heapminmax-heap

Is finding the min/max of BST considered to be O(1) time?


I was building a queue using a BST, but I realized that a min/max heap might be better. However, a BST might work, since if we store a reference to head/tail in the BST, then lookup is very close to O(1)..for example:

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

if we have a reference to head element = (1), then if (1) has no right child, that its parent (2) is next smallest. Otherwise, if (1) has a right child, then the distance to find that right child should only be 1 or 2 elements.

So I have some questions:

  1. is finding min/max in a BST considered O(1)?
  2. is there an advantage to building a queue with a min heap or max heap that a BST cannot accomplish?
  3. Is a minmax-heap the same as a BST?

I have some requirements:

  1. find smallest (and ideally also largest) in O(1)
  2. be able to insert/delete from middle of queue in <= log(n) time

Somehow, heaps seem to be implemented with arrays underneath, but I don't understand how to do inserts/deletes from middle of structure in O(1) time.


Solution

  • By caching the min/max values in a BST as you proposed, find would indeed be O(1). The reason it's not normally considered O(1) is because we assume there is only a reference to the root node.

    The min-max heap is very close to satisfying both requirements, possibly with the exception of deleting from the middle (I'm not sure how the tree rotation would work in that case). An AVL tree will definitely satisfy requirement #2. So caching the min/max combined with an AVL tree would satisfy both requirements.

    Since an AVL tree is a type of BST, you could indeed claim that a minmax-heap is the same as a BST in the sense that they can achieve the same time complexity in their operations.