PROFILBARU.COM

Van Emde Boas tree
Тип	Не бінарне дерево
Дата створення	1975
Ким створене	Ван Емде Боас
Асимптотична складність
Пам'ять	O(M)
Пошук	O(log log M)
Вставка	O(log log M)
Видалення	O(log log M)

Дерево ван Емде Боаса (також відоме як vEB tree) — це деревоподібна структура даних, яка реалізовує асоціативний масив з m- цілочисловими ключами. Всі операції виконуються за час рівний O(log m), що еквівалентно O(log log M), де M=2^m це максимальне число елементів, яке можна зберігати у цьому дереві. Не плутати М з кількістю елементів, які в даний момент зберігаються, бо в більшості структур даних швидкість роботи визначається саме кількістю елементів. ВЕБ дерево дуже ефективне при роботі з великою кількістю елементів. Ця структура даних була створена групою голландських вчених на чолі з Пітером ван Емде Боасом у 1975 році.^[1]

Операції

ВЕБ підтримує операції упорядкованого асоціативного масиву, який включає в себе звичайні асоціативні операції масиву разом з ще двома операціями: FindNext і FindPrevious:^[2]

Insert: вставити пару ключ / значення з m-бітовим ключем
Delete: видалити пару ключ / значення із заданим ключем
Lookup: знайти значення, пов'язане з заданим ключем
FindNext: знайти пару ключ / значення наступне після заданого, з найменшим ключем, в заданому дереві
FindPrevious: знайти пару ключ / значення з найбільшим ключем меншим за даний,у відповідному дереві

ВЕБ дерево також підтримує операції min і max, які повертають відповідно мінімальний і максимальний зі збережених у дереві елементів. Ці дві операції виконуються за час O (1), бо мінімальний і максимальний елементи зберігаються як атрибути кожного дерева.

Як це працює

Приклад дерева Ван Емде Боаса виміру 5 і допоміжного дерева aux після вставки 1, 2, 3, 5, 8 і 10 .

Для простоти, приймемо, log₂ m = k для деякого цілого k. Визначимо M=2^m. Дерево Т на множині {0,…,M-1} має кореневий вузол, який зберігає масив T.children довжини √M. T.children[i] є вказівником на дерево ВЕБ, яке відповідає за значенням {i√M,...,(i+1)√M-1}. Крім того, дерево T зберігає ще два значення T.min і T.max, а також допоміжне ВЕБ дерево T.aux.

Дані зберігаються в дереві ВЕБ наступним чином: найменше значення в даний момент в дереві зберігається в T.min найбільше значення зберігається в T.max. Якщо Т порожнє, то ми беремо T.max=-1 і T.min=M. Будь-яке інше значення х зберігається в піддереві T.children[i] де $i=\left\lfloor {\frac {x}{\sqrt {M}}}\right\rfloor$ . Допоміжне дерево T.aux слідкує чи має T.children синів, тобто T.aux містить значення j тоді і тільки тоді коли T.children[j] не пусте.

FindNext

Операція 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).

Insert

І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

Видалення елемента з ВЕБ дерев - це найскладніша з операцій. 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) бітового запису х відповідно. На будь-якій існуючій машині, це більш ефективно, ніж обчислення діленні і остачі.

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

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

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

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

Див. також

Посилання

↑ Peter van Emde Boas: Preserving order in a forest in less than logarithmic time (Proceedings of the 16th Annual Symposium on Foundations of Computer Science 10: 75-84, 1975)
↑ Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) [Архівовано 23 вересня 2015 у Wayback Machine.] (University of Aarhus, Department of Computer Science)
↑ Rex, A. Determining the space complexity of van Emde Boas trees. Архів оригіналу за 18 березня 2015. Процитовано 27 травня 2011.

Додаткова література

Erik Demaine, Shantonu Sen, and Jeff Lindy. Massachusetts Institute of Technology. 6.897: Advanced Data Structures (Spring 2003). Lecture 1 notes: Fixed-universe successor problem, van Emde Boas. Lecture 2 notes: More van Emde Boas, ….
P. Emde Boas, R. Kaas, E. Zijlstra Design and implementation of an efficient priority queue // Theory Comput. Syst. — Springer Science+Business Media, 1976. — Vol. 10, Iss. 1. — P. 99–127. — ISSN 1432-4350; 1433-0490 — doi:10.1007/BF01683268
d:Track:Q176916 d:Track:Q15753266 d:Track:Q56453081
Дерево ван Эмде Боаса [Архівовано 3 вересня 2016 у Wayback Machine.]

[1] Peter van Emde Boas: Preserving order in a forest in less than logarithmic time (Proceedings of the 16th Annual Symposium on Foundations of Computer Science 10: 75-84, 1975)

[2] Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) [Архівовано 23 вересня 2015 у Wayback Machine.] (University of Aarhus, Department of Computer Science)

[3] Rex, A. Determining the space complexity of van Emde Boas trees. Архів оригіналу за 18 березня 2015. Процитовано 27 травня 2011.

[1]

[2]

[3]