Van Emde Boas strom - Van Emde Boas tree

A van Emde Boas strom (Holandská výslovnost: [vɑn 'ɛmdə' boːɑs]), také známý jako a strom vEB nebo van Emde Boas prioritní fronta, je stromová datová struktura který implementuje asociativní pole s m-bitové celé číslo klíče. Provádí všechny operace v Ó (logm) času nebo ekvivalentně v Ó(log logM) čas, kde M = 2^m je maximální počet prvků, které lze uložit do stromu. The M nelze zaměňovat se skutečným počtem prvků uložených ve stromu, kterými se často měří výkon jiných stromových datových struktur. Strom vEB má dobrou efektivitu prostoru, když obsahuje mnoho prvků, jak je popsáno níže. To bylo vynalezeno týmem vedeným holandský počítačový vědec Peter van Emde Boas v roce 1975.^[1]

Podporované operace

VEB podporuje operace objednal asociativní pole, který zahrnuje obvyklé operace asociativního pole spolu se dvěma dalšími objednat operace, Najdi další a NajítPředchozí:^[2]

• Vložit: vložte pár klíč / hodnota s m-bitový klíč
• Vymazat: odebrat pár klíč / hodnota s daným klíčem
• Vzhlédnout: najít hodnotu spojenou s daným klíčem
• Najdi další: najít pár klíč / hodnota s nejmenším klíčem, který je větší než daný k
• NajítPředchozí: najít pár klíč / hodnota s největším klíčem, který je menší než daný k

Tyto operace podporuje také strom vEB Minimální a Maximum, které vrací minimální a maximální prvek uložený ve stromu.^[3] Oba běží Ó(1) čas, protože minimální a maximální prvek jsou uloženy jako atributy v každém stromu.

Jak to funguje

Byl vložen příklad stromu van Emde Boas s rozměrem 5 a aux strukturou kořene po 1, 2, 3, 5, 8 a 10.

Kvůli jednoduchosti dovolte log₂ m = k pro celé číslo k. Definovat M = 2^m. Strom vEB T přes vesmír {0, ..., M−1} má kořenový uzel, který ukládá pole T. děti délky √M. T. děti [i] je ukazatel na strom vEB, který je zodpovědný za hodnoty {i√M, ..., (i+1)√M−1}. Dodatečně, T ukládá dvě hodnoty T.min a T.max stejně jako pomocný strom vEB T.aux.

Data jsou uložena ve stromu vEB následovně: Nejmenší hodnota aktuálně ve stromu je uložena v T.min a největší hodnota je uložena v T.max. Všimněte si, že T.min není uložen nikde jinde ve stromu vEB, zatímco T.max je. Li T je prázdný, pak použijeme konvenci, že T.max = -1 a T.min = M. Jakákoli jiná hodnota X je uložen v podstromu T. děti [i] kde i = ⌊X/√M⌋. Pomocný strom T.aux sleduje, které děti nejsou prázdné, takže T.aux obsahuje hodnotu j kdyby a jen kdyby T.children [j] není prázdný.

Najdi další

Operace FindNext (T, x) který hledá nástupce prvku X ve stromu vEB probíhá takto: Pokud X pak je hledání kompletní a odpověď zní T.min. Li x≥T.max pak další prvek neexistuje, vraťte M. Jinak nechte i = X/√M. Li x pak je hledaná hodnota obsažena v T. děti [i] takže vyhledávání probíhá rekurzivně dovnitř T. děti [i]. Jinak hledáme hodnotu i v T.aux. To nám dává index j prvního podstromu, který obsahuje prvek větší než X. Algoritmus se poté vrátí T. děti [j] .min. Prvek nalezený na podřízené úrovni musí být složen z vysokých bitů, aby vytvořil úplný další prvek.

funkce FindNext (T, x) -li x pak        vrátit se T.min -li x ≥ T.max pak // žádný další prvek        vrátit se M i = podlaha (x /√M) lo = x mod √M        -li lo pak        vrátit se (√M i) + FindNext (T.children [i], lo) j = FindNext (T.aux, i) vrátit se (√M j) + T. děti [j]. minkonec

Všimněte si, že v každém případě algoritmus funguje Ó(1) pracovat a pak se případně opakovat na podstromu ve vesmíru o velikosti M^1/2 (an m/2 bitový vesmír). To dává opakování doby chodu ${ displaystyle T (m) = T (m / 2) + O (1)}$, který řeší na Ó(log m) = Ó(log log M).

Vložit

Volání vložka (T, x) který vloží hodnotu X do stromu vEB T funguje následovně:

1. Li T je prázdný, pak jsme nastavili T.min = T.max = x a jsme hotovi.
2. Jinak, pokud x pak vložíme T.min do podstromu i zodpovědný za T.min a poté nastavit T.min = x. Li T. děti [i] byl dříve prázdný, pak také vložíme i do T.aux
3. Jinak, pokud x> T.max pak vložíme X do podstromu i zodpovědný za X a poté nastavit T.max = x. Li T. děti [i] byl dříve prázdný, pak také vložíme i do T.aux
4. V opačném případě, T.min tak vložíme X do podstromu i zodpovědný za X. Li T. děti [i] byl dříve prázdný, pak také vložíme i do T.aux.

V kódu:

funkce Vložit (T, x) -li T.min> T.max pak // T je prázdný        T.min = T.max = x; vrátit se    -li x pak        swap (x, T.min) -li x> T.max pak        T.max = x i = podlaha (x / √M) lo = x mod √M    Příloha (T.children [i], lo) -li T.children [i] .min == T.children [i] .max pak        Vložit (T.aux, i)konec

Klíčem k efektivitě tohoto postupu je, že vložení prvku do prázdného stromu vEB trvá Ó(1) čas. Takže i když algoritmus někdy provede dvě rekurzivní volání, dojde k tomu pouze v případě, že první rekurzivní volání bylo do prázdného podstromu. To dává stejné opakování doby běhu ${ displaystyle T (m) = T (m / 2) + O (1)}$ jako dříve.

Vymazat

Odstranění ze stromů vEB je nejsložitější z operací. Volání Odstranit (T, x) která vymaže hodnotu X ze stromu vEB T funguje následovně:

1. Li T.min = T.max = x pak X je jediný prvek uložený ve stromu a nastavili jsme T.min = M a T.max = -1 k označení, že strom je prázdný.
2. Jinak, pokud x == T.min pak musíme najít druhou nejmenší hodnotu y ve stromu vEB jej odstraňte z aktuálního umístění a nastavte T.min = r. Druhá nejmenší hodnota y je T.children [T.aux.min] .min, takže jej lze najít v Ó(1) čas. Mazáme y z podstromu, který ho obsahuje.
3. Li x ≠ T.min a x ≠ T.max pak odstraníme x z podstromu T. děti [i] který obsahuje X.
4. Li x == T.max pak budeme muset najít druhou největší hodnotu y ve stromu vEB a nastavit T.max = r. Začneme odstraněním x jako v předchozím případě. Pak hodnota y je buď T.min nebo T. děti [T.aux.max] .max, takže jej lze najít v Ó(1) čas.
5. V kterémkoli z výše uvedených případů, pokud odstraníme poslední prvek X nebo y z jakéhokoli podstromu T. děti [i] pak také smažeme i z T.aux

V kódu:

funkce Odstranit (T, x) -li T.min == T.max == x pak        T.min = M T.max = -1 vrátit se    -li x == T.min pak        ahoj = T.aux.min * √M        j = T.aux.min T.min = x = ahoj + T. děti [j] .min i = podlaha (x / √M) lo = x mod √M    Odstranit (T.children [i], lo) -li T.children [i] je prázdný pak        Odstranit (T.aux, i) -li x == T.max pak        -li T.aux je prázdný pak            T.max = T.min jiný            ahoj = T.aux.max * √M            j = T.aux.max T.max = ahoj + T. děti [j] .maxkonec

Efektivita tohoto postupu opět závisí na skutečnosti, že odstranění ze stromu vEB, který obsahuje pouze jeden prvek, trvá jen konstantní čas. Zejména poslední řádek kódu se provede pouze pokud X byl jediným prvkem v T. děti [i] před odstraněním.

Implementace Pythonu

z matematika import strop, log2"""van Emde Boas Tree je datová struktura, která dává O (log (log (u))čas dotazu pro operace jako vkládat, hledat, mazat, nástupce a předchůdceTřída VEB obsahuje atributmin, max, u, w, shluk a souhrnzpočátku min = max = NULLu = velikost vesmíru (rozsah celkových možných záznamů)w = délka slova (počet bitů v u)w = log2 (u)cluster je pole struktur VEB o velikosti sqrt (u)souhrn je VEB o velikosti sqrt (u)když velikost struktury VEB dosáhne, neukládáme shluky a souhrnný vektorpro uložení této struktury stačí min. a max."""třída VEB:    "" "Index x lze určit jako    číslo klastru a pozice uvnitř klastru    například pojďme zvážit 11    v binárním formátu se píše jako 1011    takže první polovina částí binárního řetězce udává číslo klastru    a druhá polovina dává postiton uvnitř klastru    číslo klastru = int (10) = 2    pozice uvnitř clusteru = int (11) = 3    takže 11 je ve 2. klastru na 3. pozici    kde počítání začíná od 0. pozice    0,1,2,3|4,5,6,7|8,9,10,11|12,13,14,15                           ^    zde používáme 'c' k označení čísla klastru    a „i“ označuje index uvnitř klastru    takže x může být reprezentováno jako     kde x = c * sqrt (u) + i    """    def vysoký(já, X):        # high (x) = x // int (sqrt (u))        vrátit se X >> (já.w // 2)    def nízký(já, X):        # low (x) = x% int (sqrt (u))        vrátit se X & (1 << (já.w // 2)) - 1    def index(já, i, j):        # return i * int (sqrt (self.u)) + j        vrátit se i << (já.w // 2) | j    def __init__(já, u):        """        To byly implementovány pomocí hash tabulky        ke snížení složitosti prostoru z O (U) na O (n * log (log (u))        protože u může být velmi velký. například pokud velikost slova = 64 bitů        u = 2 ^ 64 = 16 milionů TB, které nelze prakticky uložit na RAM.        kde jako n * log * log * u může být O (3n), které lze snadno uložit.        Mám také jiný kód pro implementaci pole.        """        já.w = strop(log2(u))        # self.u = 2 ** self.w        já.min = já.max = Žádný        -li já.w >= 1:  # když u == 2 ^ w = 2 min a max jsou dost, takže zastavíme rekurzi            já.shluk = {}            já.souhrn = Žádný    def člen(já, X):        "" "Funkce pro kontrolu, zda je x ve stromu nebo ne." ""        -li X == já.min nebo X == já.max:            vrátit se Skutečný        elif já.w == 1:            vrátit se Nepravdivé        jiný:            C = já.vysoký(X)            i = já.nízký(X)            -li C v já.shluk:                vrátit se já.shluk[C].člen(i)            jiný:                vrátit se Nepravdivé    def vložit(já, X):        -li já.min je Žádný:            já.min = X            já.max = X            vrátit se        jiný:            -li X < já.min:                X, já.min = já.min, X            C = já.vysoký(X)            i = já.nízký(X)            -li já.w > 1:                -li C ne v já.shluk:                    já.shluk[C] = VEB(2 ** (já.w // 2))                -li já.shluk[C].min je Žádný:                    -li já.souhrn je Žádný:                        já.souhrn = VEB(2 ** (já.w // 2))                    já.souhrn.vložit(C)                -li C ne v já.shluk:                    já.shluk[C] = VEB(2 ** (já.w // 2))                já.shluk[C].vložit(i)            -li X > já.max:                já.max = X    def nástupce(já, X):        -li já.w == 1:            -li X == 0 a já.max == 1:                vrátit se 1            jiný:                vrátit se Žádný        elif já.min je ne Žádný a X < já.min:            vrátit se já.min        jiný:            C = já.vysoký(X)            i = já.nízký(X)            -li C v já.shluk:                max = já.shluk[C].max            jiný:                max = Žádný            -li max je ne Žádný a i < max:                offset = já.shluk[C].nástupce(i)                vrátit se já.index(C, offset)            jiný:                -li já.souhrn je ne Žádný:                    succ_cluster = já.souhrn.nástupce(já.vysoký(X))                jiný:                    succ_cluster = Žádný                -li succ_cluster je Žádný:                    vrátit se Žádný                jiný:                    offset = já.shluk[succ_cluster].min                    vrátit se já.index(succ_cluster, offset)    def předchůdce(já, X):        -li já.w == 1:            -li X == 1 a já.min == 0:                vrátit se 0            jiný:                vrátit se Žádný        elif já.max je ne Žádný a X > já.max:            vrátit se já.max        jiný:            C = já.vysoký(X)            i = já.nízký(X)            -li C v já.shluk:                min_low = já.shluk[C].min            jiný:                min_low = Žádný            -li min_low je ne Žádný a i > min_low:                offset = já.shluk[C].předchůdce(i)                vrátit se já.index(C, offset)            jiný:                -li já.souhrn je ne Žádný:                    předchozí_kupina = já.souhrn.předchůdce(C)                jiný:                    předchozí_kupina = Žádný                -li předchozí_kupina je Žádný:                    -li já.min je ne Žádný a X > já.min:                        vrátit se já.min                    jiný:                        vrátit se Žádný                jiný:                    offset = já.shluk[předchozí_kupina].max                    vrátit se já.index(předchozí_kupina, offset)    def vymazat(já, X):        -li já.min je Žádný:            vrátit se        -li X < já.min nebo X > já.max:            vrátit se        -li já.min == já.max:            já.min = já.max = Žádný        elif já.w == 1:            -li X == 0:                já.min = 1            jiný:                já.min = 0            já.max = já.min        jiný:            C = já.vysoký(X)            i = já.nízký(X)            -li X == já.min:                -li já.souhrn:                    first_cluster = já.souhrn.min                jiný:                    first_cluster = Žádný                -li first_cluster:                    X = já.index(first_cluster, já.shluk[first_cluster].min)                    já.min = X            -li C v já.shluk:                já.shluk[C].vymazat(i)                -li já.shluk[C].min je Žádný:                    já.souhrn.vymazat(C)                -li X == já.max:                    souhrn_max = já.souhrn.max                    -li souhrn_max je Žádný:                        já.max = já.min                    jiný:                        já.max = já.index(souhrn_max, já.shluk[souhrn_max].max)            elif X == já.max:                já.max = já.index(C, já.shluk[C].max)

Diskuse

Předpoklad, že log m je celé číslo je zbytečné. Operace ${ displaystyle x { sqrt {M}}}$ a ${ displaystyle x { bmod { sqrt {M}}}}$ lze nahradit převzetím pouze vyššího řádu ⌈m/2⌉ a nižšího řádu ⌊m/2⌋ kousky X, resp. Na jakémkoli existujícím počítači je to efektivnější než výpočty dělení nebo zbytku.

Implementace popsaná výše používá ukazatele a zabírá celkový prostor Ó(M) = Ó(2^m). To lze vidět následovně. Opakování je ${ displaystyle S (M) = O ({ sqrt {M}}) + ({ sqrt {M}} + 1) cdot S ({ sqrt {M}})}$Řešení, které by vedlo k ${ displaystyle S (M) in (1 + { sqrt {M}}) ^ { log log M} + log log M cdot O ({ sqrt {M}})}$Naštěstí to lze také ukázat S(M) = M−2 indukcí.^[4]

V praktických implementacích, zejména na strojích s shift-by-k a najít první nulu podle pokynů lze výkon dále zlepšit přepnutím na a bitové pole jednou m rovná se velikost slova (nebo jejich malý násobek) je dosaženo. Protože všechny operace na jednom slově jsou konstantní čas, neovlivní to asymptotický výkon, ale vyhneme se většině úložiště ukazatele a několika dereferencím ukazatele, čímž se tímto trikem dosáhne významné praktické úspory času a prostoru.

Zjevnou optimalizací stromů vEB je vyřazení prázdných podstromů. Díky tomu jsou stromy vEB poměrně kompaktní, když obsahují mnoho prvků, protože nejsou vytvářeny žádné podstromy, dokud k nim není třeba něco přidat. Zpočátku každý přidaný prvek vytváří asi log (m) nové stromy obsahující asi m/2 ukazatele dohromady. Jak strom roste, znovu a znovu se používá stále více podstromů, zejména těch větších. V plném stromu 2^m pouze prvky O (2^m) je využito prostoru. Navíc, na rozdíl od binárního vyhledávacího stromu, se většina tohoto prostoru používá k ukládání dat: dokonce i pro miliardy prvků jsou ukazatele na celé číslo stromu vEB v tisících.

U malých stromů je však režie spojená se stromy vEB obrovská: řádově ${ displaystyle { sqrt {M}}}$. To je jeden z důvodů, proč nejsou v praxi populární. Jedním ze způsobů řešení tohoto omezení je použití pouze pevného počtu bitů na úroveň, což má za následek a trie. Alternativně může být každá tabulka nahrazena a hash tabulka, zmenšení prostoru na Ó(n log M) (kde n je počet prvků uložených v datové struktuře) na úkor randomizace datové struktury. Ostatní struktury, včetně y-rychlé pokusy a x-rychlé pokusy byly navrženy, které mají srovnatelné časy aktualizací a dotazů a také používají randomizované hash tabulky ke zmenšení prostoru na Ó(n) nebo Ó(n log M).

Viz také

• Třídění celých čísel
• Problém předchůdce
• Fúzní strom
• Tango strom
• X-rychlá trie
• Y-rychlá trie

Reference

Další čtení