recursive call was into an empty subtree. This gives the same running time recurrence of as before. Delete Deletion from vEB trees is the trickiest of the operations. The call that deletes a value x from a vEB tree T operates as follows: If then x is the only element stored in the tree and we set and to indicate that the tree is empty. Otherwise, if then we need to find the second-smallest value y in the vEB tree, delete it from its current location, and set . The second-smallest value y is , so it can be found in time. We delete y from the subtree that contains it. If and then we delete x from the subtree that contains x. If then we will need to find the second-largest value y in the vEB tree and set . We start by deleting x as in previous case. Then value y is either or , so it can be found in time. In any of the above cases, if we delete the last element x or y from any subtree then we also delete i from . In code: function Delete(T, x) if T.min == T.max == x then T.min = M T.max = −1 return if x == T.min then hi = T.aux.min * j = T.aux.min T.min = x = hi + T.children[j].min i = floor(x / ) lo = x mod Delete(T.children[i], lo) if T.children[i] is empty then Delete(T.aux, i) if x == T.max then if T.aux is empty then T.max = T.min else hi = T.aux.max * j = T.aux.max T.max = hi + T.children[j].max end Again, the efficiency of this procedure hinges on the fact that deleting from a vEB tree that contains only one element takes only constant time. In particular, the second Delete call only executes if x was the only element in prior to the deletion. Discussion The assumption that is an integer is unnecessary. The operations and can be replaced by taking only higher-order and the lower-order bits of , respectively. On any existing machine, this is more efficient than division or remainder computations. In practical implementations, especially on machines with shift-by-k and find first zero instructions, performance can further be improved by switching to a bit array once equal to the word size (or a small multiple thereof) is reached. Since all operations on a single word are