Дерево ван Емде Боаса
| 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=2m це максимальне число елементів, яке можна зберігати у цьому дереві. Не плутати М з кількістю елементів, які в даний момент зберігаються, бо в більшості структур даних швидкість роботи визначається саме кількістю елементів. ВЕБ дерево дуже ефективне при роботі з великою кількістю елементів. Ця структура даних була створена групою голландських вчених на чолі з Пітером ван Емде Боасом у 1975 році.[1]
Операції[ред. | ред. код]
ВЕБ підтримує операції упорядкованого асоціативного масиву, який включає в себе звичайні асоціативні операції масиву разом з ще двома операціями: FindNext і FindPrevious:[2]
- Insert: вставити пару ключ / значення з m-бітовим ключем
- Delete: видалити пару ключ / значення із заданим ключем
- Lookup: знайти значення, пов'язане з заданим ключем
- FindNext: знайти пару ключ / значення наступне після заданого, з найменшим ключем, в заданому дереві
- FindPrevious: знайти пару ключ / значення з найбільшим ключем меншим за даний,у відповідному дереві
ВЕБ дерево також підтримує операції min і max, які повертають відповідно мінімальний і максимальний зі збережених у дереві елементів. Ці дві операції виконуються за час O (1), бо мінімальний і максимальний елементи зберігаються як атрибути кожного дерева.
Як це працює[ред. | ред. код]
Для простоти, приймемо, log2 m = k для деякого цілого k. Визначимо M=2m. Дерево Т на множині {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] де . Допоміжне дерево 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), а потім, можливо, рекурсивно на піддереві на множині розміру M1/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) бітового запису х відповідно. На будь-якій існуючій машині, це більш ефективно, ніж обчислення діленні і остачі.
Реалізація, описана вище, використовує вказівники і пам'ять рівну . Це можна за допомогою рекурентної формули . , яка приведе нас до . , що можна записати як [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
- Дерево ван Эмде Боаса [Архівовано 3 вересня 2016 у Wayback Machine.]
| |||||||||||||||||