АСП2/К2 2016

Postavka zadataka na stranici predmeta.

1. zadatak

Postavka

U digitalno stablo umetnuti ključeve 25, 23, 367, 3698, 3692, 4, a zatim obrisati ključeve 367 i 23. Koristiti reprezentaciju „najlevlji sin – desni brat“. Prikazati stablo nakon poslednjeg umetanja i brisanja.

Rešenje

Ispod su data stabla nakon poslednjeg umetanja i brisanja.

• 

  Stablo nakon poslednjeg umetanja.

• 

  Stablo nakon poslednjeg brisanja.

2. zadatak

Postavka

Izomorfizam crveno-crnih stabala i 2-3-4 stabala.

1. Na koji način se vrši umetanje u pun čvor 2-3-4 stabla da bi se očuvao izomorfizam sa crveno crnim stablima? Da li postoje razlike u odnosu na klasično B stablo?
2. U 2-3-4 stablo sa slike umetnuti ključeve 30 i 35. Nacrtati izgled stabla posle svake od izmena i označiti crvene i crne čvorove.

                 [25|44|58]
             /      |  |        \
[  |15|  ] [27|37|  ] [  |47|50] [  |60|  ]

Rešenje

Pri umetanju u pun čvor 2-3-4 stabla dešava se prelom. Razlika je u tome da crni ključ uvek ide u koren a trenutni čvor se razdvaja na dva čvora, u levom čvoru kao crni ključ dolazi levi crveni ključ prethodnog čvora, u desnom kao crni ključ dolazi desni crveni ključ prethodnog čvora a novoumetnuti ključ postaje crven u levom ili desnom čvoru u zavisnosti od toga da li je manji ili već od crnog ključa iz prethodnog čvora.

Ključ 30 umećemo u list i tom prilikom se ključ 37 pomera kao crveni.

                 [25|44|58]
             /      |  |        \
[  |15|  ] [27|30|37] [  |47|50] [  |60|  ]

Ključ 35 umećemo u taj isti list i tom prilikom se dešava prelom, 27 postaje crni ključ levog čvora, 37 postaje crni ključ desnog čvora, ključ 30 ide u koren a ključ 35 postaje levi crveni ključ desnog čvora. Prelom se dešava i u korenu, tako da 25 postaje crni ključ levog čvora, 58 postaje crni ključ desnog čvora, 44 ide u novi koren a 30 postaje desni crveni ključ levog čvora.

                        [  |44|  ]
                       /          \
           [  |25|30]                 [  |58|  ]
          /    |     \                   |  |
[  |15|  ] [  |27|  ] [35|37|  ] [  |47|50] [  |60|  ]

Bojenje ovde neće biti odrađeno, ali crni ključevi su 15, 27, 25, 44, 58, 47 i 60, a svi ostali su crveni.

3. zadatak

Postavka

Dato je B stablo reda m. Napisati u pseudokodu funkciju koja vrši pozajmicu ključeva prilikom brisanja. Ukoliko je pozajmica nemoguća, funkcija treba da signalizira grešku. Funkcija dobija pokazivač na čvor node za koji se pokušava pozajmica. Smatrati da svaki čvor sadrži pokazivač na oca i podatak o broju ključeva smeštenih u njemu.

Rešenje

Prvo proveravamo da li pozajmljujemo u čvoru koji se nalazi u praznom stablu ili u čvoru koji je koren i u tom slučaju signaliziramo grešku. Ukoliko se u čvoru nalazi dovoljan broj ključeva, pozajmica je nepotrebna pa samo izlazimo iz funkcije. Zatim, nalazimo koji je indeks trenutnog čvora u nizu pokazivača na decu njegovog roditelja i na osnovu toga pronalazimo njegovu braću, prvo desnog pa levog. Ako braća ne postoje ili nemaju dovoljno čvorova signaliziramo grešku, u suprotnom premeštamo ključeve i prevezujemo pokazivače.

B-DEL-BORROW(node)
min_nodes = ceil(m/2)-1
if (node = nil) or (parent(node) = nil) then
    ERROR(Borrow impossible)
end_if
if (num(node) ≥ min_nodes) then
    return
end_if
parent = parent(node)
for i = 0 to num(parent) do
    if pointers(parent)[i] = node then
        parent_index = i
        break
    end_if
end_for
if (parent_index < num(parent)) and (num(pointers(parent)[parent_index+1]) > min_nodes) then
    sibling = pointers(parent)[parent_index+1]
    keys(node)[num(node)+1] = keys(parent)[parent_index+1]
    keys(parent)[parent_index+1] = keys(sibling)[1]
    num(node) = num(node)+1
    num(sibling) = num(sibling)-1
    pointers(node)[num(node)] = pointers(sibling)[0]
    for i = 0 to num(sibling) do
        pointers(sibling)[i] = pointers(sibling)[i+1]
        if i < num(sibling) then
            keys(sibling)[i+1] = keys(sibling)[i+2]
        end_if
    end_for
else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then
    sibling = pointers(parent)[parent_index-1]
    for i = num(node) downto 0 do
        pointers(node)[i+1] = pointers(node)[i]
        if i < num(node) then
            keys(node)[i+2] = keys(node)[i+1]
        end_if
    end_for
    keys(node)[1] = keys(parent)[parent_index]
    keys(parent)[parent_index] = keys(sibling)[num(sibling)]
    pointers(node)[0] = pointers(sibling)[num(sibling)]
    num(node) = num(node)+1
    num(sibling) = num(sibling)-1
else
    ERROR(Borrow impossible)
end_if

4. zadatak

Postavka

Graf iz postavke 4. zadatka.

Neka se zbog uštede memorije za smeštanje ključeva koji imaju zajedničke sufikse umesto digitalnog stabla koristi usmereni aciklični graf, kao na slici. Objasniti na koji način bi se implementirale operacije pretraživanja i brisanja ključa.

Rešenje

Pretraživanje ključa se implementira isto kao i kod digitalnog stabla ako se za implementaciju grafa koristi lista susednosti. Brisanje ključa se vrši tako što prilikom pretraživanja pamtimo poslednji čvor sa izlaznim stepenom većim od 1 (kraj zajedničkog prefiksa) i prvi čvor sa ulaznim stepenom većim od 1 (početak zajedničkog sufiksa) i brišemo sve čvorove između ta dva. Ako ovaj drugi čvor ne postoji, brišemo sve od prvog do kraja ključa (sufiks je jedinstven) a ako ovaj prvi čvor ne postoji brišemo celo stablo (prefiks je jedinstven, što znači da postoji samo jedna reč u stablu).

5. zadatak

Postavka

Neki sistem datoteka koristi B+ stabla za indeksiranje datoteka unutar kataloga. Veličina čvora B+ stabla je 256b, a pokazivači zauzimaju 16b. Za smeštanje ključa B+ stabla koristi se 64b.

1. Za date parametre, odrediti maksimalni red stabla.
2. Neka se posmatra katalog u kojem već postoje datoteke, sa ključevima 6, 12, 18, 45, 58, 66, 73, 81. Pod pretpostavkom da su svi listovi popunjeni minimalnim brojem ključeva, nacrtati inicijalni izgled B+ stabla za indeksiranje takvog kataloga. Nakon toga, u katalog se dodaju datoteke sa ključevima 41, 53, 32, a potom se brišu datoteke sa ključevima 12 i 66. Nacrtati izgled stabla posle svakog umetanja i brisanja. Red stabla je određen vrednošću koja je izračunata u tački a).

Rešenje

Maksimalni red stabla je $m = 4$. Raspored memorije u čvoru dat je ispod.

Raspored memorije u čvoru B+ stabla.

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

16b

$p_0$

$k_1$

$p_1$

$k_2$

$p_2$

$k_3$

$p_3$

Pošto je minimalan broj ključeva u listu B+ stabla jednak $\left\lfloor\frac{m}{2}\right\rfloor = \left\lfloor\frac{4}{2}\right\rfloor = 2$, inicijalni izgled zadatog B+ stabla je:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|45|  ]->[58|66|  ]->[73|81|  ]

Ključ 41 se dodaje u list:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|41|45]->[58|66|  ]->[73|81|  ]

Ključ 53 se isto dodaje u list:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|41|45]->[53|58|66]->[73|81|  ]

Pri dodavanju ključa 32 dešava se prelom u listu, koji se razdvaja na listove sa 18 i 32 i sa 41 i 45, a ključ 32 odlazi u koren. Pošto je i koren pun, dešava se prelom i 12 ostaje u levom čvoru, 32 odlazi u novi koren a 45 i 66 idu u desni čvor.

                      (32|  |  )
                  /               \
      (12|  |  )                    (45|66|  )
      |   \                       /    |     \
[6 |12|  ]->[18|32|  ]->[41|45|  ]->[53|58|66]->[73|81|  ]

Pri brisanju ključa 12 pozajmica je nemoguća, pa se spajaju dva lista i na sledećem nivou se dešava pozajmica od desnog brata, čime se pozajmljuje ključ 45.

                  (45|  |  )
            /            \
      (32|  |  )              (66|  |  )
      |   \                   |   \
[6 |18|32]->[41|45|  ]->[53|58|66]->[73|81|  ]

Ključ 66 se briše iz lista i tom prilikom se ažurira roditeljski čvor.

                  (45|  |  )
            /            \
      (32|  |  )              (58|  |  )
      |   \                   |   \
[6 |18|32]->[41|45|  ]->[53|58|  ]->[73|81|  ]

6. zadatak

Postavka

Napisati u pseudokodu iterativnu implementaciju funkcije koja formira trie stablo svih podstringova stringa koji je prosledjen^[sic] kao argument toj funkciji. Data je pomoćna funkcija getPosition(chr), koja za prosledjeni^[sic] karakter chr vraća indeks odgovarajućeg pokazivača u čvoru trie stabla.

Rešenje

TRIE SUBSTRINGS(str)
root = GETNODE
for i = 1 to length(str) do
    node = root
    substr = ""
    for j = i to length(str) do
        substr = substr + str[j]
        pos = getPosition(str[j])
        if nodes(node)[pos] = nil then
            nodes(node)[pos] = GETNODE
        end_if
        node = nodes(node)[pos]
        value(node) = substr
    end_for
end_for
return root

7. zadatak

Postavka

Neka su ključevi neuniformne dužine i neka se oni u čvoru stabla m-arnog pretraživanja pakuju bez gubitka prostora.

1. Predložiti efikasnu organizaciju čvora koja dozvoljava najbrže pretraživanje ovakvog čvora.
2. Precizno nacrtati organizaciju čvora za stablo reda 6 koji trenutno sadrži ključeve IPSILON, DELTA, IKS, ALFA.

Rešenje

U čvor možemo dodati polje od m-2 celobrojnih vrednosti koje nam govore od koje memorijske lokacije počinje koji ključ. Na taj način, kad vidimo da se neki pretraživani ključ ne poklapa sa vrednošću u trenutnom polju, umesto da nastavimo da čitamo vrednost do sledećeg ključa možemo odmah da nađemo početak sledećeg ključa.

Organizacija čvora

4

9

12

12

12

A

L

F

A

D

E

L

T

A

I

K

S

I

P

S

I

L

O

N

8. zadatak

Postavka

Heširanje:

1. Analitički definisati osobinu uniformnosti heš funkcije u tabeli veličine n ulaza i objasniti je jednom rečenicom.
2. Ako je heš funkcija uniformna i ako je u tabeli sa n ulaza uneseno k ključeva, izvesti izraz koji predstavlja očekivani broj kolizija koje su se desile prilikom tih umetanja.

Rešenje

1. Uniformnost heš funkcije je osobina koja znači da je svaki od $n$ izlaza podjednako verovatan: $P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n$
2. Zamislimo da ključeve umećemo u tabelu jedan po jedan. Pošto je naša heš funkcija uniformna, prvih $n$ umetanja nećemo imati nijednu koliziju. Narednih $n$ umetanja ćemo imati jednu koliziju po umetanju, sledećih $n$ dve kolizije, i tako dalje. Ukupan broj puta koliko će se povećanje broja kolizija po ključu desiti jeste $m = \left\lfloor\frac{k}{n}\right\rfloor$, i on će na kraju biti povećan na $m$. To znači da će ukupan očekivani broj kolizija biti $n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot \frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)$. Drugi deo jednačine ima veze sa time što kada umetnemo $m \cdot n$ ključeva naš broj kolizija će biti jednak $m$, ali će nama i dalje ostati $k - m \cdot n$, odnosno $k \mod n$ ključeva koji nisu umetnuti (pri računanju $m$ smo zaokružili na manji broj) i na njima će broj kolizija biti $m$.