АСП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
Koristi se modifikovana binarna pretraga koja se izvršava dok se tačka ne nađe na kružnici ili dok je greška manja od err. Parametar err je prosleđen funkciji.
INTERSECT(K, D, err)
low = T1
high = T2
prev = low
while true do
x(mid) = (x(low) + x(high)) / 2
y(mid) = (y(low) + y(high)) / 2
dist = distance(C, mid)
if (dist = r) or (distance(mid, prev) < err) then
return mid
else if dist > r then
high = mid
else
low = mid
end_if
prev = mid
end_while
DISTANCE(A, B)
return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2))
3. 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
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_while
4. 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
Crna visina nekog čvora je broj crnih čvorova na putu od tog čvora do listova, i po definiciji crveno-crnog stabla je jednaka za sve puteve do listova.
BH CALC(x)
p = x
bh = 0
while p ≠ nil do
if (black(p)) then
bh = bh + 1
end_if
p = left(p)
end_while
return bh
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 61
Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto:
75
/ \
44 77
/ \ \
35 51 80
\ / \
39 48 61
Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto:
75
/ \
48 77
/ \ \
35 51 80
\ \
39 61
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
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
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_if
8. 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.05 između težina podstabla, a K4 0.1, pa zato biramo K3 i proces nastavljamo za [1, 2] i [4, 5, 6].
- Sa K1 u korenu razlika između levog i desnog podstabla od levog suboptimalnog podstabla je -0.05 a sa K2 je 0.3, tako da postavljamo K1 kao koren levog podstabla.
- Sa K6 u korenu razlika između levog i desnog podstabla od desnog suboptimalnog podstabla je 0, sa K5 -0.25 a sa K4 -0.4, tako da postavljamo K6 kao koren desnog podstabla.
- Na kraju, sa K5 kao korenom levog podstabla od desnog podstabla dobijamo da je razlika težina 0.05, a sa K4 -0.1, tako da K5 postavljamo za koren levog podstabla od desnog podstabla.
3
/ \
1 6
\ /
2 5
/
4