TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know whether it works or not.
In particular:
In Section 20.2.1 of CRLS, the book introduces a "proto" Van Emde Boas (vEB) structure that has some, but all, of the features of true vEB trees. At the end of the section, it says
The DELETE operation is more complicated than insertion. Whereas we can always set a summary bit to 1 when inserting, we cannot always reset the same summary bit to 0 when deleting. We need to determine whether any bit in the appropriate cluster is 1. As we have defined proto-vEB structures, we would have to examine all $\sqrt u$ bits within a cluster to determine whether any of them are 1.
However, that last claim seems dubious, since the summary structure itself already tells you that information, so that you don't have to "examine all $\sqrt u$ bits within a cluster to determine whether any of them are 1."
In particular, exercise 20.2-2 asks for an implementation of PROTO-vEB-DELETE that "scans related bits within the cluster". The following seems to work in O(lg u) time without scanning any bits, except in the base case of V.n == 2! Of course the true vEB tree has O(lg lg u) deletion, so the below is still inferior to that.
PROTO-vEB-DELETE(V, x)
if V.n == 2
V.A[x] = 0
return V.A[1-x] == 0
else
return PROTO-vEB-DELETE(V.A[high(x)], low(x))
&& PROTO-vEB-DELETE(V.summary, high(x))
PROTO-vEB-DELETE(V, x) deletes element x from the vEB structure V, and returns TRUE if and only if the deletion of x caused V to become completely empty. This algorithm seems to have complexity $T(u) = 2 T(\sqrt u) + O(1)$, which becomes $T(u) = O(\lg u)$. Does this algorithm actually work?
