2
$\begingroup$

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
end

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.