Algoritmi pretraživanja

U računarstvu i informatici algoritam pretraživanja je proces kojim se u skupu podataka pronalazi željeni podatak na osnovu određene identifikacije.

Klasifikacija[uredi | uredi izvor]

Podela se može izvršiti na osnovu pogodnosti određenog algoritma za pretragu nad statičkim, odnosno dinamičkim, skupom podataka, i složenosti njegove implementacije:

Osnovni algoritmi pretraživanja
Stabla pretraživanja
Heširanje

Osnovni algoritmi pretraživanja[uredi | uredi izvor]

Ovi algoritmi su najjednostavniji za implementaciju, a pogodni su za pretragu statičkih skupova podataka (uređenih i neuređenih tabela). Ovoj grupi spadaju:

Sekvencijalno pretraživanje
Binarno pretraživanje

Sekvencijalno pretraživanje[uredi | uredi izvor]

Ovaj način pretrage je najjednostavniji za implementaciju, ali ima najlošije performanse. Sastoji se u tome da se krene redom i proverava za svaki element da li je taj element onaj koji tražimo. Ukoliko jeste, pretraga se uspešno završava, u suprotnom se ide dalje, sve dok se ne nađe željeni element ili se ne ispitaju svi elementi.

Pretpostavimo da želimo da pronađemo poziciju nekog određenog elementa u nizu celih brojeva. Primer ovog algoritma u programskom jeziku C, izgledao bi ovako:

int sek_pret(int niz[], int n, int k) {
    int i=0;
    while(i<n) {
      if(k==niz[i]) {
         return i;
      } else {
         i++;
      }
    }
    return -1;
}

U prethodnom primeru, niz[] je niz koji pretražujemo, n je broj elemenata u nizu, k je željeni element, a i je trenutna iteracija kroz niz.

Mogu se izvršiti poboljšanja prethodnog algoritma, zasnovana na pretpostavci vremenske lokalnosti. Smatra se, da će traženi ključ, u bliskoj budućnosti, ponovo biti potreban, pa se on pomera ka početku niza, kako bi ranije bio pronađen. Metodom transpozicije, ključ se prebacuje za jedno mesto unapred, dok se kod metode prebacivanja na početak pronađeni element stavlja na početak niza.

Binarno pretraživanje[uredi | uredi izvor]

Ovaj algoritam primenljiv je samo na uređene skupove podataka. Ne provera se redom da li je trenutni element taj koji tražimo, već se počinje od elementa koji je u sredini uređenog niza.

Pretpostavimo da je niz (tabela) uređen rastuće. Ukoliko je element u sredini manji od onog koji tražimo, pretragu ćemo nastaviti u gornjoj polovini niza, u suprotnom, ako je element u sredini veći od onog koji tražimo, pretragu nastavljamo u donjoj polovini niza. Zatim ponovo uzimamo srednji element preostalog intervala za pretragu i poredimo sa željenim elementom. Pretraga se nastavlja dok se element ne pronađe, a u slučaju da element nije pronađen u toj iteraciji, interval se deli na pola. Ako se interval sastoji samo od jednog elementa, a to nije željeni element, pretraga se završava neuspešno, tj. traženi element nije pronađen u datom nizu.

Pretpostavimo da želimo da pronađemo poziciju nekog određenog elementa u uređenom nizu celih brojeva. Primer ovog algoritma u programskom jeziku C, izgledao bi ovako:

int bin_pret(int niz[], int n, int k) {
    int donja_gran= 0;
    int gornja_gran= n - 1;
    while(donja_gran<=gornja_gran) {
      int sred = (donja_gran+gornja_gran)/2;
      if(k==niz[sred]) {
         return sred;
      } else {
           if(k<niz[sred]) {
              gornja_gran = sred - 1;
           } else {
              donja_gran = sred + 1;
           }
      }
    }
    return -1;
}

Stabla pretraživanja[uredi | uredi izvor]

Kod ove grupe algoritama, implementacija je nešto složenija, ali se oni mogu primeniti, jednako dobro, i na skupove statičkih i na skupove dinamičkih podataka. Operacije nad strukturama podataka, koji omogućavaju uspešnost ovih algoritama, su zahtevnije u pogledu memorije, procesorskog i programerskog vremena.

Stablo binarnog pretraživanja
Stablo m-arnog pretraživanja
B stablo
B+ stablo
B* stablo
Stabla digitalnog pretraživanja

Stablo binarnog pretraživanja[uredi | uredi izvor]

Stablo binarnog pretraživanja primenjuje se na skupovima podataka koji se dinamički menjaju, jer se njegova struktura efikasno modifikuje prilikom ubacivanja/brisanja elemenata.

Ono se definiše kao binarno stablo za koje važi:

za svaki ključ K postoji najviše jedan čvor l gde je kljuc(l) = K
ključevi svih potomaka u levom stablu su manji od ključa tog čvora
ključevi svih potomaka u desnom stablu su veći od ključa tog čvora

Pretraga na određeni ključ u binarnom stablu pretrage, u programskom jeziku C izgledala bi ovako:

int bin_stab_pret(Cvor *koren, int k) {
    Cvor pom = koren;
    while((pom!=null) && (k!=pom->kljuc)) {
      if(k < pom->kljuc) {
         pom = pom->levi_potomak;
      } else {
         pom = pom->desni_potomak;
      }
    }
    return pom;
}

Funkciji predajemo koren stabla koji je tipa „Čvor“ i željeni ključ. Čvor je struktura koja u sebi sadrži pokazivač na desnog i levog potomka, kao i ključ koji čvor sadrži. Funkcija vraća pokazivač na čvor koji je rezultat pretrage (null pointer u slučaju neuspešne pretrage).

Stablo m-arnog pretraživanja[uredi | uredi izvor]

Stablo m-arnog pretraživanja je stablo koje zadovoljava sledeće osobine:

čvor stabla se sastoji od pokazivača na podstabla i, najviše m, ključeva, koji su organizovani tako da svaki ključ razdvaja dva pokazivača(podstabla)
ključevi unutar jednog čvora su rastuće uređeni
u proizvoljnom čvoru, svi ključevi podstabla, na koji pokazuje pokazivač levo od ključa K, su manji od ključa K
u proizvoljnom čvoru, svi ključevi podstabla, na koji pokazuje pokazivač desno od ključa K, su veći od ključa K
podstabla, na koja ukazuju pokazivači iz višeg sloja stabla m-arnog pretraživanja, su takođe stabla m-arnog pretraživanja

Pretraga u ovom stablu se vrši tako što se ključ prvo traži u korenom čvoru. Ako se tu ne nađe, onda se traži odgovarajući pokazivač na neko podstablo u kojem je možda željeni ključ. Taj pokazivač se nalazi tako što se u korenom čvoru nađu dva uzastopna ključa К_i-1 i К_i-2 takva da je željeni ključ veći od К_i-1, a manji od К_i-2. Pokazivač između ta dva ključa ukazuje na onaj čvor u kojem nastavljamo pretragu. Proces je pretrage u bilo kom čvoru je isti kao u korenom, i on se ponavalja sve dok se ne nađe ključ ili dok ne dođemo do nekog od listova stabla u kojem takođe nismo pronašli traženi ključ, a potraga se ne može nastaviti jer nema više podstabala u kojima možemo da vršimo pretragu.

Pretraga na nivou čvora se može izvršiti sekvencijalnim ili binarnim načinom pretraživanja.

Literatura[uredi | uredi izvor]

D. E. Knuth (1998). The Art of Computer Programming Volume 3: Sorting and Searching (3rd izd.). Addison-Wesley Professional. ISBN 978-0-201-48541-7.
William H. Press; Brian P. Flannery; Saul A. Teukolsky; William T. Vetterling (1992). Numerical Recipes in C: The Art of Scientific Computing (Second izd.). Cambridge University Press. ISBN 978-0-521-43108-8.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Stein, Clifford (2009). Introduction to Algorithms (Third izd.). The MIT Press. ISBN 978-0-262-03384-8.