# van Emde Boas tree: why store max recursively?

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?

• why not store min recursively? – Charlie Parker Sep 18 '15 at 13:43

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 .