АСП2/К2 2017
Поставка задатака на страници предмета.
1. задатак
Поставка
У трие стабло уметнути кључеве 35, 128, 1236, 1234 и 125, а затим обрисати кључ 1234. Приказати изглед стабла након последњег уметања и након брисања. Израчунати просечан број приступа при успешној претрази.
Решење
Испод су дата трие стабла након уметања и након брисања. Број приступа при претраживању на кључ 35 је 3, при претраживању на 128 и 125 је 4 а при претраживању на 1236 је 5, тако да је просечан број приступа при успешном претраживању .
- АСП2 К2 2017 1. задатак стабло уметање.пнг
Трие стабло добијено након уметања.
- АСП2 К2 2017 1. задатак стабло брисање.пнг
Трие стабло добијено након брисања.
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 кључева (осим можда чвора на последњем нивоу) и на сваком нивоу ће бити по један чвор, чиме се добија висина . Минимална висина се добија у скоро-комплетном стаблу. На сваком нивоу таквог стабла налази се чворова, тако да за стабло висине имамо да је укупан број чворова , из чега добијамо .
- Број кључева потребних да би се направило чворова је , тако што напунимо један чвор а затим у његову децу ставимо по још један кључ (не рачунајући један кључ који искористимо да формирамо корен), тако да је највећи број чворова за фиксирано једнако . С друге стране, најмањи број чворова добијамо када попунимо сваки чвор до максимума, што је једнако максималној висини оваквог стабла.
8. задатак
Поставка
- Нека је дат неки целобројни кључ кеy. Интерпретирати га као број у декадном систему, а затим написати хеш функцију Х(кеy) која по методу конверзије основе хешира кључ у табелу Т од 100 улаза.
- Ако н кључева из низа К треба да се мапира у хеш табелу горњом функцијом, написати функцију која израчунава број класа еквиваленције.
Решење
За основу у коју конвертујемо бирамо 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