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?