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$

2 Answers 2

5
$\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$
8
  • $\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$
    – NimaJan
    Commented Jan 13, 2020 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
    Commented Jan 13, 2020 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$
    – NimaJan
    Commented Jan 13, 2020 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
    Commented Jan 14, 2020 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$
    – NimaJan
    Commented Jan 14, 2020 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;
}
$\endgroup$
1
  • $\begingroup$ Very nice explanation! Thanks! I am glad you did a nice research. $\endgroup$
    – NimaJan
    Commented Jan 15, 2020 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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