АСП2/К2 2016

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

1. задатак

Поставка

У дигитално стабло уметнути кључеве 25, 23, 367, 3698, 3692, 4, а затим обрисати кључеве 367 и 23. Користити репрезентацију „најлевљи син – десни брат“. Приказати стабло након последњег уметања и брисања.

Решење

Испод су дата стабла након последњег уметања и брисања.

• АСП2 К2 2016 1. задатак стабло уметање.пнг

  Стабло након последњег уметања.

• АСП2 К2 2016 1. задатак стабло брисање.пнг

  Стабло након последњег брисања.

2. задатак

Поставка

Изоморфизам црвено-црних стабала и 2-3-4 стабала.

1. На који начин се врши уметање у пун чвор 2-3-4 стабла да би се очувао изоморфизам са црвено црним стаблима? Да ли постоје разлике у односу на класично Б стабло?
2. У 2-3-4 стабло са слике уметнути кључеве 30 и 35. Нацртати изглед стабла после сваке од измена и означити црвене и црне чворове.

                 [25|44|58]
             /      |  |        \
[  |15|  ] [27|37|  ] [  |47|50] [  |60|  ]

Решење

При уметању у пун чвор 2-3-4 стабла дешава се прелом. Разлика је у томе да црни кључ увек иде у корен а тренутни чвор се раздваја на два чвора, у левом чвору као црни кључ долази леви црвени кључ претходног чвора, у десном као црни кључ долази десни црвени кључ претходног чвора а новоуметнути кључ постаје црвен у левом или десном чвору у зависности од тога да ли је мањи или већ од црног кључа из претходног чвора.

Кључ 30 умећемо у лист и том приликом се кључ 37 помера као црвени.

                 [25|44|58]
             /      |  |        \
[  |15|  ] [27|30|37] [  |47|50] [  |60|  ]

Кључ 35 умећемо у тај исти лист и том приликом се дешава прелом, 27 постаје црни кључ левог чвора, 37 постаје црни кључ десног чвора, кључ 30 иде у корен а кључ 35 постаје леви црвени кључ десног чвора. Прелом се дешава и у корену, тако да 25 постаје црни кључ левог чвора, 58 постаје црни кључ десног чвора, 44 иде у нови корен а 30 постаје десни црвени кључ левог чвора.

                        [  |44|  ]
                       /          \
           [  |25|30]                 [  |58|  ]
          /    |     \                   |  |
[  |15|  ] [  |27|  ] [35|37|  ] [  |47|50] [  |60|  ]

Бојење овде неће бити одрађено, али црни кључеви су 15, 27, 25, 44, 58, 47 и 60, а сви остали су црвени.

3. задатак

Поставка

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

Решење

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

B-DEL-BORROW(node)
min_nodes = ceil(m/2)+1
if (node = nil) or (parent(node) = nil) then
    ERROR(Borrow impossible)
end_if
if (num(node) ≥ min_nodes) then
    return
end_if
parent = parent(node)
for i to 0 to num(parent) do
    if pointers(parent)[i] = node then
        parent_index = i
        break
    end_if
end_for
if (parent_index < num(parent)) and (num(pointers(parent)[parent_index+1]) > min_nodes) then
    sibling = pointers(parent)[parent_index+1]
    keys(node)[num(node)+1] = keys(parent)[parent_index+1]
    keys(parent)[parent_index+1] = keys(sibling)[1]
    num(node) = num(node)+1
    num(sibling) = num(sibling)-1
    pointers(node)[num(node)] = pointers(sibling)[0]
    for i = 0 to num(sibling) do
        pointers(sibling)[i] = pointers(sibling)[i+1]
        if i < num(sibling) then
            keys(sibling)[i+1] = keys(sibling)[i+2]
        end_if
    end_for
else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then
    sibling = pointers(parent)[parent_index-1]
    for i = 0 to num(node) do
        pointers(node)[i+1] = pointers(node)[i]
        if i < num(node) then
            keys(sibling)[i+2] = keys(sibling)[i+1]
        end_if
    end_for
    keys(node)[1] = keys(parent)[parent_index]
    keys(parent)[parent_index] = keys(sibling)[num(sibling)]
    pointers(node)[0] = pointers(sibling)[num(sibling)]
    num(node) = num(node)+1
    num(sibling) = num(sibling)-1
else
    ERROR(Borrow impossible)
end_if

4. задатак

Поставка

Датотека:АСП2 К2 2016 4. задатак граф.пнг

Граф из поставке 4. задатка.

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

Решење

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

5. задатак

Поставка

Неки систем датотека користи Б+ стабла за индексирање датотека унутар каталога. Величина чвора Б+ стабла је 256б, а показивачи заузимају 16б. За смештање кључа Б+ стабла користи се 64б.

1. За дате параметре, одредити максимални ред стабла.
2. Нека се посматра каталог у којем већ постоје датотеке, са кључевима 6, 12, 18, 45, 58, 66, 73, 81. Под претпоставком да су сви листови попуњени минималним бројем кључева, нацртати иницијални изглед Б+ стабла за индексирање таквог каталога. Након тога, у каталог се додају датотеке са кључевима 41, 53, 32, а потом се бришу датотеке са кључевима 12 и 66. Нацртати изглед стабла после сваког уметања и брисања. Ред стабла је одређен вредношћу која је израчуната у тачки а).

Решење

Максимални ред стабла је $m = 4$. Распоред меморије у чвору дат је испод.

Распоред меморије у чвору Б+ стабла.

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

16б

$p_0$

$k_1$

$p_1$

$k_2$

$p_2$

$k_3$

$p_3$

Пошто је минималан број кључева у листу Б+ стабла једнак $\left\lfloor\frac{m}{2}\right\rfloor = \left\lfloor\frac{4}{2}\right\rfloor = 2$, иницијални изглед задатог Б+ стабла је:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|45|  ]->[58|66|  ]->[73|81|  ]

Кључ 41 се додаје у лист:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|41|45]->[58|66|  ]->[73|81|  ]

Кључ 53 се исто додаје у лист:

                  (12|45|66)
              /      |  |       \
[6 |12|  ]->[18|41|45]->[53|58|66]->[73|81|  ]

При додавању кључа 32 дешава се прелом у листу, који се раздваја на листове са 18 и 32 и са 41 и 45, а кључ 32 одлази у корен. Пошто је и корен пун, дешава се прелом и 12 остаје у левом чвору, 32 одлази у нови корен а 45 и 66 иду у десни чвор.

                      (32|  |  )
                  /               \
      (12|  |  )                    (45|66|  )
      |   \                       /    |     \
[6 |12|  ]->[18|32|  ]->[41|45|  ]->[53|58|66]->[73|81|  ]

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

                  (45|  |  )
            /            \
      (32|  |  )              (66|  |  )
      |   \                   |   \
[6 |18|32]->[41|45|  ]->[53|58|66]->[73|81|  ]

Кључ 66 се брише из листа и том приликом се ажурира родитељски чвор.

                  (45|  |  )
            /            \
      (32|  |  )              (58|  |  )
      |   \                   |   \
[6 |18|32]->[41|45|  ]->[53|58|  ]->[73|81|  ]

6. задатак

Поставка

Написати у псеудокоду итеративну имплементацију функције која формира трие стабло свих подстрингова стринга који је проследјен^[сиц] као аргумент тој функцији. Дата је помоћна функција гетПоситион(цхр), која за проследјени^[сиц] карактер цхр враћа индекс одговарајућег показивача у чвору трие стабла.

Решење

TRIE SUBSTRINGS(str)
root = GETNODE
for i = 1 to length(str) do
    node = root
    substr = ""
    for j = i to length(str) do
        substr = substr + str[j]
        pos = getPosition(str[j])
        if nodes(node)[pos] = nil then
            node(node)[pos] = GETNODE
        end_if
        node = node(node)[pos]
        value(node) = substr
    end_for
end_for
return root

7. задатак

Поставка

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

1. Предложити ефикасну организацију чвора која дозвољава најбрже претраживање оваквог чвора.
2. Прецизно нацртати организацију чвора за стабло реда 6 који тренутно садржи кључеве ИПСИЛОН, ДЕЛТА, ИКС, АЛФА.

Решење

У чвор можемо додати поље од м-2 целобројних вредности које нам говоре од које меморијске локације почиње који кључ. На тај начин, кад видимо да се неки претраживани кључ не поклапа са вредношћу у тренутном пољу, уместо да наставимо да читамо вредност до следећег кључа можемо одмах да нађемо почетак следећег кључа.

Организација чвора

4

9

12

12

12

А

L

Ф

А

D

Е

L

Т

А

I

К

С

I

П

С

I

L

О

Н

8. задатак

Поставка

Хеширање:

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

Решење

1. Униформност хеш функције је особина која значи да је сваки од $n$ излаза подједнако вероватан: $P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n$
2. На сваких $n$ унетих кључева за сваки кључ можемо да очекујемо по једну колизију више на сваком унетом кључу. Уметање затим можемо поделити у више фаза, тако да је у свакој фази за по једна колизија више по кључу од прошле, и број тих (потпуних) фаза ће бити $m = \left\lfloor\frac{k}{n}\right\rfloor$. То значи да ће укупан очекивани број колизија бити $n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)$.