Sök datastruktur
Inom datavetenskap är en sökdatastruktur [ citat behövs ] vilken datastruktur som helst som möjliggör effektiv hämtning av specifika objekt från en uppsättning objekt, till exempel en specifik post från en databas .
Den enklaste, mest allmänna och minst effektiva sökstrukturen är bara en oordnad sekventiell lista över alla objekt. Att lokalisera det önskade objektet i en sådan lista, genom den linjära sökmetoden , kräver oundvikligen ett antal operationer proportionellt mot antalet n objekt, i värsta fall såväl som i genomsnittsfallet . Användbara sökdatastrukturer möjliggör snabbare hämtning; de är dock begränsade till frågor av något specifikt slag. Dessutom, eftersom kostnaden för att bygga sådana strukturer är åtminstone proportionell mot n , lönar sig de bara om flera frågor ska utföras på samma databas (eller på en databas som ändras lite mellan frågorna).
Statiska sökstrukturer är designade för att svara på många frågor på en fast databas; dynamiska strukturer tillåter också infogning, borttagning eller modifiering av objekt mellan på varandra följande frågor. I det dynamiska fallet måste man också överväga kostnaden för att fixa sökstrukturen för att ta hänsyn till förändringarna i databasen.
Klassificering
Den enklaste typen av fråga är att hitta en post som har ett specifikt fält (nyckeln ) lika med ett angivet värde v . Andra vanliga typer av frågor är "hitta objektet med det minsta (eller största) nyckelvärdet", "hitta objektet med det största nyckelvärdet som inte överstiger v ", "hitta alla objekt med nyckelvärden mellan specificerade gränser v min och v max ".
I vissa databaser kan nyckelvärdena vara punkter i något flerdimensionellt utrymme . Till exempel kan nyckeln vara en geografisk position ( latitud och longitud ) på jorden . I så fall är vanliga typer av frågor "hitta posten med en nyckel närmast en given punkt v ", eller "hitta alla objekt vars nyckel ligger på ett givet avstånd från v ", eller "hitta alla objekt inom en specificerad region R av utrymmet".
Ett vanligt specialfall av de sistnämnda är samtidiga intervallfrågor på två eller flera enkla nycklar, som "hitta alla anställdas poster med lön mellan 50 000 och 100 000 och anställd mellan 1995 och 2007".
Enkelbeställda nycklar
- Array om nyckelvärdena spänner över ett måttligt kompakt intervall.
- Prioritetssorterad lista; se linjär sökning
- Nyckelsorterad array; se binär sökning
- Självbalanserande binärt sökträd
- Hashbord
Att hitta det minsta elementet
Asymptotisk analys i värsta fall
betyder den asymptotiska notationen O ( f ( n )) "att inte överskrida någon fast multipel av f ( n ) i värsta fall."
| Datastruktur | Föra in | Radera | Balans | Gå till index | Sök | Hitta minimum | Hitta maximalt | Utrymmesanvändning |
|---|---|---|---|---|---|---|---|---|
| Osorterad array |
O (1) (se not) |
O (1) (se not) |
N/A | O (1) | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
| Sorterad array | O ( n ) | O ( n ) | N/A | O (1) | O (log n ) | O (1) | O (1) | O ( n ) |
| Stack | O (1) | O (1) | O ( n ) | O ( n ) | ||||
| Kö | O (1) | O (1) | O ( n ) | O ( n ) | ||||
| Osorterad länkad lista | O (1) | O (1) | N/A | O ( n ) | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
| Sorterad länkad lista | O ( n ) | O (1) | N/A | O ( n ) | O ( n ) | O (1) | O (1) | O ( n ) |
| Hoppa över listan | ||||||||
| Självbalanserande binärt sökträd | O (log n ) | O (log n ) | O (log n ) | N/A | O (log n ) | O (log n ) | O (log n ) | O ( n ) |
| Högen | O (log n ) | O (log n ) | O (log n ) | N/A | O ( n ) |
O (1) för en min-hög O ( n ) för en max-hög |
O (1) för en max-hög O ( n ) för en min-hög |
O ( n ) |
| Hashbord | O (1) | O (1) | O ( n ) | N/A | O (1) | O ( n ) | O ( n ) | O ( n ) |
| Försök ( k = nyckelns genomsnittliga längd) | O ( k ) | O ( k ) | N/A | O ( k ) | O ( k ) | O ( k ) | O ( k ) | O ( k n ) |
| Kartesiskt träd | ||||||||
| B-träd | O (log n ) | O (log n ) | O (log n ) | N/A | O (log n ) | O (log n ) | O (log n ) | O ( n ) |
| Röd-svart träd | O (log n ) | O (log n ) | O (log n ) | O ( n ) | ||||
| Splay träd | ||||||||
| AVL-träd | O (log n ) | |||||||
| kd träd |
Obs : Infoga på en osorterad array citeras ibland som O ( n ) på grund av antagandet att elementet som ska infogas måste infogas på en viss plats i arrayen, vilket skulle kräva att alla efterföljande element flyttas med en position. Men i en klassisk array används arrayen för att lagra godtyckliga osorterade element, och därför har den exakta positionen för ett givet element ingen betydelse, och insättningen utförs genom att öka arraystorleken med 1 och lagra elementet i slutet av arrayen, vilket är en O (1) operation. På samma sätt citeras ibland borttagningsoperationen som O ( n ) på grund av antagandet att efterföljande element måste flyttas, men i en klassisk osorterad array är ordningen oviktig (även om element implicit ordnas efter infogningstid), så radering kan utföras genom att byta ut elementet som ska raderas med det sista elementet i arrayen och sedan minska arraystorleken med 1, vilket är en O (1) operation.
Denna tabell är endast en ungefärlig sammanfattning; för varje datastruktur finns speciella situationer och varianter som kan leda till olika kostnader. Även två eller flera datastrukturer kan kombineras för att erhålla lägre kostnader.