АСП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	25	28	40
1	1	0	1	0	0	0	1	0	1	1
Takođe je moguće da se, uz napomenu, pri nailasku na ključ veći od traženog gleda levo umesto desno.

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
Postoje dva načina na koji možemo da rešimo situaciju kad naiđemo na 40 i ne možemo da ga pomerimo udesno: kažemo da se desila greška pošto ne možemo dalje da umećemo, ili pomerimo ključ 28 ulevo (preporučeno).

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

Prvo dodajemo čvor 37 u stablo:

      50
     /  \
   30    60
  /  \
20    40
     /
   37

Pošto od dede do oca i od oca do sine vode grane u suprotnim smerovima, prvo rotiramo udesno oko čvora 40:

      50
     /  \
   30    60
  /  \
20    40
        \
         37

a zatim ulevo oko čvora 30:

         50
        /  \
      37    60
     /  \
   30    40
  /
20

Pošto još uvek nismo u korenu, rotiramo ulevo oko čvora 50:

      37
     /  \
   30    50
  /     /  \
20    40    60

Zatim dodajemo čvor 32:

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

Pošto od dede do oca i od oca do sine vode grane u suprotnim smerovima, prvo rotiramo ulevo oko čvora 30:

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

a onda udesno oko čvora 37:

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

Dodajemo čvor 34:

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

Pošto od dede do oca i od oca do sine vode grane u suprotnim smerovima, prvo rotiramo udesno oko čvora 37:

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

a zatim ulevo oko čvora 32:

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

Pretražujemo ključ 33 putem 34 → 32 → nil, pa 32 moramo da pomerimo do korena, tako da radimo rotaciju udesno oko 34:

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

Pretražujemo ključ 20 putem 32 → 30 → 20. Pošto grana od oca do sina i od dede do oca imaju isti smer, radimo rotaciju udesno oko 32.

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

a zatim rotaciju udesno oko 30:

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

Zatim brišemo čvor 60. Prvo radimo rotaciju ulevo oko 37:

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

a zatim rotaciju ulevo oko 50:

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

60 i dalje nije u korenu, tako da radimo rotaciju ulevo oko 32:

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

pa rotaciju ulevo oko 34:

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

60 i dalje nije u korenu, pa radimo rotaciju ulevo oko 20:

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

a zatim rotaciju ulevo oko 30:

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

Pošto 60 ima samo jedno dete, samo ga uklanjamo:

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

Zatim brišemo čvor 31, prolazeći putem 30 → 34 → 32 → nil. Pošto je 32 poslednji čvor kojem smo pristupili, njega guramo u koren tako da prvo radimo rotaciju udesno oko 34:

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

a zatim rotaciju ulevo oko 30, čime dobijamo...

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)
if key(prev) ≤ k then
    left = prev
    right = right(prev)
    right(left) = nil
else
    right = prev
    left = left(prev)
    left(right) = nil
end_if
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 = 1}^{n} p_i (h_i + 1) + \sum_{i = 0}^{n} 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.