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?

Improve this question
$\endgroup$
  • $\begingroup$ why not store min recursively? $\endgroup$ – Charlie Parker Sep 18 '15 at 13:43
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 .

Improve this answer
$\endgroup$
  • $\begingroup$ After further testing I realized that my claim about improved performance is false, so I edited it out of the original question. $\endgroup$ – Jeremy W. Murphy Jun 2 '13 at 0:11
  • $\begingroup$ I didn't understand you well then , I think that you prefer to save recursive calls ! $\endgroup$ – Fayez Abdlrazaq Deab Jun 2 '13 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 '20 at 12:38

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.