АСП2/К2 2018

Задаци на страници предмета.

1. задатак

Поставка

У 2-3-4 стабло са слике убацити кључеве 17 и 25 и приказати еквивалентно црвено-црно стабло.

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

Решење

Датотека:АСП2 К2 2018 задатак 1 стабло.пнг

Еквивалентно црвено-црно стабло у решењу 1. задатка.

Кључ 17 долази између кључева 15 и 20. Пошто је тај чвор пун, црни кључ 15 иде у родитељски чвор, кључ 1 долази у средину и постаје црн, кључ 20 се одваја у десни чвор и постаје црн а кључ 17 завршава као црвени кључ лево од кључа 20.

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

Кључ 25 долази лево од кључа 28.

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

2. задатак

Поставка

Б+-стабла

1. Приказати максимално попуњено Б+-стабло реда м = 3 и висине х = 1. Одредити за ово стабло просечан број приступа приликом успешне и неуспешне претраге.
2. Посматра се Б+-стабло реда 4 које садржи 7 кључева. Одредити за ово стабло средњи број приступа приликом успешне и неуспешне претраге и образложити одговор.

Решење

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

2 је просечан број приступа и при успешној и при неуспешној претрази.

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

Претпостављајући да се овде ради о броју кључева у листовима (пошто се кључеви из унутрашњих чворова дуплицирају у листовима), просечан број приступа је поново 2. Све успешне претраге, као и неуспешне, морају завршити у листовима јер се само у листовима налазе показивачи ка траженим структурама, а висина овако направљеног стабла је 1.

3. задатак

Поставка

Посматра се трие стабло чији су кључеви знаковни низови који садрже цифре у бројном систему са основом 10. Написати у псеудокоду функцију која за дато стабло на чији корен показује показивач роот рачуна разлику највећег и најмањег тако представљеног броја.

Решење

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

Поставка

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

Решење

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

Поставка

У Б* стабло реда 4 се умећу кључеви од 1 до 14. Након тога се редом бришу кључеви 4, 11 и 9. Нацртати изглед стабла након сваке измене.

Решење

• Ред стабла: $m = 4$
• Минимални број кључева у не-коренском чвору: $\left\lceil\frac{2m - 1}{3}\right\rceil - 1 = 2$
• Максимални број кључева у корену: $2 \left\lfloor\frac{2m - 2}{3}\right\rfloor = 4$
• Расподела кључева при прелому: 2-2-2

Умећемо кључ 1 у празно стабло.

[ 1|  |  |  ]

Умећемо кључ 2.

[ 1| 2|  |  ]

Умећемо кључ 3.

[ 1| 2| 3|  ]

Умећемо кључ 4.

[ 1| 2| 3| 4]

При уметању кључа 5 долази до преламања чвора, тако да кључеви 1 и 2 иду у леви а 4 и 5 у десни чвор.

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

Умећемо кључ 6.

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

При уметању кључа 7 десни чвор се препуњује, па се дешава преливање у леви чвор. Кључ 3 из родитељског чвора силази у леви а кључ 4 из десног иде у родитељски.

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

При уметању кључа 8 десни чвор се поново препуњује, па се дешава преламање. Кључеви 1 и 2 остају у левом чвору, кључ 3 иде у родитељски чвор, 4 и 5 долазе у нови, средњи чвор, 6 иде у родитељски чвор а 7 и 8 остају у десном чвору.

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

Умећемо кључ 9.

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

При уметању кључа 10 дешава се преливање из десног у средњи чвор.

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

При уметању кључа 11 дешава се преламање.

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

Умећемо кључ 12.

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

При уметању кључа 13 дешава се преливање.

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

При уметању кључа 14 дешава се преламање.

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

При брисању кључа 4, због немогућности позајмице, спајање три чвора у два.

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

При брисању кључа 11 могућа је позајмица, али од левог брата.

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

При брисању кључа 9 могућа је позајмица али од брата са удаљеношћу два.

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

6. задатак

Поставка

Дато је дигитално стабло формирано од неког скупа кључева типа знаковних низова. Имплементирати функцију ЦОУНТ_КЕYС која проналази број кључева у стаблу који одговарају задатом формату знаковног низа. Показивач на корен стабла и задати формат су прослеђени као параметри функције. Формат знаковног низа поред цифара и слова може садржати и симболе који имају специјано значење. Специјални симболи су тачка (.) која мења било који знак низа и звезда (*) која представља понављање неког знака низа 0 или више пута. Сматрати да се звезда односи на први знак који јој претходи.

Пример:

скуп кључева у стаблу: абццц4а, аб3а, аацда

формат: абц*.а

резултат: 2

Решење

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

Поставка

Нека се у топ-доwн стабло м-арног претраживања редом убацују кључеви к, 2к, 3к, …, нк, нк – 1, нк – 2, нк – 3, …, н(к – 1) +1. Нацртати изглед стабла и одредити висину. Претпоставити да су н и к много већи од м.

Решење

Након убацивања кључа нк добиће се дегенерисано стабло удесно, тј. једино најдеснији показивачи у сваком унутрашњем чвору ће показивати на следећи лист, и већина кључева ће бити попуњена, тако да ће висина стабла бити $\left\lceil\frac{n}{m - 1}\right\rceil$ а у листу ће остати $(m - 1) - (n \bmod (m - 1))$ слободних места. Након убацивања свих кључева стабло ће у листовима кренути да расте улево из листова, тако да ће висина порасти на укупно: $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. задатак

Поставка

Хеширање.

1. Шта је минимална савршена хеш функција?
2. За кључеве 54, 91, 57, 23 и 28 наћи што једноставнију минималну савршену хеш функцију и исписати је. Образложити одговор и нацртати хеш табелу са уметнутим кључевима.

Решење

1. Минимална савршена хеш функција је хеш функција која пресликава н кључева у н улаза табеле без колизије.
2. Једна могућа савршена хеш функција је $h(K) = \left\lfloor\frac{K}{2}\right\rfloor \mod 5$. Кад сортирамо кључеве, добијамо редослед 23, 28, 54, 57. Можемо приметити да су они сви различити по модулу 10, али пошто табела има 5 улаза можемо прво поделити кључеве са два па узети вредност по модулу 5. Табела након примене ове хеш функције је дата испод.

Табела након примене хеш функције

0	1	2	3	4
91	23	54	57	28