АСП2/К1 2015

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Zadaci na stranici predmeta.

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   12
 /   /  \
3   7    15
 \   \     \
  4   9     18
     /     /
    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

Ovde je ideja da nagađamo na kom se delu duži, u procentima, nalazi presek s kružnicom. Za svako nagađanje računamo razdaljinu od centra i ako je veća od poluprečnika to znači da smo van kruga, odnosno da treba da idemo bliže tački T1, u suprotnom treba da idemo bliže tački T2. Parametar p nam ovde označava preciznost aproksimacije u procentima dužine duži.

INTERSECT(K, D)
p = 0.05
low = 0
high = 1
mid_x = 0
mid_y = 0
while high - low ≥ p do
    mid = (high + low) / 2
    mid_x = (x(T2) - x(T1)) * mid + x(T1)
    mid_y = (y(T2) - y(T1)) * mid + y(T1)
    diff = sqrt((mid_x - x(C)) * (mid_x - x(C)) + (mid_y - y(C)) * (mid_y - y(C)))
    if diff = r then
        return mid_x, mid_y
    else if diff < r then
        low = mid
    else
        high = mid
    end_if
end_while
return mid_x, mid_y

3. zadatak

Postavka

Stabla binarnog pretraživanja

  1. Na koji način se u stablo binarnog pretraživanja može dozvoliti umetanje ključeva sa istom vrednošću?
  2. 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:

  1. 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.
  2. Č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

  1. Definisati pojam crne visine (eng. black height) nekog čvora crveno-crnog stabla.
  2. 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

Датотека:ASP2 K1 2015 zadatak 6 stablo.png
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.

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

  1. 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.
    1. 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].
    2. Jedini kandidat za koren levog podstabla nam je K2, i zato njega postavljamo kao koren, K1 njegovo levo dete a K3 njegovo desno.
    3. 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