АСП2/К2 2018

Zadaci na stranici predmeta.

1. zadatak

Postavka

U 2-3-4 stablo sa slike ubaciti ključeve 17 i 25 i prikazati ekvivalentno crveno-crno stablo.

           [  |23|45]
          /   |     \
[ 1|15|20] [28|36|  ] [  |72|  ]

Rešenje

Ekvivalentno crveno-crno stablo u rešenju 1. zadatka.

Ključ 17 dolazi između ključeva 15 i 20. Pošto je taj čvor pun, crni ključ 15 ide u roditeljski čvor, ključ 1 dolazi u sredinu i postaje crn, ključ 20 se odvaja u desni čvor i postaje crn a ključ 17 završava kao crveni ključ levo od ključa 20.

           [15|23|45]
          /   |     \
[  | 1|  ] [17|20|  ] [28|36|  ] [  |72|  ]

Ključ 25 dolazi levo od ključa 28.

                 [15|23|45]
             /      |  |      \
[  | 1|  ] [17|20|  ] [25|28|36] [  |72|  ]

2. zadatak

Postavka

B+-stabla

1. Prikazati maksimalno popunjeno B+-stablo reda m = 3 i visine h = 1. Odrediti za ovo stablo prosečan broj pristupa prilikom uspešne i neuspešne pretrage.
2. Posmatra se B+-stablo reda 4 koje sadrži 7 ključeva. Odrediti za ovo stablo srednji broj pristupa prilikom uspešne i neuspešne pretrage i obrazložiti odgovor.

Rešenje

       (2|4)
      /  |  \
[1|2]->[3|4]->[5|6]

2 je prosečan broj pristupa i pri uspešnoj i pri neuspešnoj pretrazi.

         (3|5| )
       /   |   \
[1|2|3]->[4|5| ]->[6|7| ]

Pretpostavljajući da se ovde radi o broju ključeva u listovima (pošto se ključevi iz unutrašnjih čvorova dupliciraju u listovima), prosečan broj pristupa je ponovo 2. Sve uspešne pretrage, kao i neuspešne, moraju završiti u listovima jer se samo u listovima nalaze pokazivači ka traženim strukturama, a visina ovako napravljenog stabla je 1.

3. zadatak

Postavka

Posmatra se trie stablo čiji su ključevi znakovni nizovi koji sadrže cifre u brojnom sistemu sa osnovom 10. Napisati u pseudokodu funkciju koja za dato stablo na čiji koren pokazuje pokazivač root računa razliku najvećeg i najmanjeg tako predstavljenog broja.

Rešenje

CALC(root)
if root = nil then
    return 0
end_if
min, max = CALC_R(root)
return max - min
CALC R(root)
min = +∞
max = -∞
for i = 0 to 9 do
    field = fields(root)[i]
    if field ≠ nil then
        if is_leaf(field) then
            f_max = f_min = value(field)
        else
            f_max, f_min = CALC_R(field)
        end_if
        if f_max > max then
            max = f_max
        end_if
        if f_min < min then
            min = f_min
        end_if
    end_if
end_for
return max, min

4. zadatak

Postavka

Posmatra se B stablo reda m u kojem su svi listovi minimalno popunjeni, a njihovi roditelji su popunjeni iznad minimuma. Iz takvog stabla se briše ključ key iz lista sa adresom node. Napisati iterativnu funkciju u pseudokodu za datu situaciju brisanja. Smatrati da u čvoru postoji pokazivač na roditelja i podatak o broju ključeva smeštenih u njemu.

Rešenje

B-DELETE-NO-BORROW(root, m, node, key)
child_index = 0
parent = parent(node)
for i = 0 to num(parent) do
    if pointers(parent)[i] = node then
        child_index = i
        break
    end_if
end_for
if child_index = num(parent) then
    left_node = pointers(parent)[child_index-1]
    num(left_node) = num(left_node) + 1
    keys(left_node)[num(left_node)] = keys(parent)[child_index]
    for i = 1 to num(node) do
        if keys(node)[i] ≠ key then
            num(left_node) = num(left_node) + 1
            keys(left_node)[num(left_node)] = keys(node)[i]
        end_if
    end_for
    FREENODE(node)
else
    right_node = pointers(parent)[child_index+1]
    offset = 0
    for i = 1 to num(node) do
        if keys(node)[i] = key then
            offset = 1
        else
            keys(node)[i-offset] = keys(node)[i]
        end_if
    end_for
    keys(node)[num(node)] = keys(parent)[child_index+1]
    for i = 1 to num(right_node) do
        num(node) = num(node) + 1
        keys(node)[num(node)] = keys(right_node)[i]
    end_for
    for i = child_index to num(parent)-1 do
        keys(parent)[i+1] = keys(parent)[i+2]
        pointers(parent)[i] = pointers(parent)[i+1]
    end_for
    FREENODE(right_node)
end_if
num(parent) = num(parent) - 1

5. zadatak

Postavka

U B* stablo reda 4 se umeću ključevi od 1 do 14. Nakon toga se redom brišu ključevi 4, 11 i 9. Nacrtati izgled stabla nakon svake izmene.

Rešenje

• Red stabla: $m = 4$
• Minimalni broj ključeva u ne-korenskom čvoru: $\left\lceil\frac{2m - 1}{3}\right\rceil - 1 = 2$
• Maksimalni broj ključeva u korenu: $2 \left\lfloor\frac{2m - 2}{3}\right\rfloor = 4$
• Raspodela ključeva pri prelomu: 2-2-2

Umećemo ključ 1 u prazno stablo.

[ 1|  |  |  ]

Umećemo ključ 2.

[ 1| 2|  |  ]

Umećemo ključ 3.

[ 1| 2| 3|  ]

Umećemo ključ 4.

[ 1| 2| 3| 4]

Pri umetanju ključa 5 dolazi do prelamanja čvora, tako da ključevi 1 i 2 idu u levi a 4 i 5 u desni čvor.

         [ 3|  |  |  ]
         |  |
[ 1| 2|  ] [ 4| 5|  ]

Umećemo ključ 6.

         [ 3|  |  |  ]
         |  |
[ 1| 2|  ] [ 4| 5| 6]

Pri umetanju ključa 7 desni čvor se prepunjuje, pa se dešava prelivanje u levi čvor. Ključ 3 iz roditeljskog čvora silazi u levi a ključ 4 iz desnog ide u roditeljski.

         [ 4|  |  |  ]
         |  |
[ 1| 2| 3] [ 5| 6| 7]

Pri umetanju ključa 8 desni čvor se ponovo prepunjuje, pa se dešava prelamanje. Ključevi 1 i 2 ostaju u levom čvoru, ključ 3 ide u roditeljski čvor, 4 i 5 dolaze u novi, srednji čvor, 6 ide u roditeljski čvor a 7 i 8 ostaju u desnom čvoru.

           [ 3| 6|  |  ]
          /   |     \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8|  ]

Umećemo ključ 9.

           [ 3| 6|  |  ]
          /   |     \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8| 9]

Pri umetanju ključa 10 dešava se prelivanje iz desnog u srednji čvor.

           [ 3| 7|  |  ]
          /   |     \
[ 1| 2|  ] [ 4| 5| 6] [ 8| 9|10]

Pri umetanju ključa 11 dešava se prelamanje.

             [ 3| 6| 9|  ]
           /    |    \        \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8|  ] [10|11|  ]

Umećemo ključ 12.

             [ 3| 6| 9|  ]
           /    |    \        \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8|  ] [10|11|12]

Pri umetanju ključa 13 dešava se prelivanje.

             [ 3| 6|10|  ]
           /    |    \        \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8| 9] [11|12|13]

Pri umetanju ključa 14 dešava se prelamanje.

                    [ 3| 6| 9|12]
           /         /    |    \        \
[ 1| 2|  ] [ 4| 5|  ] [ 7| 8|  ] [10|11|  ] [13|14|  ]

Pri brisanju ključa 4, zbog nemogućnosti pozajmice, spajanje tri čvora u dva.

                 [ 5| 9| 12 |]
           /         /      |        \
[ 1| 2| 3 ] [ 6| 7| 8 ]  [ 10|11| ] [13|14| ]

Pri brisanju ključa 11 moguća je pozajmica, ali od levog brata.

                 [ 5| 8| 12 |]
           /         /      |        \
[ 1| 2| 3 ] [ 6| 7|]  [ 9 |10| ] [13|14| ]

Pri brisanju ključa 9 moguća je pozajmica ali od brata sa udaljenošću dva.

                [ 3| 7| 12 |]
           /         /      |        \
[ 1| 2| ] [ 5| 6| ]  [ 8 |10| ] [13|14| ]

6. zadatak

Postavka

Dato je digitalno stablo formirano od nekog skupa ključeva tipa znakovnih nizova. Implementirati funkciju COUNT_KEYS koja pronalazi broj ključeva u stablu koji odgovaraju zadatom formatu znakovnog niza. Pokazivač na koren stabla i zadati format su prosleđeni kao parametri funkcije. Format znakovnog niza pored cifara i slova može sadržati i simbole koji imaju specijano značenje. Specijalni simboli su tačka (.) koja menja bilo koji znak niza i zvezda (*) koja predstavlja ponavljanje nekog znaka niza 0 ili više puta. Smatrati da se zvezda odnosi na prvi znak koji joj prethodi.

Primer:

skup ključeva u stablu: abccc4a, ab3a, aacda

format: abc*.a

rezultat: 2

Rešenje

COUNT KEYS(root, format)
len = STRING_LENGTH(format)
if len = 0 then
    if key(node) = EOK then
        return 1
    else
        return 0
    end_if
end_if
count = 0
for i = 1 to num(root) do
    node = pointers(root)[i]
    if (len > 1) and (format[2] = '*') then
        if (key(node) = format[1]) or (format[1] = '.') then
            count = count + COUNT_KEYS(node, format)
        end_if
    else if (key(node) = format[1]) or (format[1] = '.') then
        count = count + COUNT_KEYS(node, format + 1)
    end_if
end_for
if (len > 1) and (format[2] = '*') then
    count = count + COUNT_KEYS(root, format + 2)
end_if
return count

7. zadatak

Postavka

Neka se u top-down stablo m-arnog pretraživanja redom ubacuju ključevi k, 2k, 3k, …, nk, nk – 1, nk – 2, nk – 3, …, n(k – 1) +1. Nacrtati izgled stabla i odrediti visinu. Pretpostaviti da su n i k mnogo veći od m.

Rešenje

Nakon ubacivanja ključa nk dobiće se degenerisano stablo udesno, tj. jedino najdesniji pokazivači u svakom unutrašnjem čvoru će pokazivati na sledeći list, i većina ključeva će biti popunjena, tako da će visina stabla biti $\left\lceil\frac{n}{m - 1}\right\rceil$ a u listu će ostati $(m - 1) - (n \bmod (m - 1))$ slobodnih mesta. Nakon ubacivanja svih ključeva stablo će u listovima krenuti da raste ulevo iz listova, tako da će visina porasti na ukupno: $h = \left\lceil\frac{n}{m - 1}\right\rceil + \left\lceil\frac{n - 1 - (m - 1) + (n \bmod (m - 1))}{m - 1}\right\rceil$.

8. zadatak

Postavka

Heširanje.

1. Šta je minimalna savršena heš funkcija?
2. Za ključeve 54, 91, 57, 23 i 28 naći što jednostavniju minimalnu savršenu heš funkciju i ispisati je. Obrazložiti odgovor i nacrtati heš tabelu sa umetnutim ključevima.

Rešenje

1. Minimalna savršena heš funkcija je heš funkcija koja preslikava n ključeva u n ulaza tabele bez kolizije.
2. Jedna moguća savršena heš funkcija je $h(K) = \left\lfloor\frac{K}{2}\right\rfloor \mod 5$. Kad sortiramo ključeve, dobijamo redosled 23, 28, 54, 57. Možemo primetiti da su oni svi različiti po modulu 10, ali pošto tabela ima 5 ulaza možemo prvo podeliti ključeve sa dva pa uzeti vrednost po modulu 5. Tabela nakon primene ove heš funkcije je data ispod.

Tabela nakon primene heš funkcije

0	1	2	3	4
91	23	54	57	28