АСП2/К1 2015 — разлика између измена
Ред 79: | Ред 79: | ||
=== Rešenje === | === 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 <code>err</code>. Parametar <code>err</code> je prosleđen funkciji. | |||
<syntaxhighlight lang="milo"> | <syntaxhighlight lang="milo"> | ||
INTERSECT(K, D) | INTERSECT(K, D, err) | ||
low = T1 | |||
low = | high = T2 | ||
high = | prev = low | ||
while true do | |||
x(mid) = (x(low) + x(high)) / 2 | |||
while | y(mid) = (y(low) + y(high)) / 2 | ||
mid | dist = distance(C, mid) | ||
if (dist = r) or (distance(mid, prev) < err) then | |||
return mid | |||
else if dist > r then | |||
if | high = mid | ||
else | |||
else | |||
low = mid | low = mid | ||
end_if | end_if | ||
prev = mid | |||
end_while | end_while | ||
return | </syntaxhighlight> | ||
<syntaxhighlight lang="milo"> | |||
DISTANCE(A, B) | |||
return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2)) | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Верзија на датум 2. новембар 2020. у 20:36
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
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_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
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_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.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