X-snabb försök
| X-snabb försök | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | Försök | |||||||||||||||
| Uppfunnet | 1982 | |||||||||||||||
| Uppfunnet av | Dan Willard | |||||||||||||||
| Tidskomplexitet i stor O-notation | ||||||||||||||||
| ||||||||||||||||
Inom datavetenskap är en x-fast trie en datastruktur för att lagra heltal från en avgränsad domän. Den stöder exakta och föregångare eller efterföljande frågor i tid O (log log M ), med O ( n log M ) utrymme, där n är antalet lagrade värden och M är det maximala värdet i domänen. Strukturen föreslogs av Dan Willard 1982, tillsammans med det mer komplicerade y-fast försöket , som ett sätt att förbättra utrymmesanvändningen för van Emde Boas-träd, samtidigt som man behåller frågetiden O (logg log M ).
Strukturera
Ett x-snabbt försök är ett bitvis försök : ett binärt träd där varje underträd lagrar värden vars binära representationer börjar med ett gemensamt prefix. Varje intern nod är märkt med det gemensamma prefixet för värdena i sitt underträd och vanligtvis lägger det vänstra barnet till en 0 till slutet av prefixet, medan det högra barnet lägger till en 1. Den binära representationen av ett heltal mellan 0 och M − 1 använder ⌈log 2 M ⌉ bitar, så höjden på trie är O (log M ).
Alla värden i x-fast försöket lagras på bladen. Interna noder lagras endast om de har löv i sitt underträd. Om en intern nod inte skulle ha något vänster underordnat, lagrar den istället en pekare till det minsta bladet i dess högra underträd, en så kallad descendant -pekare. På samma sätt, om den inte skulle ha något rätt barn, lagrar den en pekare till det största bladet i sitt vänstra underträd. Varje blad lagrar en pekare till sin föregångare och efterföljare och bildar därigenom en dubbellänkad lista . Slutligen finns det en hashtabell för varje nivå som innehåller alla noder på den nivån. Tillsammans bildar dessa hashtabeller nivåsökningsstrukturen (LSS). För att garantera de värsta frågetiderna bör dessa hashtabeller använda dynamisk perfekt hashning eller cuckoo hashing .
Den totala utrymmesanvändningen är O ( n log M ), eftersom varje element har en rot-till-blad-bana med längden O (log M ).
Operationer
Precis som van Emde Boas-träd stödjer x-fast-försök driften av en ordnad associativ array . Detta inkluderar de vanliga associativa arrayoperationerna, tillsammans med ytterligare två orderoperationer , Successor och Predecessor :
- Hitta ( k ): hitta värdet som är associerat med den givna nyckeln
- Efterträdare ( k ): hitta nyckel/värdeparet med den minsta nyckeln större än eller lika med den givna nyckeln
- Föregångare ( k ): hitta nyckel/värdeparet med den största nyckeln mindre än eller lika med den givna nyckeln
- Infoga ( k , v ): infoga det givna nyckel/värdeparet
- Ta bort ( k ): ta bort nyckel/värdeparet med den givna nyckeln
Hitta
Att hitta värdet associerat med en nyckel k som finns i datastrukturen kan göras i konstant tid genom att slå upp k i LSS [0], som är en hashtabell på alla blad.
Efterträdare och föregångare
För att hitta efterföljaren eller föregångaren till en nyckel k , hittar vi först A k , den lägsta förfadern till k . Detta är den nod i försöket som har det längsta vanliga prefixet med k . För att hitta A k utför vi en binär sökning på nivåerna. Vi börjar på nivå h /2, där h är höjden på trean. På varje nivå frågar vi motsvarande hashtabell i nivåsökningsstrukturen med prefixet k av rätt längd. Om en nod med det prefixet inte finns vet vi att A k måste vara på en högre nivå och vi begränsar vår sökning till dessa. Om det finns en nod med det prefixet A k inte vara på en högre nivå, så vi begränsar vår sökning till nuvarande och lägre nivåer.
När vi väl har hittat den lägsta förfadern till k , vet vi att den har löv i ett av sina underträd (annars skulle det inte finnas i trie) och k borde finnas i det andra underträdet. Därför pekar descendentpekaren på efterföljaren eller föregångaren till k . Beroende på vilken vi letar efter kan vi behöva ta ett steg i den länkade listan till nästa eller föregående blad.
Eftersom trien har höjd O (log M ), tar den binära sökningen efter den lägsta förfadern O (log log M ) tid. Därefter kan efterföljaren eller föregångaren hittas i konstant tid, så den totala frågetiden är O (logg log M ).
Föra in
För att infoga ett nyckel-värdepar ( k , v ) hittar vi först föregångaren och efterföljaren till k . Sedan skapar vi ett nytt blad för k , infogar det i den länkade listan med blad mellan efterföljaren och föregångaren och ger den en pekare till v . Därefter går vi från roten till det nya bladet, skapar de nödvändiga noderna på vägen ner, infogar dem i respektive hashtabeller och uppdaterar efterkommande pekare där det behövs.
Eftersom vi måste gå ner för hela trian tar denna process O (log M ) tid.
Radera
För att ta bort en nyckel k hittar vi dess blad med hjälp av hashtabellen på bladen. Vi tar bort det från den länkade listan, men kom ihåg vilka som var efterträdaren och föregångaren. Sedan går vi från bladet till roten av trie, tar bort alla noder vars underträd bara innehöll k och uppdaterar de efterkommande pekarna där det behövs. Descendentpekare som brukade peka på k kommer nu att peka på antingen efterföljaren eller föregångaren till k , beroende på vilket underträd som saknas.
Precis som insättning tar detta O (log M ) tid, eftersom vi måste gå igenom varje nivå av försöket.
Diskussion
Willard introducerade x-snabba försök till stor del som en introduktion till y-snabba försök , som ger samma frågetid, samtidigt som det bara använder O ( n ) utrymme och tillåter infogning och borttagning i O (logg log M ) tid.
En kompressionsteknik som liknar patricia-försök kan användas för att avsevärt minska utrymmesanvändningen för x-fast-försök i praktiken.
Genom att använda en exponentiell sökning före den binära sökningen över nivåerna och genom att fråga inte bara det aktuella prefixet x , utan även dess efterföljare x + 1, kan x-snabba försök svara på föregångare och efterföljare i tiden O (log log Δ ), där Δ är skillnaden mellan frågevärdet och dess föregångare eller efterföljare.