Pretraga struktura podataka
Pretraga strukture podataka u računarstvu je svaka struktura podataka koja dozvoljava povraćaj specifičnih elemenata iz skupa elemenata, kao što je baza podataka.
Najjednostavnija, najopštija, a najmanje efikasna pretraga struktura je samo neuređena sekvenciona lista svih elemenata. Lociranje željene stavke u takvoj listi, sa metodom linearne pretrage, neminovno zahteva niz operacija proporcionalnih broju n stavki, u najgorem mogućem slučaju kao i u prosečnom slučaju. Korisne pretrage strukture podataka omogućavaju bržu pretragu; međutim, oni su ograničeni na upite neke specifične vrste. Štaviše, pošto troškovi izgradnje takvih struktura su barem proporcionalni N, oni će se isplatiti samo ako se nekoliko upita treba izvršiti na istoj bazi podataka (ili na bazi podataka koja se malo menja između upita).
Statičke pretrage struktura podataka su dizajnirane za odgovaranje mnogih upita ka fiksnoj bazi podataka; Dinamičke strukture takođe omogućavaju umetanje, brisanje ili izmenu stavki između uzastopnih upita. U dinamičnom slučaju, moraju se takođe uzeti u obzir troškovi popravljanja struktura pretrage za odgovarajuće promene u bazi podataka.
Klasifikacija[uredi | uredi kod]
Najjednostavnija vrsta upita je da se pronađe zapis koji ima specifičnu oblast (tj. ključ) jednak određenoj vrednosti V. Druge uobičajene vrste upita su "pronađi stavku sa najmanjom (ili najvećom) vrednosti ključa", "naći stavku sa najvećom vrednosti ključa koja ne prelazu V", "naći sve stavke sa vrednostima ključa između navedenih granica Vmin and Vmaks".
U nekim bazama ključne vrednosti mogu biti tačke u nekim dimenzionim prostorima. Na primer, ključ može da bude geografski položaj (geografska širina i geografska dužina) na Zemlji. U tom slučaju, najčešći tipovi upita su nađi zapis sa vrednosti ključa najbližoj datoj tački V", ili "nađi sve stavke čiji ključ leži u određenom rastojanju od V", ili "nađi sve stavke unutar određenog prostora R ".
Specijalni slučaj su istovremeni opseg upita sa dva ili više jednostavnih ključeva, kao što su "nađi sve podatke o zaposlenima sa platom između 50.000 i 100.000 i ѕaposlenim između 1995 i 2007".
Pojedinačni uređeni ključevi[uredi | uredi kod]
- Niz
- Po prioritetu sortirana lista; pogledati Linearna pretraga
- Po ključu sortirani niz; pogledati binarna pretraga
- Binarno stablo pretrage
- Heš tablice
Asimptotska analiza najgoreg mogućeg scenarija[uredi | uredi kod]
U ovoj tablici, asimptotska notacija O(F(N)) znači "ne prelazi neki fiksni množioc od F(N) u najgorem mogućem scenariju."
| Umetni | Obriši | Indeks | Pretraga | Nađi maksimum-minimum | Zauzeće prostora | |
|---|---|---|---|---|---|---|
| Nesortirani niz | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) |
| Sortirani niz | O(n) | O(n) | O(1) | O(log n) | O(1) | O(n) |
| Nesortirana povezana lista | O(1)* | O(1)* | O(n) | O(n) | O(n) | O(n) |
| Sortirana povezana lista | O(1)* | O(1)* | O(n) | O(n) | O(n) | O(n) |
| Samobalansirajuće binarno stablo pretrage | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(n) |
| Hip | O(log n) | O(log n)** | N/A | O(n) | O(1) | O(n) |
| Heš tablice | O(1) | O(1) | N/A | O(1) | O(n) | O(n) |
Ova tablica je samo aproksimativna; za svaku strukturu podataka postoje posebne situacije i varijante koje mogu dovesti do različitih rezultata. Takođe, dve ili više strukture podataka mogu se kombinovati da dobiju niži troškovi.