ASP2/K1 2011

Prvi kolokvijum 2011. godine održan je 24. oktobra 2011. Postavka zadataka je dostupna sa stranice predmeta.

1. zadatak

Postavka

(30p) Koristeći algoritam binarne pretrage uređenog vektora kao osnovu, napisati na jeziku C (ili C++) funkciju za pretragu uređenog vektora jedinstvenih celobrojnih ključeva dužine n na zadati ključ deljenjem intervala pretrage na tri podintervala približno jednake dužine. Napisati glavni program koji demonstrira upotrebu prethodne funkcije. Koristiti fiksne podatke (nije potrebno čitati podatke iz datoteke ili standardnog ulaza). Komentarisati vremensku i prostornu složenost napisane funkcije. Porediti vremensku složenost napisane funkcije i algoritma binarne pretrage.

Rešenje

Vremenska složenost je $O(log_3{n})$, a prostorna $O(n)$.

FUN(arr, key)
high = n;
low = 1;
while(low <= high)
    left = (low+high)/3;
    right = 2(low+high)/3;
    if(arr[left]=key) return left;
    if(arr[right]=key) return right;
    if(key < arr[left]) high = left-1;
    if(key > arr[right]) low = right+1;
    if(key>arr[left] and key<arr[right])
        low = left+1;
        high = right-1;
    end_if
end_while
return 0;

2. zadatak

Postavka

(20p) U stablo binarnog pretraživanja se redom umeću sledeći ključevi: 22, 31, 24, 28, 26, 41, 45, 10, 6, 8, 9, 7, 4, 5, 2. Nakon umetanja se redom brišu ključevi: 41, 6, 22, 10. Prikazati izgled stabla pretraživanja nakon svake od navedenih izmena. Ako dobijeno stablo ne zadovoljava kriterijum balansiranosti AVL stabla, transformisati stablo primenom osnovnih transformacija za održavanje balansiranosti da bi se dobilo AVL stablo. Prikazati izgled stabla nakon primene svake transformacije. Napomena: prilikom brisanja ključeva, koristiti sledbenike.

Rešenje

Stablo nakon umetanja ključeva 22,31,24,28,26 i 41

Stablo nakon umetanja ključeva 45,10,6 i 8

Stablo nakon umetanja ključeva 9 i 7

Stablo nakon umetanja ključeva 4 i 5

Stablo nakon svih umetanja

Stablo nakon brisanja ključeva 41,6 i 22

Stablo nakon svih brisanja

3. zadatak

Postavka

(20p) Definisati AVL stablo i kritični čvor. Kada se javlja potreba za dvostrukom rotacijom? Objasniti ovu operaciju i ilustrovati opštim slikama.

Rešenje

AVL stablo je stablo binarnog pretraživanja koje ispunjava kriterijum da svaki čvor mora da ima balans 0, 1 ili -1, gde balans predstavlja razliku visina levog i desnog podstabla.

Kritični čvor je koren najmanjeg podstabla koje nije visinski balansirano.

Dvostruka rotacija se vrši kada kritični čvor i sin sa one strane na koju naginje kritični čvor naginju na suprotne strane (npr kritični čvor na desno a njegov levi sin na levo). Prvo se vrši odgovarajuća rotacija nad sinom tako da kritični čvor i sin naginju na istu stranu, a zatim se vrši rotacija u suprotnu stranu nad kritičnim čvorom, čime se dobija visinski balansirano stablo.

Početno stanje

Stablo nakon prve rotacije udesno oko sina

Stablo nakon rotacije ulevo oko kritičnog čvora

4. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

(30p) Pitanja:

1. Dati pseudokod i objasniti sekvencijalno pretraživanje sa graničnikom. Kakvo poboljšanje ono donosi?
2. Objasniti organizaciju 2-3-4 stabla. Kakva je njihova prednost i kako se implementiraju?
3. Objasniti strategiju dobijanja približno optimalnog stabla koja uzima u obzir i uspešna i neuspešna pretraživanja.

Rešenje

c) Približno optimalno stablo se formira od korena na dole i bira se tako da se minimizira težina levog i desnog podstabla, a zatim se u blizini korena traži mogući novi koren sa većom verovatnoćom pristupa, i ako se takav čvor pronađe, pređašnji čvor se pomera malo ulevo ili udesno. Postupak se ponavlja rekurzivno.