Изворни код странице АСП2/К1 2018

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_1819.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Optimalno stablo binarnog pretraživanja
<div class="abc-list">
# Navesti formulu za izračunavanje cene optimalnog stabla binarnog pretraživanja i objasniti je.
# Ukoliko se posmatraju tri ključa <math>K_1 < K_2 < K_3</math> sa poznatim verovatnoćama uspešnog pretraživanja p1 = 0.2, p2 = 0.05, p3 = 0.1 i neuspešnog pretraživanja q0 = 0.15, q1 = 0.2, q2 = 0.1 i q3 = 0.2, odrediti i nacrtati optimalno stablo binarnog pretraživanja.
</div>

=== Rešenje ===
Formula je napisana i objašnjena u [[АСП2/К1 2019#8. zadatak|osmom zadatku na prvom kolokvijumu 2019. godine]].

Postoji pet rasporeda ovih čvorova (<math>p_i</math> označavaju ključeve a <math>q_i</math> eksterne čvorove stabla):
    p1
   /  \
 q0    p2
      /  \
    q1    p3
         /  \
       q2    q3
: <math>C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +</math>
: <math>+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =</math>
: <math>= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.05</math>
        p2
     /      \
    p1       p3
   /  \     /  \
 q0    q1 q2    q3
: <math>C = 2 \cdot 0.2 + 1 \cdot 0.05 + 2 \cdot 0.1 +</math>
: <math>+ 2 \cdot 0.15 + 2 \cdot 0.2 + 2 \cdot 0.1 + 2 \cdot 0.2 =</math>
: <math>= 0.4 + 0.05 + 0.2 + 0.3 + 0.4 + 0.2 + 0.4 = 1.95</math>
          p3
         /  \
       p2    q3
      /  \
    p1    q2
   /  \
 q0    q1
: <math>C = 3 \cdot 0.2 + 2 \cdot 0.05 + 1 \cdot 0.1 +</math>
: <math>+ 3 \cdot 0.15 + 3 \cdot 0.2 + 2 \cdot 0.1 + 1 \cdot 0.2 =</math>
: <math>= 0.6 + 0.1 + 0.1 + 0.45 + 0.6 + 0.2 + 0.2 = 2.25</math>
    p1
   /  \
 q0    p3
      /  \
    p2    q3
   /  \
 q1    q2
: <math>C = 1 \cdot 0.2 + 3 \cdot 0.05 + 2 \cdot 0.1 +</math>
: <math>+ 1 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 2 \cdot 0.2 =</math>
: <math>= 0.2 + 0.15 + 0.2 + 0.15 + 0.6 + 0.3 + 0.4 = 2</math>
       p3
      /  \
    p1    q3
   /  \
 q0    p2
      /  \
    q1    q2
: <math>C = 2 \cdot 0.2 + 3 \cdot 0.05 + 1 \cdot 0.1 +</math>
: <math>+ 2 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 1 \cdot 0.2 =</math>
: <math>= 0.4 + 0.15 + 0.1 + 0.3 + 0.6 + 0.3 + 0.2 = 2.05</math>
Ovim dobijamo da je optimalno stablo binarnog pretraživanja za ova tri ključa stablo u kojem je <math>K_2</math> u korenu.

== 2. zadatak ==
=== Postavka ===
Napisati u pseudokodu efikasnu iterativnu implementaciju funkcije koja u stablu binarnog pretraživanja na čiji koren ukazuje pokazivač ''root'' pronalazi sledbenika čvora koji sadrži ključ ''key''. U okviru čvora stabla ne postoji pokazivač na oca.

=== Rešenje ===
Ideja je da umesto ''inorder'' obilaska iskoristimo činjenicu da se sledbenik čvora sa ključem ''key'' može pronaći jednim spuštanjem niz stablo u pretrazi za ključem ''key''. Postoje dva slučaja:
# kada čvor sa ključem ''key'' ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i
# kada taj čvor nema desno podstablo, uzimamo poslednji čvor kod koga smo utvrdili da mu je ključ veći od ključa koji tražimo (poslednji čvor kod koga smo "otišli levo").
{{Милокод|<nowiki>
FIND BST SUCC(root, key)
p = root
succ = nil
while (key(p) ≠ key) do
    if (key(p) < key) then
        p = right(p)
    else if (key(p) > key) then
        succ = p
        p = left(p)
    end_if
end_while
if (right(p) ≠ nil) then
    p = right(p)
    while (p ≠ nil) do
        succ = p
        p = left(p)
    end_while
end_if
return succ
</nowiki>}}

== 3. zadatak ==
{{делимично решено}}
=== Postavka ===
[[Датотека:ASP2 K1 2018 zadatak 3 stablo.svg|thumb|Crveno-crno stablo iz postavke zadatka.]]
Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 81 i 79 i uklanjanja ključa 23.

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
U stablu binarne pretrage greškom su dva čvora zamenila svoje pozicije. Implementirati funkciju CORRECT_BST koja ispravlja grešku i vraća ova dva čvora na svoje prave pozicije. Svaki čvor osim celobrojnog ključa i pokazivača na levo i desno podstablo sadrži i pokazivač na oca.

=== Rešenje ===
Pod zamenom čvorova se ne misli samo na zamenu ključeva u tim čvorovima već na zamenu zajedno sa podstablima, tako da jedna zamena ne može imati kaskadne posledice već će samo dva čvora ostati nekonzistentna.

Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.
{{Милокод|<nowiki>
CORRECT BST(root)
STACK_INIT(S_nodes)
STACK_INIT(S_low)
STACK_INIT(S_high)
PUSH(S_nodes, root)
PUSH(S_low, -∞)
PUSH(S_high, +∞)
while not STACK_EMPTY(S_nodes) do
    node = POP(S_nodes)
    low = POP(S_low)
    high = POP(S_high)
    if low < key(node) < high then
        if left(node) ≠ nil then
            PUSH(S_nodes, left(node))
            PUSH(S_low, low)
            PUSH(S_high, key(node))
        end_if
        if right(node) ≠ node then
            PUSH(S_nodes, right(node))
            PUSH(S_low, key(node))
            PUSH(S_high, high)
        end_if
    else
        if first = nil then
            first = node
        else
            second = node
            break
        end_if
    end_if
end_while
tmp = parent(first)
parent(first) = parent(second)
parent(second) = tmp
if left(parent(first)) = second then
    left(parent(first)) = first
else
    right(parent(first)) = first
end_if
if left(parent(second)) = first then
    left(parent(second)) = second
else
    right(parent(second)) = second
end_if
</nowiki>}}

== 5. zadatak ==
=== Postavka ===
Neka se u prazno AVL stablo redom ubacuju ključevi 27, 12, 7, 34, 31, 5, 6, a zatim se brišu ključevi 31, 34, 12. Prilikom brisanja koristiti '''prethodnika'''. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.

=== Rešenje ===
Konačno stablo je:
     7
    / \
   6   27
  /
 5
Postupak možete simulirati u nekom od [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html simulatora] za AVL stabla.

== 6. zadatak ==
=== Postavka ===
Koristeći metodu binarne pretrage kao ideju, napisati u pseudokodu funkciju koja efikasno proverava da li je tačka T teme ''n''-tougla M. Mnogougao M se zadaje pomoću niza tačaka – temena. Tačke su određene koordinatama ''x'' i ''y''. Niz temena mnogougla je uređen rastuće po vrednosti koordinate ''x'', pri čemu za istu vrednost koordinate ''x'' važi rastuća uređenost po vrednosti koordinate ''y''.

=== Rešenje ===
Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je ''x'' koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je ''y'' koordinata veća od tražene, ide se ulevo, a ukoliko je ''x'' koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je ''y'' koordinata manja od tražene, ide se udesno.
{{Милокод|<nowiki>
CHECK VERTEX(M, n, T)
low = 1
high = n
while low ≤ high do
    mid = (high + low) / 2
    if (x(M[mid]) = x(T)) and (y(M[mid]) = y(T)) then
        return true
    else if (x(M[mid]) < x(T)) or ((x(M[mid]) = x(T)) and (y(M[mid]) < y(T))) then
        low = mid + 1
    else
        high = mid - 1
    end_if
end_while
return false
</nowiki>}}
Postupak se mogao pojednostaviti ukoliko se pretpostavi da ne može postojati više od dve tačke sa istom ''x'' koordinatom, jer bi u tom slučaju te tačke bile kolinearne i ne bi mogle da budu temena ''n''-tougla.

== 7. zadatak ==
=== Postavka ===
Dat je neuređeni niz ''A'' dužine ''n'' celobrojnih ključeva u opsegu vrednosti 1..100 koji se pretražuje i neuređeni niz ključeva ''K'' mnogo veće dužine ''m'' na koje se vrši pretraga. U nizu ''K'' ima veliki broj ponovljenih ključeva. Zbog neravnomerne verovatnoće pretrage ključeva, koristi se sledeća tehnika optimizacije. Nakon svakog uspešnog pretraživanja, vrši se prebacivanje za ''p'' pozicija unapred, gde je ''p'' broj uspešnih nalaženja tog ključa. Napisati u pseudokodu funkciju koja redom pretražuje niz ''A'' na ključeve iz niza ''K'' i vraća prosečan broj poređenja po nađenom ključu.

=== Rešenje ===
{{Милокод|<nowiki>
SEARCH(A, K, n, m)
for i = 1 to 100 do
    P[i] = 0
end_for
sum = 0
num = 0
for i = 1 to m do
    key = K[i]
    found = 0
    for j = 1 to n do
        if A[j] = key then
            found = j
            break
        end_if
    end_for
    if found ≠ 0 then
        sum = sum + j
        num = num + 1
        P[key] = P[key] + 1
        for k = found downto found - P[key] + 1 do
            A[k] = A[k-1]
        end_for
        A[found - P[key]] = key
    end_if
end_for
if num = 0 then
    return 0
else
    return sum/num
end_if
</nowiki>}}

== 8. zadatak ==
=== Postavka ===
Obrazložiti da li je sledeća sekvenca ključeva validna u stablu binarnog pretraživanja:
<div class="abc-list">
# Ako se prilikom uspešnog pretraživanja u jednom stablu redom proveravaju ključevi 23, 87, 158, 348, 160, 200, 150, 158.
# Ako se prilikom neuspešnog pretraživanja u drugom stablu redom proveravaju ključevi 546, 453, 427, 68, 415, 231, 247, 417, 300.
</div>

=== Rešenje ===
Ovde gledamo naš silazak niz potencijalni BST i na osnovu prethodno pogledanih čvorova određujemo granice ''high'' i ''low'' u kojima se moraju nalaziti naredni ključevi kako bi stablo bilo validan BST. Dobijamo da oba slučaja nisu moguća u binarnom stablu pretraživanja.
<div class="abc-list">
#
## 23 → 87, low = 23, high = +∞
## 87 → 158, low = 87, high = +∞
## 158 → 348, low = 158, high = +∞
## 348 → 160, low = 158, high = 348
## 160 → 200, low = 160, high = 348
## 200 → 150, 150 < low => ⚡
#
## 546 → 453, low = -∞, high = 546
## 453 → 427, low = -∞, high = 453
## 427 → 68, low = -∞, high = 427
## 68 → 415, low = 68, high = 427
## 415 → 231, low = 68, high = 415
## 231 → 247, low = 231, high = 415
## 247 → 417, 417 > high => ⚡
</div>

[[Категорија:АСП2]]
[[Категорија:Рокови]]