Van Emde Boas träd

van Emde Boas träd
Typ	Icke-binärt träd
Uppfunnet	1975
Uppfunnet av	Peter van Emde Boas
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Plats O ( M ) O ( M ) Sök O (logg log M ) O (logg log M ) Föra in O (logg log M ) O (logg log M ) Radera O (logg log M ) O (logg log M )

Ett van Emde Boas-träd ( holländskt uttal: [vɑn ˈɛmdə ˈboːɑs] ), även känt som ett vEB-träd eller van Emde Boas prioritetskö , är en träddatastruktur som implementerar en associativ array med m -bitars heltalsnycklar. Den uppfanns av ett team ledd av den holländska datavetaren Peter van Emde Boas 1975. Den utför alla operationer i O (log m ) tid (förutsatt att en m bit operation kan utföras i konstant tid), eller motsvarande i O (log m ) log M ) tid, där M = 2 ^m är det största elementet som kan lagras i trädet. Parametern M ska inte förväxlas med det faktiska antalet element som är lagrade i trädet, med vilket prestandan hos andra träddatastrukturer ofta mäts.

vEB-trädet har dålig utrymmeseffektivitet. Till exempel, för att lagra 32-bitars heltal (dvs. när m =32 ) kräver det M =2 ³² bitars lagring. Liknande datastrukturer med lika bra tidseffektivitet och utrymme O ( n ) existerar dock, där n är antalet lagrade element.

Operationer som stöds

En vEB stöder operationerna för en ordnad associativ array , som inkluderar de vanliga associativa arrayoperationerna tillsammans med ytterligare två orderoperationer , FindNext och FindPrevious :

• Infoga : infoga ett nyckel/värdepar med en m -bit nyckel
• Ta bort : ta bort nyckel/värdeparet med en given nyckel
• Uppslag : hitta värdet som är associerat med en given nyckel
• FindNext : hitta nyckel/värdeparet med den minsta nyckeln som är större än ett givet k
• FindPrevious : hitta nyckel/värdeparet med den största nyckeln som är mindre än ett givet k

Ett vEB-träd stöder också operationerna Minimum och Maximum , som returnerar det minsta och maximala elementet som är lagrat i trädet. Dessa körs båda i O (1) tid, eftersom minimum och maximum element lagras som attribut i varje träd.

Fungera

Ett exempel av Emde Boas-träd med dimension 5 och rotens aux-struktur efter 1, 2, 3, 5, 8 och 10 har infogats.

För enkelhetens skull, låt log ₂ m = k för något heltal k . Definiera M = 2 ^m . Ett vEB-träd T över universum {0, ..., M −1 } har en rotnod som lagrar en array T.children med längden √ M . T.children[i] är en pekare till ett vEB-träd som är ansvarigt för värdena { i √ M , ..., ( i +1) √ M −1 }. Dessutom lagrar T två värden T.min och T.max samt ett extra vEB-träd T.aux .

Data lagras i ett vEB-träd enligt följande: Det minsta värdet för närvarande i trädet lagras i T.min och det största värdet lagras i T.max . Observera att T.min inte lagras någon annanstans i vEB-trädet, medan T.max är det. Om T är tomt så använder vi konventionen att T.max=−1 och T.min=M . Alla andra värden x lagras i underträdet T.children[i] där i = ⌊ x / √ M ⌋ . Hjälpträdet T.aux håller reda på vilka barn som inte är tomma, så T.aux innehåller värdet j om och endast om T.children[j] är icke-tom.

Hitta nästa

Operationen FindNext(T, x) som söker efter efterföljaren till ett element x i ett vEB-träd fortsätter enligt följande: Om x <T.min är sökningen klar, och svaret är T.min . Om x≥T.max då nästa element inte existerar, returnera M. Annars låter du i = ⌊ x / √ M ⌋ . Om x<T.children[i].max så finns värdet som söks efter i T.children[i] så sökningen fortsätter rekursivt i T.children[i] . Annars söker vi efter efterföljaren till värdet i i T.aux . Detta ger oss index j för det första underträdet som innehåller ett element som är större än x . Algoritmen returnerar sedan T.children[j].min . Elementet som finns på barnnivån måste komponeras med de höga bitarna för att bilda ett komplett nästa element.

         
        
    
    
         funktion  FindNext(T, x)  om  x < T.min  returnerar  sedan  T.min  om  x ≥ T.max  då  // inget nästa element  returnerar  M i = floor(x/  √  M  ) lo = x mod  √  M  om  lo < T.children[i].max  returnerar  sedan  (  √  M  i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i)  returnerar  (  √  M  j) + T.children[j] .min  slut 

Observera att algoritmen i alla fall utför M ^{1/2 . O} ( 1) arbete och sedan eventuellt återkommer på ett underträd över ett universum med storleken (ett m / 2 bitars universum) Detta ger en upprepning för körtiden av ${\displaystyle T(m)=T(m/2)+O(1)} ,$ vilket löser sig till O (log m ) = O (log log M ) .

Föra in

Anropsinfogningen (T, x) som infogar ett värde x i ett vEB-träd T fungerar enligt följande:

1. Om T är tomt så sätter vi T.min = T.max = x och vi är klara.
2. Annars, om x<T.min så infogar vi T.min i underträdet i som ansvarar för T.min och sätter sedan T.min = x . Om T.children[i] tidigare var tom, så infogar vi även i i T.aux
3. Annars, om x>T.max så infogar vi x i underträdet i som är ansvarigt för x och sätter sedan T.max = x . Om T.children[i] tidigare var tom, så infogar vi även i i T.aux
4. Annars är T.min< x < T.max så vi infogar x i underträdet i ansvarig för x . Om T.children[i] tidigare var tom, så infogar vi även i i T.aux .

I koden:

 
     funktion  Infoga(T, x)  om  T.min > T.max  då  // T är tomt  T.min = T.max = x;  returnera  om  x < T.min  så  byt(x, T.min)  om  x > T.max  då  T.max = x i = golv(x /  √  M  ) lo = x mod  √  M  Insert(T.children[i] , lo)  om  T.children[i].min == T.children[i].max  så  Insert(T.aux, i)  end 

Nyckeln till effektiviteten av denna procedur är att det tar O (1) tid att infoga ett element i ett tomt vEB-träd. Så även om algoritmen ibland gör två rekursiva anrop, inträffar detta bara när det första rekursiva anropet var i ett tomt underträd. Detta ger samma gångtid återkommande av $T(m)=T(m/2)+O(1)$ som tidigare.

Radera

Radering från vEB-träd är den svåraste av operationerna. Anropet Delete(T, x) som tar bort ett värde x från ett vEB-träd T fungerar enligt följande:

1. Om T.min = T.max = x så är x det enda elementet som är lagrat i trädet och vi sätter T.min = M och T.max = −1 för att indikera att trädet är tomt.
2. Annars, om x == T.min måste vi hitta det näst minsta värdet y i vEB-trädet, ta bort det från dess nuvarande plats och ställa in T.min=y . Det näst minsta värdet y är T.children[T.aux.min].min , så det kan hittas i O (1) tid. Vi tar bort y från underträdet som innehåller det.
3. Om x≠T.min och x≠T.max så tar vi bort x från underträdet T.children[i] som innehåller x .
4. Om x == T.max måste vi hitta det näst största värdet y i vEB-trädet och sätta T.max=y . Vi börjar med att radera x som i tidigare fall. Då är värdet y antingen T.min eller T.children[T.aux.max].max , så det kan hittas i O (1) tid.
5. I något av ovanstående fall, om vi tar bort det sista elementet x eller y från något underträd T.children[i] så tar vi också bort i från T.aux .

I koden:

    
         funktion  Delete(T, x)  om  T.min == T.max == x  så  T.min = M T.max = −1  returnera  om  x == T.min  då  hi = T.aux.min *  √  M  j = T.aux.min T.min = x = hej + T.barn[j].min i = våning(x /  √  M  ) lo = x mod  √  M  Radera(T.barn[i], lo)  om  T.children[i] är tom  så  Ta bort(T.aux, i)  om  x == T.max  och  om  T.aux är tom  så är   T.max = T.min  annars  hi = T.aux.max *  √  M  j = T.aux.max T.max = hi + T.barn[j].max  slut 

Återigen beror effektiviteten av denna procedur på det faktum att radering från ett vEB-träd som bara innehåller ett element tar bara konstant tid. I synnerhet körs det andra Delete-anropet endast om x var det enda elementet i T.children[i] före raderingen.

Diskussion

Antagandet att log m är ett heltal är onödigt. Operationerna $x{\sqrt {M}}$ och $x{\bmod {\sqrt {M}}}$ kan ersättas genom att endast ta högre ordning ⌈ m /2⌉ och de lägre ordningens ⌊ m /2⌋ bitarna av x , respektive. På vilken befintlig maskin som helst är detta mer effektivt än divisions- eller restberäkningar.

I praktiska implementeringar, särskilt på maskiner med shift-by-k och hitta första noll- instruktioner, kan prestandan förbättras ytterligare genom att byta till en bitarray när m lika med ordstorleken (eller en liten multipel därav) har nåtts. Eftersom alla operationer på ett enstaka ord är konstant tid, påverkar detta inte den asymptotiska prestandan, men det undviker majoriteten av pekarlagringen och flera pekarereferenser, vilket ger en betydande praktisk besparing i tid och utrymme med detta trick.

En uppenbar optimering av vEB-träd är att kassera tomma underträd. Detta gör vEB-träd ganska kompakta när de innehåller många element, eftersom inga underträd skapas förrän något behöver läggas till dem. Inledningsvis skapar varje element som läggs cirka log( m ) nya träd som innehåller cirka m /2 pekare tillsammans. I takt med att trädet växer återanvänds fler och fler underträd, särskilt de större. I ett fullt träd av M element används endast O( M ) mellanslag. Dessutom, till skillnad från ett binärt sökträd, används det mesta av detta utrymme för att lagra data: även för miljarder element är pekarna i ett fullt vEB-träd i tusental.

Implementeringen som beskrivs ovan använder pekare och upptar ett totalt utrymme på O ( M ) = O (2 ^m ) , proportionell mot storleken på nyckeluniversumet. Detta kan ses på följande sätt. Upprepningen är $S(M)=O({\sqrt {M}})+({\sqrt {M}} +1)\cdot S({\sqrt {M}})$ . En lösning som skulle leda till $S(M)\in (1+{\sqrt {M}} )^{\log \log M}+\log \log M\cdot O({\sqrt {M}})$ . Man kan lyckligtvis också visa att S ( M ) = M −2 genom induktion.

Liknande strukturer

O . ( M ) utrymmesanvändningen för vEB-träd är en enorm overhead om inte en stor del av universum av nycklar lagras Detta är en anledning till att vEB-träd inte är populära i praktiken. Denna begränsning kan åtgärdas genom att ändra arrayen som används för att lagra barn till en annan datastruktur. En möjlighet är att endast använda ett fast antal bitar per nivå, vilket resulterar i ett försök . Alternativt kan varje array ersättas av en hash-tabell , vilket reducerar utrymmet till O ( n ) (där n är antalet element lagrade i datastrukturen) på bekostnad av att göra datastrukturen slumpmässig. Andra datastrukturer inklusive x-snabb-försök och y-snabb-försök har jämförbara uppdaterings- och frågetider som vEB-träd och använder även randomiserade hashtabeller för att minska utrymmet till O ( n log M ) respektive O ( n ) .

Genomföranden

Det finns en verifierad implementering i Isabelle (proof assistant) . Både funktionell korrekthet och tidsgränser är bevisade. Effektiv imperativ Standard ML -kod kan genereras.

Se även

• Heltalssortering
• Föregångarens problem
• Fusionsträd
• Tangoträd

Vidare läsning

• Erik Demaine, Sam Fingeret, Shravas Rao, Paul Christiano. Massachusetts Institute of Technology. 6.851: Avancerade datastrukturer (våren 2012). Föreläsning 11 anteckningar . 22 mars 2012.
• van Emde Boas, P. ; Kaas, R.; Zijlstra, E. (1976). "Design och implementering av en effektiv prioriteringskö". Matematisk systemteori . 10 : 99–127. doi : 10.1007/BF01683268 .