АСП2/К1 2019

Zadaci na stranici predmeta.

1. zadatak

Postavka

Data je neopadajuće uređena proširena tabela i odgovarajući vektor bitova validnosti. Prikazati izgled povećane tabele i vektora validnosti nakon umetanja svakog od ključeva: 5, 28 i 29, a zatim ukloniti ključeve: 14 i 15 i prikazati finalno stanje.

Stanje niza iz postavke zadatka

4	7	10	14	15	15	21	24	25	40	45
1	0	0	1	0	0	0	1	0	1	0

Rešenje

Stanje niza nakon unosa broja 5

4	5	5	14	15	15	21	24	25	40	45
1	1	0	1	0	0	0	1	0	1	0

Stanje niza nakon unosa broja 28

4	5	5	14	15	15	21	24	28	40	45
1	1	0	1	0	0	0	1	1	1	0

Stanje niza nakon unosa broja 29

4	5	5	14	15	15	21	24	28	29	40
1	1	0	1	0	0	0	1	1	1	1

Stanje niza nakon brisanja broja 14

4	5	5	14	15	15	21	24	28	29	40
1	1	0	0	0	0	0	1	1	1	1

Pri brisanju ključa 15 dešava se greška jer taj ključ ne postoji.

2. zadatak

Postavka

Neka je dat veoma veliki uređeni niz arr dužine n. Poznato je da verovatnoća pretraživanja ključeva monotono opada od početka ka kraju niza.

1. Predložiti i kratko objasniti tehniku binarnog pretraživanja koja obećava naveću^[sic] efikasnost pod zadatim uslovima.
2. Napisati u pseudokodu iterativnu implementaciju funkcije koja implementira binarno pretraživanje niza arr dužine n u skladu sa tehnikom predloženom pod a).

Rešenje

Način za efikasno binarno pretraživanje ovog niza jeste tako što se prvo ispituju ključevi na pozicijama $2^i, i \in \mathbb{N}, 2^m \leq 2^n \leq n$ i zatim kada se odrede $m, n \in \mathbb{N}$ tako da $arr[2^m] < k < arr[2^n]$ na intervalu od $2^m$ do $2^n$ se sprovodi binarna pretraga.

U postavci funkcije u zadatku nije bio dat parametar k, odnosno ključ koji se pretražuje, ali je ovde dodat.

BINARY SEARCH PROB(arr, n, k)
low = 1
high = 2
while (high ≤ n) and (arr[high] < k) do
    low = high
    high = 2 * high
end_while
if (high > n) then
    high = n
end_if
while (low ≤ high) do
    mid = (low + high) / 2
    if (arr[mid] = k) then
        return mid
    else if (arr[mid] < k) then
        low = mid + 1
    else
        high = mid - 1
    end_if
end_while
return nil

3. zadatak

Postavka

Na slici je dato stablo binarnog pretraživanja. Potrebno je transformisati ovo stablo u AVL stablo. Prikazati transformaciju stabla po koracima.

   25
  /  \
 9    38
     /  \
    36   49
   /    /
  31   42
 /    /  \
27   40   45
            \
             47

Rešenje

Prvo pronađemo kritične čvorove u stablu:

   25
  /  \
 9    38
     /  \
    36   49
   /    /
  31   42
 /    /  \
27   40   45
            \
             47

Zatim radimo rotaciju udesno oko čvora 36 (njegovo levo dete naginje na levu stranu):

  25
 /  \
9    38
   /    \
  31     49
 /  \   /
27  36 42
      /  \
     40   45
            \
             47

čime postižemo da čvor 36 više nije kritičan. Zatim radimo rotaciju ulevo oko čvora 42 (levo dete čvora 49 naginje na desnu stranu):

  25
 /  \
9    38
   /    \
  31     49
 /  \   /
27  36 45
      /  \
     42   47
    /
   40

pa rotaciju udesno oko čvora 49:

    25
  /    \
 9      38
      /    \
     31     45
    /  \   /  \
   27  36 42   49
         /    /
        40  47

čime postižemo da čvor 49 više nije kritičan. Na kraju radimo rotaciju ulevo oko čvora 25 (njegovo desno dete naginje na desnu stranu) i dobijamo...

Konačno stablo:

        38
    /        \
  25          45
 /  \        /  \
9    31     42   49
    /  \   /    /
   27  36 40  47

4. zadatak

Postavka

Na slici je prikazano stablo binarnog pretraživanja nakon brisanja ključa 19. Ako je poznato da se prilikom brisanja koristi prethodnik, prikazati sve moguće izglede stabla neposredno pre brisanja navedenog ključa.

    10
   /  \
  5   18
 /   /  \
3   14  20
     \
     15
      \
      17

Rešenje

    10
   /  \
  5   18
 /   /  \
3   14  19
     \   \
     15  20
      \
      17

     10
   /    \
  5      18
 /     /    \
3     14    20
       \    /
       15  19
        \
        17

    10
   /  \
  5   19
 /   /  \
3   18  20
    /
   14
    \
    15
     \
     17

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     15
      \
      17
       \
       18

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     18
     /
    15
     \
      17

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     15
      \
      18
      /
     17

5. zadatak

Postavka

Neka se u dato samopodešavajuće stablo redom ubacuju ključevi 37, 32, 34, nakon čega se pretražuje na ključeve 33 i 20, a zatim se brišu ključevi 60 i 31. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.

    50
   /  \
  30   60
 /  \
20  40

Rešenje

Konačno stablo:

      32
     /  \
   30    34
  /        \
20          50
           /
         37
           \
            40

6. zadatak

Postavka

Posmatra se samopodešavajuće stablo dato pokazivačem na koren root. Napisati pseudokod operacije split, koja od jednog datog stabla pravi dva nova tako da se u jednom stablu nalaze svi ključevi manji ili jednaki od zadatog ključa k, a u drugom stablu se nalaze svi ključevi veći od ključa k. Sam ključ k ne mora da se nalazi u početnom stablu. Smatrati da operacija SPLAY(x) koja vrši širenje zadatog čvora x postoji već implementirana.

Rešenje

SPLAY SPLIT(root, k)
if (root = nil) then
    return nil, nil
end_if
x = root
prev = left = right = nil
while (x ≠ nil) do
    prev = x
    if (key(x) = k) then
        break
    else if (key(x) < k) then
        x = right(x)
    else
        x = left(x)
    end_if
end_while
SPLAY(prev)
left = prev
right = right(prev)
right(left) = nil
return left, right

7. zadatak

Postavka

Napisati u pseudokodu iterativnu implementaciju funkcije koja u stablu binarnog pretraživanja na koje ukazuje pokazivač root pronalazi čvor koji sadrži najveći ključ koji je jednak ili manji od zadatog ključa key. Ključ key ne mora postojati u stablu.

Rešenje

FIND BST FLOOR(root, key)
largest = nil
p = root
while (p ≠ nil) do
    if (key(p) = key) then
        return key
    else if (key(p) < key) then
        largest = p
        p = right(p)
    else
        p = left(p)
    end_if
end_while
if (largest ≠ nil) then
    return key(largest)
end_if
return nil

8. zadatak

Postavka

Neka se posmatra stablo binarnog pretraživanja sa slike sa poznatim verovatnoćama uspešnog pretraživanja $p_i$ i neuspešnog pretraživanja $q_i$ u tabelama u prilogu.

   25
  /  \
12    33
  \
   19

$K_i$	12	19	25	33
$p_i$	0.2	0.2	0.15	0.05

$K_i$	$K_i < 12$	$12 < K_i < 19$	$19 < K_i < 25$	$25 < K_i < 33$	$33 < K_i$
$q_i$	0.05	0.1	0.15	0.05	0.05

1. Formalno definisati, a zatim izračunati cenu C ovog stabla.
2. Ukoliko se od ključeva u stablu formira suboptimalno stablo binarnog pretraživanja kod koga se koren bira tako da razlika težina levog i desnog podstabla bude minimalna, odrediti takvo stablo i obrazložiti odgovor.

Rešenje

Cena binarnog stabla pretraživanja definiše se kao: $C = \sum_{i = 0}^{n} (p_i (h_i + 1) + q_i h_i)$ gde su:

• $p_i$ verovatnoće pretraživanja za neki od postojećih ključeva ($i$ odgovara poziciji ključa u uređenom nizu ključeva),
• $q_i$ verovatnoće pretraživanja koje će završiti u jednom od eksternih čvorova stabla binarnog pretraživanja ($i$ odgovara poziciji eksternog čvora pri inorder obilasku svih eksternih čvorova) i
• $h_i$ odgovara nivou čvora.

S gornjom definicijom u vidu, stablu možemo docrtati eksterne čvorove:

      p3
    /    \
  p1      p4
 /  \    /  \
q1   p2 q4  q5
    /  \
   q2  q3

i zatim izračunati cenu po formuli:

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

$+ 2 \cdot 0.05 + 3 \cdot 0.1 + 3 \cdot 0.15 + 2 \cdot 0.05 + 2 \cdot 0.05 =$

$= 0.4 + 0.6 + 0.15 + 0.1 + 0.1 + 0.3 + 0.45 + 0.1 + 0.1 = 2.3$

U zavisnosti od izbora korena imaćemo različite čvorove u levom i desnom podstablu. Izračunavamo razliku težina u datom stablu kao $(p_1 + p_2 + q_1 + q_2 + q_3) - (p_4 + q_4 + q_5) = (0.2 + 0.2 + 0.05 + 0.1 + 0.15) - (0.05 + 0.05 + 0.05) = 0.7 - 0.15 = 0.55$. Prebacivanjem korena na čvor 33 vidimo da će doći do još manjeg balansa težina, stoga koren prebacujemo na čvor 19 i dobijamo stablo ispod:

      p2
    /    \
  p1      p3
 /  \    /  \
q1  q2  q3   p4
            /  \
           q4  q5

Za ovo stablo izračunavamo razliku težina kao $(p_1 + q_1 + q_2) - (p_3 + p_4 + q_3 + q_4 + q_5) = (0.2 + 0.05 + 0.1) - (0.15 + 0.05 + 0.15 + 0.05 + 0.05) = 0.35 - 0.45 = -0.1$. Sada vidimo da je balans veći i da je prešao na drugu stranu, tako da znamo da će prebacivanjem korena na čvor 12 balans biti manji.