track of which children are non-empty, so contains the value j if and only if is non-empty. FindNext The operation that searches for the successor of an element x in a vEB tree proceeds as follows: If then the search is complete, and the answer is . If then the next element does not exist, return M. Otherwise, let . If then the value being searched for is contained in so the search proceeds recursively in . Otherwise, we search for the successor of the value i in . This gives us the index j of the first subtree that contains an element larger than x. The algorithm then returns . The element found on the children level needs to be composed with the high bits to form a complete next element. function FindNext(T, x) if x < T.min then return T.min if x ≥ T.max then // no next element return M i = floor(x/) lo = x mod if lo < T.children[i].max then return ( i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) return ( j) + T.children[j].min end Note that, in any case, the algorithm performs work and then possibly recurses on a subtree over a universe of size (an bit universe). This gives a recurrence for the running time of , which resolves to . Insert The call that inserts a value into a vEB tree operates as follows: If T is empty then we set and we are done. Otherwise, if then we insert into the subtree responsible for and then set . If was previously empty, then we also insert into Otherwise, if then we insert into the subtree responsible for and then set . If was previously empty, then we also insert into Otherwise, so we insert into the subtree responsible for . If was previously empty, then we also insert into . In code: function Insert(T, x) if T.min > T.max then // T is empty T.min = T.max = x; return if x < T.min then swap(x, T.min) if x > T.max then T.max = x i = floor(x / ) lo = x mod Insert(T.children[i], lo) if T.children[i].min == T.children[i].max then Insert(T.aux, i) end The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes time. So, even though the algorithm sometimes makes two recursive calls, this only occurs when the first