АСП2/К1 2015
1. zadatak
Postavka
Skup ključeva smešten je u stablo binarnog pretraživanja. Nakon brisanja ključa 12, dobijen je izgled stabla prikazan na slici. Pod pretpostavkom da je ključ 9 umetnut u stablo nakon ključa 12, da nije bilo prethodnih brisanja ključeva i da se prilikom brisanja koristi sledbenik, prikazati izgled stabla neposredno pre brisanja ključa 12.
6
/ \
5 15
/ / \
3 7 18
\ \ /
4 9 16
/ \
8 17
Rešenje
6
/ \
5 15
/ / \
3 12 18
\ / /
4 7 16
\ \
9 17
/
8
6
/ \
5 15
/ / \
3 7 18
\ \ /
4 12 16
/ \
9 17
/
8
6
/ \
5 12
/ / \
3 7 15
\ \ \
4 9 18
/ /
8 16
\
17
6
/ \
5 12
/ / \
3 7 18
\ \ /
4 9 15
/ \
8 16
\
17
6
/ \
5 12
/ / \
3 7 18
\ \ /
4 9 16
/ / \
8 15 17
2. zadatak
Postavka
Dat je krug K, sa centrom u tački C, poluprečnika r. Data je duž D čije je teme T1 unutar K, a teme T2 izvan K. Koristeći metodu binarne pretrage kao ideju, napisati u pseudokodu funkciju koja približno određuje tačku preseka K i D. Preciznost aproksimacije kontrolisati posebnim parametrom funkcije.
Rešenje
Ovde je ideja da nagađamo na kom se delu duži, u procentima, nalazi presek s kružnicom. Za svako nagađanje računamo razdaljinu od centra i ako je veća od poluprečnika to znači da smo van kruga, odnosno da treba da idemo bliže tački T1, u suprotnom treba da idemo bliže tački T2. Parametar p nam ovde označava preciznost aproksimacije u procentima dužine duži.
INTERSECT(K, D)
p = 0.05
low = 0
high = 1
mid_x = 0
mid_y = 0
while high - low ≥ p do
mid = (high + low) / 2
mid_x = (x(T2) - x(T1)) * mid + x(T1)
mid_y = (y(T2) - y(T1)) * mid + y(T1)
diff = sqrt((mid_x - x(C)) * (mid_x - x(C)) + (mid_y - y(C)) * (mid_y - y(C)))
if diff = r then
return mid_x, mid_y
else if diff < r then
low = mid
else
high = mid
end_if
end_while
return mid_x, mid_y3. zadatak
Postavka
Stabla binarnog pretraživanja
- Na koji način se u stablo binarnog pretraživanja može dozvoliti umetanje ključeva sa istom vrednošću?
- Napisati u pseudokodu iterativnu implementaciju funkcije koja umeće vrednost x u stablo binarnog pretraživanja na koje pokazuje pokazivač root. U stablo je dozvoljeno umetati ključeve sa istom vrednošću.
Rešenje
Postoje dva načina na koje se može dozvoliti umetanje ključeva sa istom vrednošću u binarno stablo pretraživanja:
- U svakom čvoru stabla se čuva niz čvorova koje imaju istu vrednost ključa - ovim se postiže da se struktura stabla ne povećava.
- Čvorovi sa istom vrednošću se tretiraju kao veći, odnosno čuvaju u desnom podstablu - ovim se postiže veća pogodnost kod korišćenja za realizaciju struktura poput prioritetnog reda.
BST INSERT MOD(root, x)
node = GETNODE
value(node) = x
if root = nil then
root = node
return
end_if
p = root
while true do
if key(p) = x then
right(node) = right(p)
right(p) = node
break
else if key(p) < x then
if right(p) = nil then
right(p) = node
break
else
p = right(p)
end_if
else
if left(p) = nil then
left(p) = node
break
else
p = left(p)
end_if
end_if
end_while4. zadatak
Postavka
Crveno-crna stabla
- Definisati pojam crne visine (eng. black height) nekog čvora crveno-crnog stabla.
- Napisati u pseudokodu funkciju koja u zadatom crveno-crnom stablu određuje crnu visinu zadatog čvora X.
Rešenje
5. zadatak
Postavka
Neka se u prazno AVL stablo redom umeću ključevi 35, 75, 51, 61, 65, 80, 44, 48, 39, 77, a zatim brišu ključevi 65, 44, 80. Prilikom brisanja, koristiti sledbenika. Prikazati izgled stabla nakon svakog izvršenog umetanja i brisanja.
Rešenje
Postupak umetanja možete simulirati u nekom od simulatora za AVL stabla. Nakon umetanja dobije se sledeće stablo:
65
/ \
44 77
/ \ / \
35 51 75 80
\ / \
39 48 60
Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:
75
/ \
44 77
/ \ \
35 51 80
\ / \
39 48 60
Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:
75
/ \
48 77
/ \ \
35 51 80
\ \
39 60
Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega:
48
/ \
35 75
\ / \
39 51 77
\
61
6. zadatak
Postavka
U crveno-crno stablo sa slike se najpre vrši umetanje ključa 50, a zatim vrši brisanje ključa 13. Prikazati izgled stabla nakon svake od navedenih promena.
Rešenje
7. zadatak
Postavka
Dati pseudokod i objasniti algoritam određivanja prethodnika čvora sa zadatom adresom x u stablu binarnog pretraživanja. Napomena: Prilikom kretanja uz stablo ne koristiti proveru na pripadnost podstablu, već na vrednosti ključeva.
Rešenje
Prvo proveravamo da li čvor ima levo podstablo. Ukoliko ima, vraćamo najdesniji čvor u levom podstablu kao prethodnika čvora. Ukoliko nema, penjemo se uz stablo poredeći ključ čvora x sa ključevima njegovih roditelja i ako nađemo čvor sa manjim ključem vratimo ga.
PRED NODE(x)
if left(x) = nil then
p = parent(x)
while p ≠ nil do
if key(p) < key(x) then
return p
end_if
p = parent(p)
end_while
return nil
else
p = left(x)
while right(p) ≠ nil do
p = right(p)
end_while
return p
end_if8. zadatak
Postavka
a) Objasniti jednu strategiju za dobijanje suboptimalnog stabla binarnog pretraživanja koja uključuje i uspešna i neuspešna pretraživanja. b) Postupak ilustrovati po koracima ako su dati ključevi , sa verovatnoćama uspešnog pretraživanja , (0.1, 0.05, 0.05, 0.1, 0.05, 0.1, respektivno) i verovatnoćama neuspešnog pretraživanja (0.2, 0.05, 0.05, 0.0, 0.0, 0.05, 0.2, respektivno).
Rešenje
- Možemo formirati suboptimalno binarno stablo pretraživanja odabiranjem korena sa najmanjom razlikom težina između podstabala i rekurzivno ponavljati proces za oba podstabla.
-
- Kandidati za koren su nam K3 i K4. K3 nam daje razliku 0.1 između težina podstabla, a K4 0.05, pa zato biramo K4 i proces nastavljamo za [1, 2, 3] i [5, 6].
- Jedini kandidat za koren levog podstabla nam je K2, i zato njega postavljamo kao koren, K1 njegovo levo dete a K3 njegovo desno.
- Kandidat K6 je bolji od K5 jer omogućava razliku od 0.05 između težina podstabala za razliku od 0.1, pa njega postavljamo kao koren a K5 kao njegovo levo dete i dobijamo konačno stablo:
4 / \ 2 6 / \ / 1 3 5