5
$\begingroup$

In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store max but not min recursively. Why store max recursively?

If it is not stored recursively, insert(V, x) can take advantage of the special case where a cluster or summary contains one element (min = max), although I think the advantage gained from this is insignificant. Keith Schwarz implements it this way in his Archive of Interesting Code. So why do CLRS and Erik not make use of this optimization in the algorithm? Is it actually a mistake?

$\endgroup$
1
  • $\begingroup$ why not store min recursively? $\endgroup$ Sep 18, 2015 at 13:43

1 Answer 1

1
$\begingroup$

take a look here he explains what you are saying , the theory does not guarantee the algorithm performance so what you pointed at to be weird is not but it is equivalent both cases and give the same $O(\log \log (u) )$ but it may differ in performance as you said .

$\endgroup$
3
  • $\begingroup$ After further testing I realized that my claim about improved performance is false, so I edited it out of the original question. $\endgroup$ Jun 2, 2013 at 0:11
  • $\begingroup$ I didn't understand you well then , I think that you prefer to save recursive calls ! $\endgroup$ Jun 2, 2013 at 5:22
  • $\begingroup$ The link is broken: cs.haifa.ac.il/~oren/Courses/etgar11/lecture1.pdf Internet Archive haven't indexed it. $\endgroup$
    – ptyshevs
    Jan 2, 2020 at 12:38

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.