The Wikipedia page for vEB trees (specifically the version from 27 September, 2018), gives the following pseudocode for finding the successor element of x in the vEB tree (of universe of size M):

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/√M)
    lo = x mod √M
    hi = x − lo
    if lo < T.children[i].max then
        return hi + FindNext(T.children[i], lo)
    return hi + T.children[FindNext(T.aux, i)].min

Consider the very last return statement. Shouldn't it instead be

    y = FindNext(T.aux, i)
    return y√M + T.children[y].min

Seems like a bug to me but I wanted to confirm.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.