Binary tree to get minimum element in O(1)

Question

I'm accessing the minimum element of a binary tree lots of times. What implementations allow me to access the minimum element in constant time, rather than O(log n)?

Answer 1

Depending on your other requirements, a min-heap might be what you are looking for. It gives you constant time retrieval of the minimum element.

However you cannot do some other operations with the same ease as with a simple binary search tree, like determining if a value is in the tree or not. You can take a look at splay trees, a kind of self-balancing binary tree that provides improved access time to recently accessed elements.

Answer 2

Find it once in O(log n) and then compare new values which you are going to add with this cached minimum element.

UPD: about how can this work if you delete the minimum element. You'll just need to spend O(log n) one more time and find new one.

Let's imagine that you have 10 000 000 000 000 of integers in your tree. Each element needs 4 bytes in memory. In this case all your tree needs about 40 TB of harddrive space. Time O (log n) which should be spent for searching minimum element in this huge tree is about 43 operations. Of course it's not the simplest operations but anyway it's almost nothing even for 20 years old processors.

Of course this is actual if it's a real-world problem. If for some purposes (maybe academical) you need real O(1) algorithm then I'm not sure that my approach can give you such performance without using additional memory.