Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Дерево ван Емде Боаса також відоме як vEB tree це деревоподібна структура даних яка реалізовує асоціативний масив з m ці

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

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

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

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

Операції

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

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

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

Як це працює

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

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

Реалізація, описана вище, використовує вказівники і пам'ять рівну image. Це можна за допомогою рекурентної формули image. , яка приведе нас до image. , що можна записати як image

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

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

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

Див. також

Посилання

  1. : 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. : Dynamic algorithms: Course notes on van Emde Boas trees (PDF) [ 23 вересня 2015 у Wayback Machine.] (, Department of Computer Science)
  3. Rex, A. . Архів оригіналу за 18 березня 2015. Процитовано 27 травня 2011.

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

  • Erik Demaine, Shantonu Sen, and Jeff Lindy. Massachusetts Institute of Technology. 6.897: Advanced Data Structures (Spring 2003). . .
  • P. Emde Boas, R. Kaas, E. Zijlstra Design and implementation of an efficient priority queue // Theory Comput. Syst. — , 1976. — Vol. 10, Iss. 1. — P. 99–127. — ISSN 1432-4350; 1433-0490 — doi:10.1007/BF01683268
    d:Track:Q176916d:Track:Q15753266d:Track:Q56453081
  • Дерево ван Эмде Боаса [ 3 вересня 2016 у Wayback Machine.]


Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Derevo van Emde Boasa takozh vidome yak vEB tree ce derevopodibna struktura danih yaka realizovuye asociativnij masiv z m cilochislovimi klyuchami Vsi operaciyi vikonuyutsya za chas rivnij O log m sho ekvivalentno O log log M de M 2m ce maksimalne chislo elementiv yake mozhna zberigati u comu derevi Ne plutati M z kilkistyu elementiv yaki v danij moment zberigayutsya bo v bilshosti struktur danih shvidkist roboti viznachayetsya same kilkistyu elementiv VEB derevo duzhe efektivne pri roboti z velikoyu kilkistyu elementiv Cya struktura danih bula stvorena grupoyu gollandskih vchenih na choli z Piterom van Emde Boasom u 1975 roci Van Emde Boas tree Tip Ne binarne derevo Data stvorennya 1975 Kim stvorene Van Emde Boas Asimptotichna skladnist Pam yat O M Poshuk O log log M Vstavka O log log M Vidalennya O log log M OperaciyiVEB pidtrimuye operaciyi uporyadkovanogo asociativnogo masivu yakij vklyuchaye v sebe zvichajni asociativni operaciyi masivu razom z she dvoma operaciyami FindNext i FindPrevious Insert vstaviti paru klyuch znachennya z m bitovim klyuchem Delete vidaliti paru klyuch znachennya iz zadanim klyuchem Lookup znajti znachennya pov yazane z zadanim klyuchem FindNext znajti paru klyuch znachennya nastupne pislya zadanogo z najmenshim klyuchem v zadanomu derevi FindPrevious znajti paru klyuch znachennya z najbilshim klyuchem menshim za danij u vidpovidnomu derevi VEB derevo takozh pidtrimuye operaciyi min i max yaki povertayut vidpovidno minimalnij i maksimalnij zi zberezhenih u derevi elementiv Ci dvi operaciyi vikonuyutsya za chas O 1 bo minimalnij i maksimalnij elementi zberigayutsya yak atributi kozhnogo dereva Yak ce pracyuyePriklad dereva Van Emde Boasa vimiru 5 i dopomizhnogo dereva aux pislya vstavki 1 2 3 5 8 i 10 Dlya prostoti prijmemo log2 m k dlya deyakogo cilogo k Viznachimo M 2m Derevo T na mnozhini 0 M 1 maye korenevij vuzol yakij zberigaye masiv T children dovzhini M T children i ye vkazivnikom na derevo VEB yake vidpovidaye za znachennyam i M i 1 M 1 Krim togo derevo T zberigaye she dva znachennya T min i T max a takozh dopomizhne VEB derevo T aux Dani zberigayutsya v derevi VEB nastupnim chinom najmenshe znachennya v danij moment v derevi zberigayetsya v T min najbilshe znachennya zberigayetsya v T max Yaksho T porozhnye to mi beremo T max 1 i T min M Bud yake inshe znachennya h zberigayetsya v pidderevi T children i de i x M displaystyle i left lfloor frac x sqrt M right rfloor Dopomizhne derevo T aux slidkuye chi maye T children siniv tobto T aux mistit znachennya j todi i tilki todi koli T children j ne puste FindNext Operaciya FindNext T x yaka shukaye nastupnij element pislya x u VEB derevi vidbuvayetsya takim chinom yaksho x T min to poshuk bude zaversheno i vidpovid T min Yaksho x gt T max to nastupnij element ne isnuye i povertayetsya M V inshomu vipadku vizmemo i x M Yaksho x T children i max to potribne znachennya mistitsya v T children i tak poshuk trivaye rekursivno v T children i V inshomu vipadku mi shukayemo znachennya i v T aux Ce daye nam indeks j pershogo piddereva sho mistit element bilshij nizh x Algoritm potim povertaye T children j min Element sho znahoditsya na rivni siniv musit buti skladenij z visokimi bitiv shob sformuvati povnij nastupnij element Psevdokod function FindNext T x if x T min then return T min if x gt T max then nema nastupnogo elementa 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 Slid zaznachiti sho v bud yakomu vipadku algoritm vikonuye robotu za O 1 a potim mozhlivo rekursivno na pidderevi na mnozhini rozmiru M1 2 abo na m 2 bitah Ce daye recidiv dlya chasu roboti yakij rivnij T m T m 2 O 1 i robota vikonuyetsya za O log m O log log M Insert Insert T x vstavlyaye znachennya h u VEB derevo T takim chinom Yaksho T porozhnye to mi zberigayemo T min T max x V inshomu vipadku yaksho x lt T min todi vstavlyayemo T min u pidderevo i sho vidpovidaye T min a potim prisvoyuyemo T min x Yaksho T children i bulo puste to mi takozh vstavlyayemo i v T aux V inshomu vipadku yaksho h gt T max todi vstavlyayemo h u pidderevo i vidpovidalnogo za x a potim prisvoyuyemo T max x Yaksho T children i bulo puste to mi takozh vstavlyayemo i v T aux V reshti vipadkiv T min lt x lt T max mi vstavlyayemo x u pidderevo i vidpovidne do x Yaksho T children i puste to mi zberigayemo i v T aux Psevdokod function Insert T x if T min gt T max then T puste T min T max x return if T min T max then if x lt T min then T min x if x gt T max then T max x if x lt T min then swap x T min if x gt 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 Klyuchem do efektivnosti ciyeyi proceduri ye te sho vstavka elementa v porozhnye VEB derevo vimagaye O 1 chasu Takim chinom navit pri tomu sho inodi algoritm robit dva rekursivnih vikliki ce vidbuvayetsya tilki todi koli pershij rekursivnij viklik buv u porozhnogo piddereva Ce daye toj zhe chas vikonannya T M T M 2 O 1 yak i ranishe Delete Vidalennya elementa z VEB derev ce najskladnisha z operacij Delete T h pracyuye takim chinom Yaksho T min T max x to x yedinij element yakij zberigayetsya v derevi todi prisvoyuyemo T min M i T max 1 shob vkazati sho derevo porozhnye V inshomu vipadku yaksho x T min mi povinni znajti druge najmenshe znachennya y v VEB derevi vidaliti jogo z potochnogo miscya i vikonati prisvoyennya T min y Druge najmenshe znachennya y dorivnyuye T max abo T children T aux min min a otzhe jogo mozhna znajti za chas O 1 V ostannomu vipadku mi vidalyayemo u z piddereva sho mistit jogo Analogichnim chinom yaksho x T max to mi povinni znajti druge za velichinoyu znachennya u v VEB derevi i vstanoviti T max y Druge za velichinoyu znachennya y dorivnyuye T min abo T children T aux max max tomu jogo mozhna znajti takozh za chas O 1 Potim takozh vidalyayemo h z piddereva sho mistit jogo U vipadku koli h ne dorivnyuye T min abo T max i T ne maye niyakih inshih elementiv todi mi znayemo sho h ne mistitsya v T i povertayemosya nazad ne vikonuyuchi nichogo V inshomu vipadku mi mayemo tipovij vipadok koli h T min i h T max U comu vipadku mi vidalyayemo h z piddereva T children i yake mistit x U bud yakomu z cih vipadkiv yaksho mi vidalyayemo ostannij element h abo u z bud yakogo z pidderev T children i to mi takozh vidalyayemo i z T aux Psevdokod 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 Znovu zh taki efektivnist ciyeyi proceduri viznachayetsya tim sho vidalennya z dereva VEB yake mistit tilki odin element zajmaye postijnij chas Zokrema ostannij ryadok kodu vikonuyetsya tilki yaksho h buv yedinim elementom u T children i do vidalennya Obgovorennya Pripushennya sho log m yavlyaye soboyu cile chislo ne ye neobhidnim Operaciyi h M i h M mozhna zaminiti vzyavshi stelyu z M 2 i pidlogu nizhchogo poryadku M 2 bitovogo zapisu h vidpovidno Na bud yakij isnuyuchij mashini ce bilsh efektivno nizh obchislennya dilenni i ostachi Realizaciya opisana vishe vikoristovuye vkazivniki i pam yat rivnu O M O 2 m displaystyle O M O 2 m Ce mozhna za dopomogoyu rekurentnoyi formuli S M O M M 1 S M displaystyle S M O sqrt M sqrt M 1 cdot S sqrt M yaka privede nas do S M 1 M log log M log log M O M displaystyle S M in 1 sqrt M log log M log log M cdot O sqrt M sho mozhna zapisati yak S M M 2 displaystyle S M M 2 Pri realizaciyi osoblivo na mashinah zi zsuvom po K produktivnist mozhe buti dodatkovo pokrashena za rahunok perehodu do bitovogo masivu yak tilki m dorivnyuye rozmiru slova Oskilki vsi operaciyi na odnomu slovi vikonuyutsya za postijnij chas ce ne vplivaye na asimptotichnu produktivnist ale dozvolyaye uniknuti zberigannya vkazivnika i kilkoh operacij rozimenuvannya Cej tryuk daye znachnu praktichnu ekonomiyu chasu i pam yati Ochevidno optimizaciya VEB derev polyagaye u vidalenni porozhnih pidderev Ce robit VEB dereva dosit kompaktnimi navit yaksho voni mistyat bagato elementiv tomu sho nemaye neobhidnosti stvoryuvati pidderevo poki ne potribno shos dodati do nogo Spochatku kozhen dodanij element stvoryuye priblizno log m novih derev sho mistyat blizko 2 m vkazivnikiv vsi razom Pri rosti dereva vse bilshe i bilshe pidderev vikoristovuyutsya povtorno osoblivo velikih U povnomu derevi z 2 m elementiv vikoristovuyetsya tilki O 2 m pam yati Krim togo na vidminu vid binarnogo dereva poshuku pam yat v osnovnomu vikoristovuyetsya dlya zberigannya danih navit pri milyardi elementiv v povnomu VEB derevi vkazivnikiv bude blizko tisyachi Tim ne mensh dlya nevelikih derev nakladni vitrati pov yazani z VEB derevami velichezni Ce odna z prichin chomu voni ne koristuyutsya populyarnistyu na praktici Odin iz sposobiv virishennya cogo polyagaye u vikoristanni tilki fiksovanogo chisla bitiv i krim togo kozhna tablicya mozhe buti zaminena na hesh tablicyu zmenshuyuchi vikoristannya pam yati abo na inshi strukturi v tomu chisli prefiksnimi derevami shob zmenshiti vikoristannya pam yati do O N de N ye chislo elementiv sho zberigayutsya v strukturi danih abo do O N log M Div takozhDerevo teoriya grafiv Binarne derevo Binarne derevo poshuku B derevo AVL derevoPosilannya 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 Dynamic algorithms Course notes on van Emde Boas trees PDF 23 veresnya 2015 u Wayback Machine Department of Computer Science Rex A Arhiv originalu za 18 bereznya 2015 Procitovano 27 travnya 2011 Dodatkova literatura Erik Demaine Shantonu Sen and Jeff Lindy Massachusetts Institute of Technology 6 897 Advanced Data Structures Spring 2003 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 Q176916d Track Q15753266d Track Q56453081 Derevo van Emde Boasa 3 veresnya 2016 u Wayback Machine

Дата публікації:
Топ