1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like to know in detail how these are saved and updated as attribute. It it just very vague for me when you say 'they are stored as a attribute'. How does it get updated when a node is inserted? What are the details? $\endgroup$ – NimaKimi Jan 13 at 15:57
  • $\begingroup$ @NimaKimi 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. $\endgroup$ – OmG Jan 13 at 20:07
  • $\begingroup$ So when designing the data structure you will use a variable that automatically gets updated in some way to store the min/max? $\endgroup$ – NimaKimi Jan 13 at 22:03
  • $\begingroup$ @NimaKimi Indeed nothing happens automatically. But it's keeping updated by checking that stored value is greater than the inserted value or not (depends on the min or max case). $\endgroup$ – OmG Jan 14 at 12:37
  • $\begingroup$ Thank for your answer. To summarize it, you can define an attribute by a variable that keeps track of the min/max in each operation you make on the tree. Is this it? $\endgroup$ – NimaKimi Jan 14 at 14:33
1
$\begingroup$

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;
}
New contributor
Geeth Sandaru Madhushan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ Very nice explanation! Thanks! I am glad you did a nice research. $\endgroup$ – NimaKimi 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.