АСП2/К1 2016

Zadaci na stranici predmeta.

1. zadatak

Postavka

Ako je inorder obilaskom nekog stabla binarnog pretraživanja dobijen niz ključeva 1 5 8 9 11 14 prikazati tri moguća izgleda ovog stabla sa: (a) najmanjom visinom, (b) najvećom visinom i (c) visinom između najmanje i najveće. Obeležiti stablo sa najboljim i najlošijim performansama operacija.

Rešenje

Stablo A ima najbolje performanse operacija:

    9
   / \
  5   11
 / \    \
1   8    14

Stablo B ima najlošije performanse operacija:

1
 \
  5
   \
    8
     \
      9
       \
        11
          \
           14

Stablo C nema ni najbolje ni najlošije performanse operacija:

        11
       /  \
      9    14
     /
    8
   /
  5
 /
1

2. zadatak

Postavka

Dat je niz celih brojeva. Koristeći stablo binarnog pretraživanja, napisati funkciju koja menja svaki element njegovim sledbenikom. U slučaju da element nema sledbenika, zadržati originalnu vrednost. Rezultat funkcije je niz preuredjen na opisani način.

Rešenje

Ovde prvo prebacujemo zadati niz u binarno stablo pretraživanja koristeći funkciju za umetanje čvora a zatim za svaki element niza pronalazimo sledbenika slično kao u drugom zadatku sa prvog kolokvijuma 2018.

ARR TRANSFORM(arr, n)
bst = nil
for i = 1 to n do
    BST-INSERT(bst, arr[i])
end_for
for i = 1 to n do
    key = arr[i]
    p = bst
    prev = nil
    while (p ≠ nil) and (key(p) ≠ key) do
        if key(p) > key then
            prev = p
            p = left(p)
        else
            p = right(p)
        end_if
    end_while
    p = right(p)
    while p ≠ nil do
        prev = p
        p = left(p)
    end_while
    if prev ≠ nil then
        arr[i] = key(prev)
    end_if
end_for

BST-INSERT(bst, key)
node = GETNODE
key(node) = key
if bst = nil then
    bst = node
else
    p = bst
    while true do
        if key(p) > key then
            if left(p) = nil then
                left(p) = node
                break
            else
                p = left(p)
            end_if
        else
            if right(p) = nil then
                right(p) = node
                break
            else
                p = right(p)
            end_if
        end_if
    end_while
end_if

3. zadatak

Postavka

Neka je dat rastuće uređeni niz celih brojeva (npr., 1 2 3 5 7 9) ili neka njegova rotacija (npr., 5 7 9 1 2 3). Vrednosti se ne ponavljaju u nizu. Napisati u pseudokodu iterativnu funkciju koja na efikasan način pronalazi minimalnu vrednost u nizu.

Rešenje

Ovaj problem se svodi na binarnu pretragu sa izmenjenim uslovima: sada detektujemo da li se nalazimo levo ili desno od tražene vrednosti poredeći se sa prvim elementom (ukoliko je trenutni element veći od prvog, levo smo od tražene vrednosti) a detekciju tražene vrednosti tako što proverimo da li je element levo od trenutnog veći od njega (to znači da smo došli na početak nerotiranog niza).

FIND MIN(arr, n)
low = 1
high = n
if arr[1] ≤ arr[n] then
    return arr[1]
end_if
while low ≤ high do
    mid = (high + low) / 2
    if arr[mid] < arr[mid-1] then
        return arr[mid]
    else if arr[mid] < arr[1] then
        high = mid - 1
    else
        low = mid + 1
    end_if
end_while

4. zadatak

Postavka

Binarno pretraživanje u povećanoj tabeli

1. Objasniti na koji način se vrši umetanje i brisanje u povećanoj tabeli.
2. Data je povećana tabela uređena neopadajuće i odgovarajući vektor sa bitovima validnosti. Na slici je prikazano trenutno stanje. Prikazati izgled povećane tabele i vektora validnosti nakon umetanja svakog od kljuceva: 6, 29 i 35, a zatim ukloniti ključeve : 18 i 23 i prikazati finalno stanje.

Početno stanje povećane tabele

5	5	9	18	22	22	23	25	28	38	40
1	0	0	1	0	0	0	1	0	1	0

Rešenje

Umetanje se vrši tako što prvo uradimo (binarnu) pretragu za neki ključ i ako utvrdimo da postoji (da postoji ključ sa traženom vrednošću u tabeli i da mu je bit validnosti postavljen na 1) bacamo grešku, u suprotnom proveravamo bit validnosti na polju do kojeg smo došli: ako je 1, moramo pomeriti sve validne ključeve koji slede nakon tog polja za jedno mesto unapred kako bismo mogli da ubacimo ključ na to polje. Pri ubacivanju se bit validnosti tog ključa postavi na 1, svi sledeći nevalidni ključevi se postave na tu vrednost a svi prethodni na vrednost prethodnog validnog ključa.

Pri brisanju se nakon pretrage za dati ključ, bit validnosti ključa samo postavi na 0 ukoliko postoji ili baci greška ukoliko ne postoji.

Stanje povećane tabele nakon unosa ključa 6

5	6	6	18	22	22	23	25	28	38	40
1	1	0	1	0	0	0	1	0	1	0

Stanje povećane tabele nakon unosa ključa 29

5	6	6	18	22	22	23	25	25	29	38
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 povećane tabele nakon unosa ključa 35

5	6	6	18	22	22	23	25	29	35	38
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 38 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č 29 ulevo (preporučeno).

Stanje povećane tabele nakon uklanjanja ključa 18

5	6	6	18	22	22	23	25	29	35	38
1	1	0	0	0	0	0	1	1	1	1

Brisanjem ključa 23 dešava se greška jer taj ključ ne postoji.

5. zadatak

Postavka

Dato je stablo binarnog pretraživanja. Da li stablo zadato na slici zadovoljava kriterijum AVL stabla? Ukoliko ne, izvršiti balansiranje stabla po AVL kriterijumu, a zatim iz dobijenog stabla obrisati ključeve 55 i 20, pa u stablo umetnuti ključ 30. Prilikom brisanja, koristiti sledbenika. Prikazati izgled stabla nakon svake izvršene izmene.

        20
       /  \
     17    32
    /     /  \
  10    25    33
 /     /  \     \
5     22  27     57
                /  \
               55  71

Rešenje

Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:

      20
    /    \
  10      32
 /  \    /  \
5   17 25    33
      /  \     \
     22  27     57
               /  \
              55  71

čime taj čvor više nije kritičan, ali zbog skraćivanja dužine levog podstabla čvor 20 postaje kritičan. Zatim radimo levu rotaciju oko čvora 33:

      20
    /    \
  10       32
 /  \    /    \
5   17 25      57
      /  \    /  \
     22  27  33   71
               \
                55

čime čvor 33 više nije kritičan. Na kraju, radimo levu rotaciju oko čvora 20:

             32
          /      \
      20           57
   /      \       /  \
  10      25    33    71
 /  \    /  \     \
5   17  22  27     55

Briše se čvor 55. Čvor je list tako da je brisanje trivijalno. Stablo ostaje balansirano nakon brisanja ovog čvora.

             32
          /      \
      20           57
   /      \       /  \
  10      25    33    71
 /  \    /  \      
5   17  22  27

Brišemo čvor 20. Na njegovo mesto stavljamo njegovog sledbenika 22.

             32
          /      \
      22           57
   /      \       /  \
  10      25    33    71
 /  \       \      
5   17      27

Umećemo čvor 30 kao desnog sina 27.

             32
          /      \
      22           57
   /      \       /  \
  10      25    33    71
 /  \       \      
5   17       27
               \
                30

Njegovim umetanjem čvor 25 postaje kritičan pa zato radimo rotaciju ulevo oko njega i time dobijamo...

Konačno stablo:

             32
          /      \
      22           57
   /      \       /  \
  10      27    33    71
 /  \    /  \      
5   17 25    30

6. zadatak

Postavka

Crveno-crno stablo iz postavke zadatka.

U crveno-crnom stablu sa slike se najpre izvrši brisanje ključa 35, a zatim umetanje ključeva 9, 43, 10. Prikazati izgled stabla nakon svake od navedenih promena.

7. zadatak

Postavka

1. U pseudokodu napisati funkciju koja za AVL stablo zadate visine h izračunava najmanji broj čvorova koje stablo može da sadrži.
2. Na kojoj visini može da se nalazi list najbliži korenu?
3. Kako se nazivaju ovakva stabla i po čemu su dobila ime?

Rešenje

1. Pseudokod je dat ispod.
2. ceil(h / 2). Ovo je zato što su podstabla Fibonačijevih stabala isto Fibonačijeva stabla, tako da se najmanja visina lista izračunava kao najmanja visina lista Fibonačijevog stabla čija je visina za 2 manja od trenutnog uvećana za 1.
3. Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima čija se rekurzivna definicija veoma malo razlikuje od rekurzivne definicije broja čvorova ovakvih stabala u zavisnosti od njihove visine.

AVL MIN NODES(h)
if h = 0 then
    return 1
else if h = 1 then
    return 2
else
    return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1
end_if

8. zadatak

Postavka

Za stablo binarnog pretraživanja koje sadrži ključeve K1 < K2 < ... < Kn i čiji je koren ključ Kr izvesti vezu cene stabla i cena podstabla. Obavezno objasniti postupak.

Rešenje

Cena podstabla se definiše kao:

$C_{ij} = \sum_{k = i+1}^j p_k (h_k + 1) + \sum_{k = i}^j q_k h_k$

gde su $p_i$ verovatnoće uspešnog, $q_i$ neuspešnog pretraživanja a $h_i$ visine čvorova $K_i$.

Uzimamo da su prvi čvor levog podstabla i poslednji čvor desnog podstabla trenutnog čvora po inorder poretku $K_i$ i $K_j$ a trenutni čvor $K_k$. Pošto je visina u formuli za cene levog i desnog podstabla sada povećana za 1, dobijamo da je ukupna cena trenutnog čvora jednaka:

$C_{ij} = \left(\sum_{m = i+1}^{k-1} p_m (h_m + 2) + \sum_{m = i}^{k-1} q_m (h_m + 1)\right) + p_k + \left(\sum_{m = k+1}^{j} p_m (h_m + 2) + \sum_{m = k}^{j} q_m (h_m + 1)\right) =$

$= \left(\sum_{m = i+1}^{k-1} p_m (h_m + 1) + \sum_{m = i+1}^{k-1} p_m + \sum_{m = i}^{k-1} q_m h_m + \sum_{m = i}^{k-1} q_m\right) + p_k + \left(\sum_{m = k+1}^{j} p_m (h_m + 1) + \sum_{m = k+1}^{j} p_m + \sum_{m = k}^{j} q_m h_m + \sum_{m = k}^{j} q_m\right) =$

$= \left(\sum_{m = i+1}^{k-1} p_m (h_m + 1) + \sum_{m = i}^{k-1} q_m h_m\right) + \left(\sum_{m = k+1}^{j} p_m (h_m + 1) + \sum_{m = k}^{j} q_m h_m\right) + w_{ij} =$

$= C_{i,k-1} + C_{k,j} + w_{ij}$