АСП2/К1 2018

Zadaci na stranici predmeta.

1. zadatak

Postavka

Optimalno stablo binarnog pretraživanja

1. Navesti formulu za izračunavanje cene optimalnog stabla binarnog pretraživanja i objasniti je.
2. Ukoliko se posmatraju tri ključa $K_1 < K_2 < K_3$ 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.

Rešenje

Formula je napisana i objašnjena u osmom zadatku na prvom kolokvijumu 2019. godine.

Postoji pet rasporeda ovih čvorova ($p_i$ označavaju ključeve a $q_i$ eksterne čvorove stabla):

   p1
  /  \
q0    p2
     /  \
   q1    p3
        /  \
      q2    q3

$C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +$

$+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =$

$= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.05$

       p2
    /      \
   p1       p3
  /  \     /  \
q0    q1 q2    q3

$C = 2 \cdot 0.2 + 1 \cdot 0.05 + 2 \cdot 0.1 +$

$+ 2 \cdot 0.15 + 2 \cdot 0.2 + 2 \cdot 0.1 + 2 \cdot 0.2 =$

$= 0.4 + 0.05 + 0.2 + 0.3 + 0.4 + 0.2 + 0.4 = 1.95$

         p3
        /  \
      p2    q3
     /  \
   p1    q2
  /  \
q0    q1

$C = 3 \cdot 0.2 + 2 \cdot 0.05 + 1 \cdot 0.1 +$

$+ 3 \cdot 0.15 + 3 \cdot 0.2 + 2 \cdot 0.1 + 1 \cdot 0.2 =$

$= 0.6 + 0.1 + 0.1 + 0.45 + 0.6 + 0.2 + 0.2 = 2.25$

   p1
  /  \
q0    p3
     /  \
   p2    q3
  /  \
q1    q2

$C = 1 \cdot 0.2 + 3 \cdot 0.05 + 2 \cdot 0.1 +$

$+ 1 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 2 \cdot 0.2 =$

$= 0.2 + 0.15 + 0.2 + 0.15 + 0.6 + 0.3 + 0.4 = 2$

      p3
     /  \
   p1    q3
  /  \
q0    p2
     /  \
   q1    q2

$C = 2 \cdot 0.2 + 3 \cdot 0.05 + 1 \cdot 0.1 +$

$+ 2 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 1 \cdot 0.2 =$

$= 0.4 + 0.15 + 0.1 + 0.3 + 0.6 + 0.3 + 0.2 = 2.05$

Ovim dobijamo da je optimalno stablo binarnog pretraživanja za ova tri ključa stablo u kojem je $K_2$ 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:

1. kada čvor sa ključem key ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i
2. 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").

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

3. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

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.

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.

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

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 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.

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

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

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

8. zadatak

Postavka

Obrazložiti da li je sledeća sekvenca ključeva validna u stablu binarnog pretraživanja:

1. Ako se prilikom uspešnog pretraživanja u jednom stablu redom proveravaju ključevi 23, 87, 158, 348, 160, 200, 150, 158.
2. Ako se prilikom neuspešnog pretraživanja u drugom stablu redom proveravaju ključevi 546, 453, 427, 68, 415, 231, 247, 417, 300.

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.

1. 1. 23 → 87, low = 23, high = +∞
   2. 87 → 158, low = 87, high = +∞
   3. 158 → 348, low = 158, high = +∞
   4. 348 → 160, low = 158, high = 348
   5. 160 → 200, low = 160, high = 348
   6. 200 → 150, 150 < low => ⚡
2. 1. 546 → 453, low = -∞, high = 546
   2. 453 → 427, low = -∞, high = 453
   3. 427 → 68, low = -∞, high = 427
   4. 68 → 415, low = 68, high = 427
   5. 415 → 231, low = 68, high = 415
   6. 231 → 247, low = 231, high = 415
   7. 247 → 417, 417 > high => ⚡