Y-snabb försök
| Y-snabb försök | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | Försök | |||||||||||||||
| Uppfunnet | 1982 | |||||||||||||||
| Uppfunnet av | Dan Willard | |||||||||||||||
| Tidskomplexitet i stor O-notation | ||||||||||||||||
| ||||||||||||||||
Inom datavetenskap är en y-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 (logg log M ), med O ( n ) 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 för att minska O ( n log M ) utrymmet som används av ett x-fast försök .
Strukturera
Ett y-fast försök består av två datastrukturer: den övre halvan är ett x-fast försök och den nedre halvan består av ett antal balanserade binära träd . Nycklarna är indelade i grupper av O (log M ) på varandra följande element och för varje grupp skapas ett balanserat binärt sökträd. För att underlätta effektiv insättning och radering innehåller varje grupp minst (log M )/4 och högst 2 log M element. För varje balanserat binärt sökträd väljs ett representativt r . Dessa representanter lagras i x-fast försök. Ett representativt r behöver inte vara ett element i trädet som är associerat med det, men det behöver vara ett heltal som är mindre än efterföljaren till r och minimielementet i trädet som är associerat med den efterföljaren och större än föregångaren till r och maximumelementet av trädet som är associerat med den föregångaren. Inledningsvis kommer representanten för ett träd att vara ett heltal mellan minimum- och maximumelementet i dess träd.
Eftersom x-fast trie lagrar O ( n / log M ) representanter och varje representant förekommer i O (log M ) hashtabeller, använder denna del av y-fast försök O ( n ) mellanslag. De balanserade binära sökträden lagrar totalt n element som använder O ( n ) utrymme. Därför använder totalt ett y-snabb försök O ( n ) mellanslag.
Operationer
Liksom van Emde Boas-träd och x-snabbförsök stöder y-snabbförsök driften av en ordnad associativ array . Detta inkluderar de vanliga associativa array-operationerna, 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
En nyckel k kan lagras i antingen trädet för den minsta representanten r större än k eller i trädet hos föregångaren till r eftersom representanten för ett binärt sökträd inte behöver vara ett element lagrat i dess träd. Därför hittar man först den minsta representanten r större än k i x-snabb försöket. Med hjälp av denna representant hämtar man föregångaren till r . Dessa två representanter pekar på två balanserade binära sökträd, som båda söker efter k .
Att hitta den minsta representanten r större än k i det x-snabba försöket tar O (log log M ). Att använda r tar konstant tid att hitta sin föregångare. Att söka i de två balanserade binära sökträden som innehåller O (log M ) element tar vart och ett O (log log M ) tid. Följaktligen kan en nyckel k hittas, och dess värde hämtas, i O (log log M ) tid.
Efterträdare och föregångare
På samma sätt som själva nyckeln k , kan dess efterföljare lagras i antingen trädet för den minsta representanten r större än k eller i trädet till föregångaren till r . Därför, för att hitta efterföljaren till en nyckel k , söker man först det x-snabba försöket efter den minsta representanten större än k . Därefter använder man denna representant för att hämta sin föregångare i x-fast försöket. Dessa två representanter pekar på två balanserade binära sökträd, som man söker efter efterföljaren till k .
Att hitta den minsta representanten r större än k i det x-snabba försöket tar O (log log M ) tid och att använda r för att hitta dess föregångare tar konstant tid. Att söka i de två balanserade binära sökträden som innehåller O (log M ) element tar vart och ett O (log log M ) tid. Följaktligen kan efterföljaren till en nyckel k hittas, och dess värde hämtas, i O (log log M ) tid.
Att söka efter föregångaren till en nyckel k är mycket likt att hitta dess efterföljare. Man söker i x-fast försöket efter den största representativa r mindre än k och man använder r för att hämta sin föregångare i x-fast försöket. Slutligen söker man i de två balanserade binära sökträden för dessa två representanter efter föregångaren till k . Detta tar O (log log M ) tid.
Föra in
För att infoga ett nytt nyckel/värdepar ( k , v ) måste man först bestämma i vilket balanserat binärt sökträd man behöver infoga k . För detta ändamål hittar man trädet T som innehåller efterföljaren till k . Därefter infogar man k i T . För att säkerställa att alla balanserade binära sökträd innehåller O (log M ) element, delar man upp T i två balanserade binära träd och tar bort dess representant från x-fast försöket om det innehåller mer än 2 log M element. Vart och ett av de två nya balanserade binära sökträden innehåller högst log M + 1 element. Man väljer en representant för varje träd och infogar dessa i x-fast försöket.
Att hitta efterföljaren till k tar O (log log M ) tid. Att infoga k i ett balanserat binärt sökträd som innehåller O (log M ) element tar också O (log log M ) tid. Att dela upp ett binärt sökträd som innehåller O (log M ) element kan göras på O (log log M ) tid. Slutligen tar det O (log M ) tid att infoga och ta bort de tre representanterna . Men eftersom man delar trädet högst en gång för varje O (log M ) insättning och radering, tar detta konstant amorterad tid. Att infoga ett nytt nyckel/värdepar tar därför O (logg log M ) avskriven tid.
Radera
Borttagningar påminner mycket om infogningar. Man hittar först nyckeln k i ett av de balanserade binära sökträden och raderar den från detta träd T . För att säkerställa att alla balanserade binära sökträd innehåller O (log M ) element, slår man samman T med det balanserade binära sökträdet för dess efterföljare eller föregångare om det innehåller mindre än (log M )/4 element. Representanter för de sammanslagna träden tas bort från x-fast försöket. Det är möjligt för det sammanslagna trädet att innehålla mer än 2 log M -element. Om så är fallet delas det nybildade trädet i två ungefär lika stora träd. Därefter väljer man en ny representant för vart och ett av de nya träden och man infogar dessa i x-fast försöket.
Att hitta nyckeln k tar O (logg log M ) tid. Att ta bort k från ett balanserat binärt sökträd som innehåller O (log M ) element tar också O (log log M ) tid. Att slå samman och eventuellt dela upp de balanserade binära sökträden tar O (logg log M ) tid. Slutligen tar det O (log M ) tid att ta bort de gamla representanterna och infoga de nya representanterna i x-fast försöket. Sammanfogning och eventuell delning av det balanserade binära sökträdet görs dock högst en gång för varje O (log M ) infogning och borttagning. Därför tar det konstant amorterad tid. Därför tar borttagning av ett nyckel/värdepar O (logg log M ) avskriven tid.