АСП2/К1 2015

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

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

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 (color(p) = 0) then // pretpostavili smo da je bit boje za crne čvorove jednak 0
        bh = bh + 1
    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  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
       \
        60

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.

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 $K_i, i = 1..6$, sa verovatnoćama uspešnog pretraživanja $p_i, i = 1..6$, (0.1, 0.05, 0.05, 0.1, 0.05, 0.1, respektivno) i verovatnoćama neuspešnog pretraživanja $q_i, i = 0..6$ (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.
2. 1. 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].
   2. 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.
   3. 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.
   4. 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