АСП2/К1 2008

Prvi kolokvijum 2008. godine održan je 29. oktobra 2008. Postavka zadataka je dostupna sa stranice predmeta.

1. zadatak

Postavka

(20p) Posmatra se niz celobrojnih ključeva, implementiran u vidu jednostruko ulančane liste. Ključevi se umeću u proizvoljnom redosledu, ali nije neophodno zadržati poredak. Potrebno je izabrati efikasnu metodu pretrage opisanog niza. Od interesa su sledeći parametri: brzina pretrage, brzina umetanja i brisanja ključa, vreme režije. Razmatraju se sledeći pristupi:

1. Binarna pretraga
2. Sekvencijalna pretraga sa transpozicijom ključeva

Komentarisati efikasnost ponuđenih metoda prema navedenim parametrima. Za metodu koja se proceni kao bolja skicirati postupak pretrage na jedan ključ.

Rešenje

1. Za binarnu pretragu je neophodno čuvati uređenu listu, pa je i umetanje i brisanje ključa iste složenosti, kao i nalaženje ključa, što u slučaju ulančane liste nije dobra složenost (svodi se na sekvencijalnu pretragu).
2. Sekvencijalna pretraga sa transpozicijom ključeva ima mnogo bolju složenost za datu strukturu - umetanje je O(1). Brisanje se svodi na nalaženje pa je složenost O(n), a pretraga je takođe O(n), sa mogućim ubrzanjem ukoliko se često pretražuju isti elementi.

Primer sekvencijalne pretrage na ključ 3 sa transpozicijom

2. zadatak

Postavka

(30p) U AVL stablo se redom umeću sledeći ključevi: 30, 12, 15, 14, 22, 35,18, 26, 32, 20, 33, 31, 24, 25, 28, 27. Nakon umetanja se redom brišu ključevi: 22, 15, 32. Prikazati izgled stabla nakon svake od navedenih izmena. Napomena: prilikom brisanja ključeva, menjati im mesta sa prethodnicima.

Rešenje

Ukoliko želite da zadatak proverite korak po korak, to možete uraditi na linku.

Stablo nakon svih umetanja

Stablo nakon svih brisanje

3. zadatak

Postavka

(20p) Skicirati i objasniti algoritam određivanja prethodnika zadatog čvora u stablu binarnog pretraživanja. Ilustrovati primerima različite slučajeve.

Rešenje

Ukoliko čvor ima levo podstablo, njegov prethodnik je najdešnji potomak njegovog levog sina, a ukoliko nema levo podstablo, njegov prethodnik je njegov najniži predak čiji je desni sin takođe njegov predak. U primeru ispod, prethodnik od 3 je 1, a prethodnik od 6 je 5.

Primer

4. zadatak

Postavka

(30p) Pitanja:

1. Objasniti šta su samopodešavajuća stabla, princip na kojem su zasnovana i diskutovati performanse.
2. Zašto se uvode 2-3 stabla? Objasniti njihovu organizaciju i glavne osobine.
3. Definisati optimalno stablo binarnog pretraživanja i navesti osnovnu osobinu na kojoj se zasniva algoritam za njegovo određivanje.

Rešenje

1. Samopodešavajuća stabla su stabla binarnog pretraživanja kod kojih se raspored ključeva zasniva na vremenskoj lokalnosti. To znači da se prilikom svake operacije (umetanje, brisanje i pretraga) traženi ključ, ili njemu najbliži (ukoliko je u pitanju neuspešna operacija) prebaci u koren nizom rotacija zig ili zag tipa. Složenost je O(n) u najgorem slučaju, jer se ne garantuje balansiranost stabla (nemaju nikakav kriterijum balansiranosti).
3. Optimalno stablo binarnog pretraživanja je ono stablo čija je cena najmanja, gde cenu definišemo kao: $C = \sum_{i}^{m-n} p_{i}(h_{i} + 1) + \sum_{i}^{m-n} q_{i}h_{i}$, gde su Pi verovatnoće pristupa ključevima Kn...Km, a Qi verovatnoće pristupa eksternim čvorovima. Osobina na kojoj se zasniva algoritam za nalaženje optimalnog stabla binarnog pretraživanja je da su sva podstabla optimalnog stabla pretraživanja takođe optimalna.