Дерево ван Емде Боаса

Операція FindNext(T, x) яка шукає наступний елемент після x у ВЕБ дереві, відбувається таким чином: якщо x≤T.min то пошук буде завершено, і відповідь T.min. Якщо x>T.max, то наступний елемент не існує, і повертається М. В іншому випадку, візьмемо i=x/√M. Якщо x≤T.children[i].max то потрібне значення міститься в T.children[i] так пошук триває рекурсивно в T.children[i]. В іншому випадку, ми шукаємо значення і в T.aux. Це дає нам індекс j першого піддерева, що містить елемент більший, ніж x. Алгоритм потім повертає T.children[j].min. Елемент, що  знаходиться на рівні синів мусить бути складений з високими бітів, щоб сформувати повний наступний елемент.

Псевдокод:

 function FindNext(T, x).
    if x ≤ T.min then
        return T.min
    if x > T.max then // нема наступного елемента
        return M
    i = floor(x/sqrt(M))
    lo = x % sqrt(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

Слід зазначити, що, в будь-якому випадку, алгоритм виконує роботу за O (1), а потім, можливо, рекурсивно на піддереві на множині розміру M^1/2 (або на  m/ 2 бітах). Це дає рецидив для часу роботи який рівний T (m) = T (m / 2) + O (1), і робота виконується за  O (log m) = O (log log M).

Іnsert(T, x) вставляє значення х у ВЕБ дерево T  таким чином:

Якщо Т порожнє, то ми зберігаємо T.min = T.max = x.

В іншому випадку, якщо x<T.min тоді вставляємо T.min у піддерево i, що відповідає T.min а потім присвоюємо T.min = x. Якщо T.children [і] було пусте, то ми також вставляємо i в T.aux

В іншому випадку, якщо х> T.max тоді вставляємо х у піддерево i відповідального за x, а потім присвоюємо T.max = x. Якщо T.children[i] було пусте, то ми також вставляємо i в T.aux

В решті випадків, T.min< x < T.max ми вставляємо x у піддерево i відповідне до x. Якщо T.children[i] пусте,то ми зберігаємо i в T.aux.

Псевдокод:

 function Insert(T, x)
    if T.min > T.max then // T пусте
        T.min = T.max = x;
        return
    if T.min == T.max then
        if x < T.min then
            T.min = x
        if x > T.max then
            T.max = x
    if x < T.min then
        swap(x, T.min)
    if x > T.max then
        T.max = x
    i = floor(x / sqrt(M))
    Insert(T.children[i], x % sqrt(M))
    if T.children[i].min == T.children[i].max then
        Insert(T.aux, i)
end

Ключем до ефективності цієї процедури є те, що вставка елемента в порожнє ВЕБ дерево вимагає O (1) часу. Таким чином, навіть при тому, що іноді алгоритм робить два рекурсивних виклики, це відбувається тільки тоді, коли перший рекурсивний виклик був у порожнього піддерева. Це дає той же  час виконання T (M) = T (M / 2) + O (1), як і раніше.

Видалення елемента з ВЕБ дерев -  це найскладніша з операцій. Delete(Т, х), працює таким чином:

Якщо T.min = T.max = x то x - єдиний елемент, який зберігається в дереві, тоді присвоюємо T.min = M і T.max = −1, щоб вказати, що дерево порожнє.

В іншому випадку, якщо x = T.min ми повинні знайти друге-найменше значення y в ВЕБ дереві, видалити його з поточного місця, і виконати присвоєння T.min=y. Друге найменше значення y дорівнює T.max або T.children[T.aux.min].min, а отже його можна знайти за час O(1). В останньому випадку ми видаляємо у з піддерева, що містить його.

Аналогічним чином, якщо x = T.max то ми повинні знайти друге за величиною значення у в ВЕБ дереві і встановити T.max=y. Друге за величиною значення y дорівнює T.min або T.children[T.aux.max].max, тому його можна знайти також за  час  O (1). Потім також видаляємо х з піддерева, що містить його.

У випадку, коли х не дорівнює T.min або T.max, і T не має ніяких інших елементів, тоді ми знаємо що х не міститься в Т і повертаємося назад, не виконуючи нічого.

В іншому випадку, ми маємо типовий випадок, коли х ≠ T.min і х ≠ T.max. У цьому випадку ми видаляємо х з піддерева T.children [і], яке містить x.

У будь-якому з цих випадків, якщо ми видаляємо останній елемент х або у з будь-якого з піддерев T.children [і], то ми також видаляємо і з T.aux

Псевдокод:

 function Delete(T, x)
    if T.min == T.max == x then
        T.min = M
        T.max = -1
        return
    if x == T.min then
        if T.aux is empty then
            T.min = T.max
            return
        else
            x = T.children[T.aux.min].min
            T.min = x
    if x == T.max then
        if T.aux is empty then
            T.max = T.min
            return
        else
            T.max = T.children[T.aux.max].max
    if T.aux is empty then
        return
    i = floor(x / sqrt(M))
    Delete(T.children[i], x % sqrt(M))
    if T.children[i] is empty then
        Delete(T.aux, i)
end

Знову ж таки, ефективність цієї процедури визначається тим, що видалення з дерева ВЕБ, яке містить тільки один елемент займає постійний час. Зокрема, останній рядок коду виконується тільки якщо х був єдиним елементом у T.children [і] до видалення.

Припущення, що log m являє собою ціле число не є необхідним. Операції х / √M і х% √M можна замінити взявши стелю з (M / 2) і підлогу нижчого порядку (M / 2) бітового запису  х відповідно. На будь-якій існуючій машині, це більш ефективно, ніж обчислення діленні і остачі.

Реалізація, описана вище, використовує вказівники і пам'ять рівну ${\displaystyle O(M)=O(2^{m})}$. Це можна за допомогою рекурентної формули ${\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})}$. , яка приведе нас до ${\displaystyle S(M)\in (1+{\sqrt {M}})^{\log \log M}+\log \log M\cdot O({\sqrt {M}})}$. , що можна записати як ${\displaystyle S(M)=M-2}$[3]

При реалізації, особливо на машинах зі зсувом, по-K, продуктивність може бути додатково покращена за рахунок переходу до бітового масиву, як тільки m дорівнює розміру слова  Оскільки всі операції на одному слові виконуються за постійний час, це не впливає на асимптотичну продуктивність, але дозволяє уникнути зберігання вказівника  і кількох операцій розіменування. Цей трюк дає значну практичну економію часу і пам'яті.

Очевидно, оптимізація ВЕБ дерев, полягає у видаленні порожніх піддерев. Це робить ВЕБ дерева досить компактними, навіть якщо вони містять багато елементів, тому що немає необхідності створювати піддерево, поки не потрібно щось додати до нього. Спочатку кожен доданий елемент створює приблизно log(m) нових дерев, що містять близько 2/m вказівників всі разом. При рості дерева, все більше і більше піддерев використовуються повторно, особливо великих. У повному дереві з 2^m елементів, використовується тільки O (2^m) пам'яті. Крім того, на відміну від бінарного дерева пошуку, пам'ять в основному використовується для зберігання даних: навіть при мільярді елементів в  повному ВЕБ дереві вказівників буде близько тисячі.

Тим не менш, для невеликих дерев накладні витрати, пов'язані з ВЕБ деревами величезні. Це одна з причин, чому вони не користуються популярністю на практиці. Один із способів вирішення цього полягає у використанні тільки фіксованого числа бітів, і крім того, кожна таблиця може бути замінена на хеш-таблицю, зменшуючи використання пам'яті, або на інші структури, в тому числі префіксними деревами щоб зменшити використання пам'яті до O (N)(де N є число елементів, що зберігаються в структурі даних) або до O (N log M).