Van Emde Boas Tree - How IT Works - FindNext

FindNext

The operation FindNext(T, x) that searches for the successor of an element x in a vEB tree proceeds as follows: If x≤T.min then the search is complete, and the answer is T.min. If x>T.max then the next element does not exist, return M. Otherwise, let i=x/M1/2. If x≤T.children.max then the value being searched for is contained in T.children so the search proceeds recursively in T.children. Otherwise, We search for the value i in T.aux. This gives us the index j of the first subtree that contains an element larger than x. The algorithm then returns T.children.min. The element found on the children level needs to be composed with the high bits to form a complete next element.

Note that, in any case, the algorithm performs O(1) work and then possibly recurses on a subtree over a universe of size M1/2 (an m/2 bit universe). This gives a recurrence for the running time of T(m)=T(m/2) + O(1), which resolves to O(log m) = O(log log M).