АСП2/К2 2017

Поставка задатака на страници предмета.

1. задатак

Поставка

У трие стабло уметнути кључеве 35, 128, 1236, 1234 и 125, а затим обрисати кључ 1234. Приказати изглед стабла након последњег уметања и након брисања. Израчунати просечан број приступа при успешној претрази.

Решење

Испод су дата трие стабла након уметања и након брисања. Број приступа при претраживању на кључ 35 је 3, при претраживању на 128 и 125 је 4 а при претраживању на 1236 је 5, тако да је просечан број приступа при успешном претраживању $\frac{3 + 4 + 4 + 5}{4} = 4$.

• 

  Трие стабло добијено након уметања.

• 

  Трие стабло добијено након брисања.

2. задатак

Поставка

Нека се уз кључеве Б стабла реда м чува и број приступа податку придруженом том чвору. Кључеви чијим подацима се чешће приступа треба да се нађу што ближе корену стабла. Објаснити како би требало модификовати структуру и операције претраживања и брисања да би се то реализовало.

3. задатак

Поставка

Написати у псеудокоду функцију за уметање кључа у Б+ стабло реда м на чији корен указује показивач роот. Претпоставити да отац листа у који се врши уметање није максимално попуњен. Сматрати да је структура чвора фиксна и да чвор садржи алоциран простор за максималан број кључева и показивача. Додатно, сваки чвор садржи показивач на оца и податак о броју кључева смештених у њему.

Решење

Прво проналазимо лист у који умећемо, чувајући индекс нашег подстабла у родитељском чвору (parent_index) и бацајући грешку уколико наиђемо на постојећи кључ с истом вредношћу. Затим формирамо стабло уколико родитељски чвор не постоји или формирамо нови поредак кључева у чвору у помоћном низу (arr) са довољно алоцираног места. Ако се ради о уметању у пун чвор, у старом чвору остављамо пола кључева, алоцирамо нови чвор у који убацујемо друго пола кључева а највећи кључ убацујемо у родитељски чвор и ажурирамо показиваче и уланчану листу.

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. задатак

Поставка

На примеру Б* стабла реда 5 са слике, приказати и објаснити ситуацију брисања кључа када долази до спајања чворова по систему „3-у-2“.

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

Решење

Из датог примера није могуће одмах извршити брисање тако да се споје чворови, тако да прво бришемо кључ 9. Дешава се позајмица од другог десног брата, тако да 13 силази у чвор из којег је избачено, 27 иде у корен, 54 силази у чвор из којег је изашло 27 а 57 иде у корен.

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

Затим избацујемо кључ 13. Дешава се спајање тако што третирамо 6, 27, 37, 54, 57, 60, 65 као сортиран низ, његов средњи кључ шаљемо у корен, његову леву половину у лево дете а десну у десно дете тог средњег кључа.

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

5. задатак

Поставка

Написати у псеудокоду функцију која црвено-црно стабло, дато показивачем на корен роот, претвара у 2-3-4 стабло и враћа показивач на његов корен. Чвор црвено-црног стабла садржи информацију о боји.

Решење

Одвајамо на случајеве 2-чвора, 3-чвора и 4-чвора и рекурзивно трансформишемо чворове црвено-црног стабла.

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. задатак

Поставка

У дигиталном стаблу имплементираном по принципу леви син – десни брат смештају се кључеви са алфа-нумеричким вредностима. Имплеметирати функцију за уклањање свих кључева који почињу префиксом који је прослеђен као параметар функције. Вредности знакова који представљају „браћу“ у стаблу уређене су растуће према лексикографском поретку.

Решење

Одвајамо решење на три рекурзивне функције, тражену, функцију за силазак низ стабло до чвора са траженим префиксом и функцију за брисање свих чворова у подстаблу.

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

Функција за силазак низ стабло као трећи и четврти аргумент прима показиваче на братски и/или родитељски чвор у којима је потребно ажурирати показиваче на чвор који се избацује.

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. задатак

Поставка

Нека топ-доwн стабло м-арног претраживања има н кључева:

1. Извести и објаснити изразе за максималну и минималну висину овог стабла.
2. Колико најмање и колико највише чворова може имати ово стабло. Објаснити.

Решење

1. Максимална висина оваквог стабла се добија када направимо дегенерисано стабло уметањем сортираног низа кључева у њега. Том приликом ће сваки чвор бити попуњен са м-1 кључева (осим можда чвора на последњем нивоу) и на сваком нивоу ће бити по један чвор, чиме се добија висина $h = \left\lceil\frac{n}{m-1}\right\rceil$. Минимална висина се добија у скоро-комплетном стаблу. На сваком нивоу таквог стабла налази се $m^h$ чворова, тако да за стабло висине $h$ имамо да је укупан број чворова $m^0 + m^1 + m^2 + ... + m^h = \frac{m^{h+1} - 1}{m-1} = \left\lceil\frac{n}{m-1}\right\rceil$, из чега добијамо $h = \left\lceil\log_m\left(n + 1\right)\right\rceil - 1$.
2. Број кључева потребних да би се направило $m$ чворова је $2m-2$, тако што напунимо један чвор а затим у његову децу ставимо по још један кључ (не рачунајући један кључ који искористимо да формирамо корен), тако да је највећи број чворова за фиксирано $n$ једнако $m \cdot \frac{n-1}{2m-2}$. С друге стране, најмањи број чворова добијамо када попунимо сваки чвор до максимума, што је једнако максималној висини оваквог стабла.

8. задатак

Поставка

1. Нека је дат неки целобројни кључ кеy. Интерпретирати га као број у декадном систему, а затим написати хеш функцију Х(кеy) која по методу конверзије основе хешира кључ у табелу Т од 100 улаза.
2. Ако н кључева из низа К треба да се мапира у хеш табелу горњом функцијом, написати функцију која израчунава број класа еквиваленције.

Решење

За основу у коју конвертујемо бирамо 13, јер је узајамно просто са 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