ASP2/K2 2019

Zadaci na stranici predmeta.

1. zadatak

Postavka

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

1. Dato binarno crveno-crno stablo transformisati u izomorfno 2-3-4 stablo. Osenčeni čvorovi su crni.
2. Iz stabla dobijenog pod a) brišu se ključevi 63 i 60. Nacrtati stabla dobijena nakon svakog od ova dva brisanja.
3. Ako se stablo dobijeno pod a) posmatra kao obično B stablo reda 4, da li bi bilo razlike u konačnom izgledu stabla nakon brisanja ključeva 63 i 60? Ukratko objasniti.

Rešenje

Ekvivalentno izomorfno 2-3-4 stablo je:

           [57|74|  ]
          /   |      \
[21|43|  ] [60|63|  ] [88|91|94]

Pri izbacivanju ključa 63, ključ 60 dolazi na njegovo mesto (i postaje crn).

           [57|74|  ]
          /     |    \
[21|43|  ] [  |60|  ] [88|91|94]

Pri izbacivanju ključa 60, vrši se pozajmljivanje od pravog brata, koji je ovde levi brat u izomorfnom 2-3-4 stablu, pa ključ 43 postaje razdelni a ključ 57 silazi u čvor iz kojeg se briše.

           [43|74|  ]
          /     |    \
[  |21|  ] [  |57|  ] [88|91|94]

Ekvivalentna crveno-crna stabla su data ispod.

Da je stablo bilo obično B stablo reda 4, u drugom koraku bi se pozajmljivalo od desnog brata umesto od levog brata, jer B stabla nemaju pravilo da se prvo pozajmljuje od pravog brata. Takođe, ključevi 21 i 57 ne bi stajali u središnjem polju čvora, već najlevljem.

• 

  Originalno crveno-crno stablo

• 

  Crveno-crno stablo nakon brisanja čvora 63

• 

  Crveno-crno stablo nakon brisanja čvora 60

2. zadatak

Postavka

U B+ stablo sa slike redom se umeću ključevi 6, 25, 21 i 27, nakon čega se uklanjaju ključevi 33, 27 i 6. Prikazati ažuriranje stabla po koracima.

            [33|64|  ]
          /     |     \
[20|22|33]->[42|64|  ]->[71|81|  ]

Rešenje

• Red stabla: $m = 4$
• Minimalni broj ključeva u unutrašnjim čvorovima: $\left\lceil\frac{m}{2}\right\rceil-1 = 1$
• Minimalni broj ključeva u listovima: $\left\lfloor\frac{m}{2}\right\rfloor = 2$

Ključ 6 se umeće levo od čvora 20. Dolazi do preloma i 6 i 20 ostaju u čvoru, 20 ide u roditelja, a 22 i 33 se odvajaju u novi čvor.

                  (20|33|64)
            /        |  |     \
[ 6|20|  ]->[22|33|  ]->[42|64|  ]->[71|81|  ]

Ključ 25 se umeće između ključeva 22 i 33.

                  (20|33|64)
            /        |  |     \
[ 6|20|  ]->[22|25|33]->[42|64|  ]->[71|81|  ]

Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 64.

                         (22|  |  )
                      /              \
          (20|  |  )                   (33|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|33|  ]->[42|64|  ]->[71|81|  ]

Ključ 27 se umeće između ključeva 25 i 33.

                         (22|  |  )
                      /              \
          (20|  |  )                   (33|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|27|33]->[42|64|  ]->[71|81|  ]

Pri uklanjanju ključa 33, pošto je najveći ključ u čvoru, mora se ažurirati roditeljski čvor tako da 33 u roditeljskom čvoru postaje 27.

                         (22|  |  )
                      /              \
          (20|  |  )                   (27|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|27|  ]->[42|64|  ]->[71|81|  ]

Pri uklanjanju ključa 27, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od oba brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu se takođe izbacuje ključ iz roditeljskog čvora.

                         (22|  |  )
                      /              \
          (20|  |  )                   (64|  |  )
         /   |                    /       |
[ 6|20|  ]->[21|22|  ]->[25|42|64]->[71|81|  ]

Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:

            (22|64|  )
          /    |       \
[20|21|22]->[25|42|64]->[71|81|  ]

3. zadatak

Postavka

Dato digitalno stablo je potrebno transformisati u kompaktniju formu kako bi se smanjila veličina stabla.

1. Predložiti i objasniti način na koji se može ostvariti transformacija digitalnog stabla u kompaktniju formu i prikazati izgled digitalnog stabla nakon opisane transformacije.
2. Implementirati funkciju TRIE COMPACTION koja transformiše stablo na prethodno opisani način. Pokazivač na koren stabla root je prosleđen funkciji. Smatrati da je digitalno stablo predstavljeno po principu levi sin - desni brat.

      A
   /  |  \
  B   C   S
  |   |   |
  K   J   4
 / \  |   |
D   T M   6
|   | |   |
9   * *   A
|         |
3         *
|
*

Rešenje

Kompaktnija forma ovog stabla može se dobiti tako što sve čvorove koji imaju samo jednu putanju do listova zamenimo sa listovima koji sadrže pokazivače na zapise na koje su listovi prethodno pokazivali i celu vrednost ključa. U tom slučaju ne mora da postoji čvor za kraj ključa.

TRIE COMPACTION(root)
if root ≠ nil then
    compacted_root = COMPACT(root, "")
    if compacted_root ≠ nil then
        root = compacted_root
    end_if
end_if
COMPACT(node, str)
if key(node) = '*' then
    FREENODE(node)
    return str
end_if
compacted_child = COMPACT(left(node), str + key(node))
if right(node) = nil then
    FREENODE(node)
    return compacted_child
else
    COMPACT(right(node), str)
    if compacted_child ≠ nil then
        left(node) = compacted_child
    end_if
    return nil
end_if

4. zadatak

Postavka

Napisati u pseudokodu funkciju koja iz 'top-down' stabla m-arnog pretraživanja na čiji koren pokazuje pokazivač root briše zadati ključ key.

Rešenje

DELETE(root, m, key)
parent = nil
parent_index = 0
p = root
i = 0
found = false
while (p ≠ nil) and (not found) do
    for i = 1 to num(p) do
        if keys(p)[i] = key then
            found = true
            break
        else if keys(p)[i] > key then
            parent = p
            parent_index = i
            p = pointers(p)[i-1]
            break
        end_if
    end_for
    if i = num(p) + 1 then
        p = pointers(p)[i-1]
    end_if
end_while
if p = nil then
    ERROR(Ključ nije pronađen)
end_if
q = pointers(p)[i]
if q ≠ nil then
    prev = p
    while q ≠ nil do
        parent = prev
        parent_index = 1
        prev = q
        q = pointers(q)[0]
    end_while
    keys(p)[i] = key(prev)
    p = prev
    i = 1
end_if
for j = i to num(p) do
    keys(node)[i-1] = keys(node)[i]
end_for
num(p) = num(p) - 1
if num(p) = 0 then
    FREENODE(p)
    pointers(parent)[parent_index-1] = nil
end_if

5. zadatak

Postavka

U B* stablo reda 5 sa slike se umeću ključevi 18, 23, 7, 37, 19. Nakon toga se redom brišu ključevi 80, 55, 18, 9 i 15. Nacrtati izgled stabla nakon svake izmene.

                            [15|24|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|20|21|  ] [27|33|40|  ] [55|75|  |  ] [93|96|  |  ]

Rešenje

• Red stabla: $m = 5$
• Minimalan broj ključeva u ne-korenskim čvorovima: $\left\lceil\frac{2m - 1}{3}\right\rceil-1 = 3 - 1 = 2$
• Maksimalan broj ključeva u korenu: $2\left\lfloor\frac{2m - 2}{3}\right\rfloor = 4$
• Raspodela ključeva pri prelomu: 2-3-3

Ključ 18 umećemo između ključeva 16 i 20.

                            [15|24|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|18|20|21] [27|33|40|  ] [55|75|  |  ] [93|96|  |  ]

Ključ 23 umećemo desno od ključa 21. Dešava se prelivanje u desni čvor, 23 završava u roditelju a 24 u desnom čvoru.

                            [15|23|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|18|20|21] [24|27|33|40] [55|75|  |  ] [93|96|  |  ]

Ključ 7 umećemo između ključeva 2 i 9.

                            [15|23|41|80]
             /             /      |      \             \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|40] [55|75|  |  ] [93|96|  |  ]

Ključ 37 umećemo između ključeva 33 i 40. Dešava se prelivanje u desni čvor, 40 završava u roditelju a 41 u desnom čvoru.

                            [15|23|40|80]
             /             /      |      \             \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|37] [41|55|75|  ] [93|96|  |  ]

Ključ 19 umećemo između ključeva 18 i 20. Prelivanje u levog i desnog brata je nemoguće, pa se dešava prelom. Ključevi 16 i 18 ostaju u čvoru, 19 ide u roditeljski čvor, 20, 21 i 23 idu u novi čvor, 24 ide u roditeljski čvor i 27, 33 i 37 ostaju u desnom bratu. Prelom se dešava i u roditeljskom čvoru, tako da 15 i 19 idu u levo dete novog korena, 24 ide u novi koren a 40 i 80 idu u desno dete novog korena.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [40|80|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|37|  ] [41|55|75|  ] [93|96|  |  ]

Ključ 80 menjamo svojim sledbenikom, 93, pa ga brišemo iz lista. U listu ostaje nedovoljno mnogo ključeva, pa vršimo pozajmicu od levog brata. Tom prilikom se ključ 93 vraća nazad u list u kojem je bio a 75 dolazi na mesto gde je ranije bio ključ 80.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [40|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|37|  ] [41|55|  |  ] [93|96|  |  ]

Pri brisanju ključa 55 iz lista ostaje nedovoljno ključeva, pa pozajmljujemo od levog brata. Tom prilikom ključ 37 dolazi na mesto 40 u roditeljskom čvoru a 40 se spušta u list.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

Pri brisanju ključa 18 iz lista ostaje nedovoljno ključeva, pa pozajmljujemo od desnog brata. Tom prilikom ključ 20 ide u roditeljski čvor a ključ 19 se spušta u list.

                                                [24|  |  |  ]
                                       /                      \
              [15|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

Brišemo ključ 9 iz lista.

                                                [24|  |  |  ]
                                       /                      \
              [15|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7|10|  ] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

Ključ 15 menjamo svojim sledbenikom, 16, pa brišemo ključ iz lista. U tom listu ostaje nedovoljno mnogo ključeva, pa se pozajmljuje od levog brata tako što se ključ 16 vrati na svoje prethodno mesto a ključ 10 ode u roditeljski čvor.

                                                [24|  |  |  ]
                                       /                      \
              [10|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7|  |  ] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

6. zadatak

Postavka

Posmatra se baza podataka studenata.

1. Ukoliko se zna da je najčešći upit nad zadatom bazom dohvatanje svih studenata koji su fakultet upisali u zadatom periodu (između dve godine), predložiti strukturu podataka koja bi podržala efikasno izvršavanje ovakvog upita i detaljno opisati razloge.
2. Implementirati funkciju FIND_STUDENTS_IN_RANGE koja nad odabranom strukturom vrši pretragu i vraća rezultat upita navedenog pod tačkom a). Parametri funkcije su pokazivač na odabranu strukturu, početna godina i krajnja godina traženog perioda, respektivno. Rezultat vratiti u formi niza.

Rešenje

Struktura koja se ovde može upotrebiti je B+ stablo, jer nam dozvoljava lak sekvencijalni pristup (za izlistavanje svih studenata u rasponu od dve godine) kao i brzo pronalaženje prvog ključa (za prvog studenta iz raspona). Ključevi ovakvog stabla mogu biti kombinacija godine i broja indeksa studenta, tako da je godina primarni a broj indeksa sekundarni ključ.

FIND STUDENTS IN RANGE(structure, year1, year2)
p = structure
while (not IS_LEAF(p)) do
    for i = 1 to num(p) do
        if keys(p)[i] > year1 then
            p = pointers(p)[i-1]
            break
        end_if
    end_for
    if i = num(p)+1 then
        p = pointers(p)[num(p)]
    end_if
end_while
length = 0
q = p
key_index = 1
while (q ≠ nil) and (years(q)[key_index] ≤ year2) do
    length = length + 1
    if node_index = num(q) then
        key_index = 1
        q = next(q)
    else
        key_index = key_index + 1
    end_if
end_while
arr = ALLOCATE(length)
for i = 1 to length do
    j = 1
    while j < num(p) and i < length do
        arr[i] = students(p)[j]
        i = i + 1
        j = j + 1
    end_while
    p = next(p)
end_for
return arr

7. zadatak

Postavka

Neka se za indeksnu strukturu datoteke koristi B stablo reda m. U okviru datoteke se smeštaju zapisi veličine 256 bitova zajedno sa 32-bitnim poljem ključa. Neka se na datom sistemu adrese predstavljaju na 64 bita. Odrediti vrednosti m u zavisnosti od toga da li se u čvoru B stabla smešta samo ključ ili čitav podataka, pod pretpostavkom da je veličina bloka na disku 2KB. Diskutovati rešenje.

Rešenje

Jedan čvor B stabla mora stati u jedan blok na disku, što je 2KiB, odnosno 2048B, odnosno 16384b. Zapis čvora obuhvata:

• $m-1$ ključeva (32b) zajedno sa adresama njihovih zapisa (64b), odnosno u drugoj varijanti ceo zapis (256b)
• $m$ adresa (64b) podstabala

Tako je veličina jednog čvora stabla u prvoj varijanti jednaka $(m-1) \cdot (32 + 64) + m \cdot 64 = m \cdot 96 + m \cdot 64 - 96 = m \cdot 160 - 96$. Ako pretpostavimo da je ovo jednako veličini bloka, dobijamo $m \cdot 160 = 16480 \implies m = \frac{16480}{160} = 103$.

U drugoj varijanti, ako pretpostavimo da se ključ može zaključiti iz strukture pa se ne čuva odvojeno, veličina čvora je jednaka $(m-1) \cdot 256 + m \cdot 64 = m \cdot 256 - 256 + m \cdot 64 = m \cdot 320 - 256$. Sa istom pretpostavkom dobijamo $m \cdot 320 = 16640 \implies m = \frac{16640}{320} = 52$.

8. zadatak

Postavka

Heširanje.

1. Kako funkcioniše metod deljenja i koje su njegove osnovne osobine? Koje vrednosti delioca treba izbegavati?
2. Neka je dat skup ključeva 19, 10, 4, 37, 49, 52. Ukoliko je poznatao da se prilikom heširanja koristi metod deljenja i veličina tabele n = 9, komentarisati izbor veličine tabele u odnosu na verovatnoću mogućih kolizija zadatog skupa ključeva. Predložiti alternativnu, blisku veličinu tabele kako bi se verovatnoća kolizija smanjila.

Rešenje

Metod deljenja funkcioniše tako što heš funkcija ima oblik $h(K) = K mod n$, gde je $n$ broj ulaza tabele. Loši brojevi $n$ su parni brojevi, brojevi deljivi s 10 i, ako su svi ključevi kongurentni po modulu $d$, brojevi koji nisu uzajamno prosti sa $d$.

Za dati skup ključeva dobijamo sledeću tabelu:

Heš tabela nakon umetanja datog skupa ključeva

0	1	2	3	4	5	6	7	8
	19 10 37			4 49			52

Ovde se kolizija desila u 50% slučajeva. Predlažemo malo izmenjen broj ulaza $n = 8$:

Heš tabela nakon umetanja datog skupa ključeva s predloženom heš funkcijom

0	1	2	3	4	5	6	7
	49	10	19	4 52	37

Ovde se kolizija dešava u 16.66% slučajeva.