АСП2/К2 2017

Postavka zadataka na stranici predmeta.

1. zadatak

Postavka

U trie stablo umetnuti ključeve 35, 128, 1236, 1234 i 125, a zatim obrisati ključ 1234. Prikazati izgled stabla nakon poslednjeg umetanja i nakon brisanja. Izračunati prosečan broj pristupa pri uspešnoj pretrazi.

Rešenje

Ispod su data trie stabla nakon umetanja i nakon brisanja. Broj pristupa pri pretraživanju na ključ 35 je 3, pri pretraživanju na 128 i 125 je 4 a pri pretraživanju na 1236 je 5, tako da je prosečan broj pristupa pri uspešnom pretraživanju $\frac{3 + 4 + 4 + 5}{4} = 4$.

• 

  Trie stablo dobijeno nakon umetanja.

• 

  Trie stablo dobijeno nakon brisanja.

2. zadatak

Postavka

Neka se uz ključeve B stabla reda m čuva i broj pristupa podatku pridruženom tom čvoru. Ključevi čijim podacima se češće pristupa treba da se nađu što bliže korenu stabla. Objasniti kako bi trebalo modifikovati strukturu i operacije pretraživanja i brisanja da bi se to realizovalo.

3. zadatak

Postavka

Napisati u pseudokodu funkciju za umetanje ključa u B+ stablo reda m na čiji koren ukazuje pokazivač root. Pretpostaviti da otac lista u koji se vrši umetanje nije maksimalno popunjen. Smatrati da je struktura čvora fiksna i da čvor sadrži alociran prostor za maksimalan broj ključeva i pokazivača. Dodatno, svaki čvor sadrži pokazivač na oca i podatak o broju ključeva smeštenih u njemu.

Rešenje

Prvo pronalazimo list u koji umećemo, čuvajući indeks našeg podstabla u roditeljskom čvoru (parent_index) i bacajući grešku ukoliko naiđemo na postojeći ključ s istom vrednošću. Zatim formiramo stablo ukoliko roditeljski čvor ne postoji ili formiramo novi poredak ključeva u čvoru u pomoćnom nizu (arr) sa dovoljno alociranog mesta. Ako se radi o umetanju u pun čvor, u starom čvoru ostavljamo pola ključeva, alociramo novi čvor u koji ubacujemo drugo pola ključeva a najveći ključ ubacujemo u roditeljski čvor i ažuriramo pokazivače i ulančanu listu.

B PLUS INSERT(root, m, key)
new_key_index = ceil(m/2) + 1
p = root
prev = nil
while p ≠ nil do
    for i = 1 to num(p) do
        if keys(p)[i] = key then
            ERROR(Key already inserted)
        else if keys(p)[i] > key then
            prev = p
            p = pointers(p)[i-1]
            parent_index = i-1
        end_if
    end_for
    if i = num(p)+1 then
        prev = p
        p = pointers(p)[i-1]
        parent_index = i-1
    end_if
end_while
if prev = nil then
    root = GETNODE
    num(root) = 1
    keys(root)[1] = key
else
    inserted = false
    for i = 1 to m do
        if ((i = m) or (keys(prev)[i] = nil) or (keys(prev)[i] > key)) and (not inserted) then
            inserted = true
            arr[i] = key
        end_if
    end_for
    if num(prev) = m-1 then
        for i = 1 to new_key_index-1 do
            keys(prev)[i] = arr[i]
        end_for
        new_node = GETNODE
        num(new_node) = m + 1 - new_key_index
        num(prev) = new_key_index-1
        for i = new_key_index to m do
            keys(new_node)[i-new_key_index+1] = arr[i]
        end_for
        for i = num(parent(prev)) downto parent_index do
            pointers(parent(prev))[i+1] = pointers(parent(prev))[i]
            keys(parent(parent))[i] = keys(parent(parent))[i-1]
        end_for
        keys(parent(prev))[parent_index+1] = keys(prev)[num(prev)]
        pointers(parent(prev))[parent_index+1] = new_node
        next(new_node) = next(prev)
        next(prev) = new_node
    else
        for i = 1 to num(prev)+1 do
            keys(prev)[i] = arr[i]
        end_for
        num(prev) = num(prev)+1
    end_if
end_if

4. zadatak

Postavka

Na primeru B* stabla reda 5 sa slike, prikazati i objasniti situaciju brisanja ključa kada dolazi do spajanja čvorova po sistemu „3-u-2“.

                      [13|54|78|  ]
                  /      /     \       \
[6 |9 |  |  ] [27|37|  |  ] [57|60|65|  ] [80|85|90|  ]

Rešenje

Iz datog primera nije moguće odmah izvršiti brisanje tako da se spoje čvorovi, tako da prvo brišemo ključ 9. Dešava se pozajmica od drugog desnog brata, tako da 13 silazi u čvor iz kojeg je izbačeno, 27 ide u koren, 54 silazi u čvor iz kojeg je izašlo 27 a 57 ide u koren.

                      [27|57|78|  ]
                  /      /     \       \
[6 |13|  |  ] [37|54|  |  ] [60|65|  |  ] [80|85|90|  ]

Zatim izbacujemo ključ 13. Dešava se spajanje tako što tretiramo 6, 27, 37, 54, 57, 60, 65 kao sortiran niz, njegov srednji ključ šaljemo u koren, njegovu levu polovinu u levo dete a desnu u desno dete tog srednjeg ključa.

                      [54|78|  |  ]
                  /     /    \
[6 |27|37|  ] [57|60|65|  ] [80|85|90|  ]

5. zadatak

Postavka

Napisati u pseudokodu funkciju koja crveno-crno stablo, dato pokazivačem na koren root, pretvara u 2-3-4 stablo i vraća pokazivač na njegov koren. Čvor crveno-crnog stabla sadrži informaciju o boji.

Rešenje

Odvajamo na slučajeve 2-čvora, 3-čvora i 4-čvora i rekurzivno transformišemo čvorove crveno-crnog stabla.

TRANSFORM(root)
if root = nil then
    return nil
end_if
new_node = GETNODE
if (left(root) ≠ nil) and (red(left(root))) and (right(root) ≠ nil) and (red(right(root))) then
    keys(new_node)[1] = key(left(root))
    keys(new_node)[2] = key(root)
    keys(new_node)[3] = key(right(root))
    pointers(new_node)[0] = TRANSFORM(left(left(root)))
    pointers(new_node)[1] = TRANSFORM(right(left(root)))
    pointers(new_node)[2] = TRANSFORM(left(right(root)))
    pointers(new_node)[3] = TRANSFORM(right(right(root)))
else if (left(root) ≠ nil) and (red(left(root))) then
    keys(new_node)[1] = key(left(root))
    keys(new_node)[2] = key(root)
    pointers(new_node)[0] = TRANSFORM(left(left(root)))
    pointers(new_node)[1] = TRANSFORM(right(left(root)))
    pointers(new_node)[2] = TRANSFORM(right(root))
else if (right(root) ≠ nil) and (red(right(root))) then
    keys(new_node)[2] = key(root)
    keys(new_node)[3] = key(right(root))
    pointers(new_node)[1] = TRANSFORM(left(root))
    pointers(new_node)[2] = TRANSFORM(left(right(root)))
    pointers(new_node)[3] = TRANSFORM(right(right(root)))
else
    keys(new_node)[2] = key(root)
    pointers(new_node)[1] = TRANSFORM(left(root))
    pointers(new_node)[2] = TRANSFORM(right(root))
end_if
return new_node

6. zadatak

Postavka

U digitalnom stablu implementiranom po principu levi sin – desni brat smeštaju se ključevi sa alfa-numeričkim vrednostima. Implemetirati funkciju za uklanjanje svih ključeva koji počinju prefiksom koji je prosleđen kao parametar funkcije. Vrednosti znakova koji predstavljaju „braću“ u stablu uređene su rastuće prema leksikografskom poretku.

Rešenje

Odvajamo rešenje na tri rekurzivne funkcije, traženu, funkciju za silazak niz stablo do čvora sa traženim prefiksom i funkciju za brisanje svih čvorova u podstablu.

DELETE KEYS(prefix)
TRAVERSE(prefix, root, nil)

Funkcija za silazak niz stablo kao treći i četvrti argument prima pokazivače na bratski i/ili roditeljski čvor u kojima je potrebno ažurirati pokazivače na čvor koji se izbacuje.

TRAVERSE(prefix, root, parent, sibling)
if root = nil then
    return
end_if
len = STRING_LENGTH(prefix)
if (len = 1) and (prefix[0] = value(root)) then
    if parent ≠ nil then
        left(parent) = right(root)
    end_if
    if sibling ≠ nil then
        right(sibling) = right(root)
    end_if
    DELETE(left(root))
    FREENODE(root)
else if (len > 1) and (prefix[0] = value(root)) then
    TRAVERSE(prefix+1, left(root), root, nil)
else
    TRAVERSE(prefix, right(root), nil, root)
end_if
DELETE(root)
if root ≠ nil then
    DELETE(left(root))
    DELETE(right(root))
    FREENODE(root)
end_if

7. zadatak

Postavka

Neka top-down stablo m-arnog pretraživanja ima n ključeva:

1. Izvesti i objasniti izraze za maksimalnu i minimalnu visinu ovog stabla.
2. Koliko najmanje i koliko najviše čvorova može imati ovo stablo. Objasniti.

Rešenje

1. Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa m-1 ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina $h = \left\lceil\frac{n}{m-1}\right\rceil$. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se $m^h$ čvorova, tako da za stablo visine $h$ imamo da je ukupan broj čvorova $m^0 + m^1 + m^2 + ... + m^h = \frac{m^{h+1} - 1}{m-1} = \left\lceil\frac{n}{m-1}\right\rceil$, iz čega dobijamo $h = \left\lceil\log_m\left(n + 1\right)\right\rceil - 1$.
2. Broj ključeva potrebnih da bi se napravilo $m$ čvorova je $2m-2$, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano $n$ jednako $m \cdot \frac{n-1}{2m-2}$. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.

8. zadatak

Postavka

1. Neka je dat neki celobrojni ključ key. Interpretirati ga kao broj u dekadnom sistemu, a zatim napisati heš funkciju H(key) koja po metodu konverzije osnove hešira ključ u tabelu T od 100 ulaza.
2. Ako n ključeva iz niza K treba da se mapira u heš tabelu gornjom funkcijom, napisati funkciju koja izračunava broj klasa ekvivalencije.

Rešenje

Za osnovu u koju konvertujemo biramo 13, jer je uzajamno prosto sa 10.

H(key)
q = 13
p = key
num = 0
exp = 1
while p > 0 do
    num = num + (p % 10) * exp
    p = p / 10
    exp = exp * 13
end_while
return num % 100
EQUIV CLASS(K, n)
for i = 0 to 99 do
    arr[i] = false
end_for
num_classes = 0
for i = 1 to n do
    k = H(K[i])
    if (not arr[k]) then
        num_classes = num_classes + 1
    end_if
    arr[k] = true
end_for
return num_classes