АСП2/К1 2015 — разлика између измена
м (Замена начина истицања милокода.) |
|||
(Није приказано 8 међуизмена 2 корисника) | |||
Ред 80: | Ред 80: | ||
=== 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. | 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. | ||
< | {{Милокод|<nowiki> | ||
INTERSECT(K, D, err) | INTERSECT(K, D, err) | ||
low = T1 | low = T1 | ||
Ред 98: | Ред 98: | ||
prev = mid | prev = mid | ||
end_while | end_while | ||
</ | </nowiki>}} | ||
{{Милокод|<nowiki> | |||
< | |||
DISTANCE(A, B) | DISTANCE(A, B) | ||
return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2)) | return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2)) | ||
</ | </nowiki>}} | ||
== 3. zadatak == | == 3. zadatak == | ||
Ред 117: | Ред 116: | ||
# 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. | # 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. | # Č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. | ||
< | {{Милокод|<nowiki> | ||
BST INSERT MOD(root, x) | BST INSERT MOD(root, x) | ||
node = GETNODE | node = GETNODE | ||
Ред 127: | Ред 126: | ||
p = root | p = root | ||
while true do | while true do | ||
if key(p) | if key(p) ≤ x then | ||
if right(p) = nil then | if right(p) = nil then | ||
right(p) = node | right(p) = node | ||
Ред 147: | Ред 142: | ||
end_if | end_if | ||
end_while | end_while | ||
</ | </nowiki>}} | ||
== 4. zadatak == | == 4. zadatak == | ||
Ред 158: | Ред 153: | ||
=== Rešenje === | === 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. | |||
{{Милокод|<nowiki> | |||
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 | |||
</nowiki>}} | |||
== 5. zadatak == | == 5. zadatak == | ||
Ред 171: | Ред 179: | ||
35 51 75 80 | 35 51 75 80 | ||
\ / \ | \ / \ | ||
39 48 | 39 48 61 | ||
Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto: | Po brisanju čvora 65, njegov sledbenik čvor 75 dolazi na njegovo mesto: | ||
75 | 75 | ||
Ред 179: | Ред 187: | ||
35 51 80 | 35 51 80 | ||
\ / \ | \ / \ | ||
39 48 | 39 48 61 | ||
Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto: | Zatim se briše čvor 44 i njegov sledbenik čvor 48 dolazi na njegovo mesto: | ||
75 | 75 | ||
Ред 187: | Ред 195: | ||
35 51 80 | 35 51 80 | ||
\ \ | \ \ | ||
39 | 39 61 | ||
Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega: | Na kraju, briše se čvor 80 čime čvor 75 postaje kritičan čvor pa radimo rotaciju ulevo oko njega: | ||
48 | 48 | ||
Ред 198: | Ред 206: | ||
== 6. zadatak == | == 6. zadatak == | ||
{{делимично решено}} | |||
=== Postavka === | === Postavka === | ||
[[Датотека:ASP2 K1 2015 zadatak 6 stablo. | [[Датотека:ASP2 K1 2015 zadatak 6 stablo.svg|thumb|Crveno-crno stablo iz postavke zadatka.]] | ||
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. | 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. | ||
Ред 210: | Ред 219: | ||
=== Rešenje === | === 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. | 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. | ||
< | {{Милокод|<nowiki> | ||
PRED NODE(x) | PRED NODE(x) | ||
if left(x) = nil then | if left(x) = nil then | ||
Ред 228: | Ред 237: | ||
return p | return p | ||
end_if | end_if | ||
</ | </nowiki>}} | ||
== 8. zadatak == | == 8. zadatak == | ||
Ред 238: | Ред 247: | ||
# 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. | # 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. | ## 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. | |||
</div> | </div> | ||
3 | |||
/ \ | |||
1 6 | |||
\ / | |||
2 5 | |||
/ | |||
4 | |||
[[Категорија:АСП2]] | [[Категорија:АСП2]] | ||
[[Категорија:Рокови]] | [[Категорија:Рокови]] |
Тренутна верзија на датум 13. септембар 2024. у 02:09
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