Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?

Question

I have read in the book

"Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (Chapter 20)

that Emde Boas trees run min/max operations in $\mathcal{O}(1)$ time since the minimum and maximum element are stored as attributes in each tree. I don't understand this very well. Does this mean that the min and max values are already given in the input, because the minimum and maximum must be calculated somewhere?

Answer 1

No. They are not given as an input! They were stored and updated as an attribute of each tree(Beware that the concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure). The same situation is taking place in the min[Max]-heap data structure. You can find the minimum [maximum] in a min[max]-heap with $O(1)$ operation by keeping update (in insertion time) the mentioned attribute.

Answer 2

To search the min/max or successor/predecessor, we use a recursive algorithm that goes through the sub-trees and does the search. While the recursion happens, we don't calculate the min/max in every iteration. We have an attribute in an object that we get as an parameter to the recursive function that we use to assign the min/max. In every iteration, if there's a new min/max, then we assign the attribute to the new value so that we are always up-to-date with the min/max and when we need them, we can get them from the attribute which is $O(1)$.

recursiveFunction(metadataObj, x) {

  if x < metadataObj.min:
    metadataObj.min = x;

  if x > metadata.max:
    metadataObj.max = x;
}