АСП2/К2 2019

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

1. задатак

Поставка

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

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

Решење

Еквивалентно изоморфно 2-3-4 стабло је:

           [57|74|  ]
          /   |      \
[21|43|  ] [60|63|  ] [88|91|94]

При избацивању кључа 63, кључ 60 долази на његово место (и постаје црн).

           [57|74|  ]
          /     |    \
[21|43|  ] [  |60|  ] [88|91|94]

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

           [43|74|  ]
          /     |    \
[  |21|  ] [  |57|  ] [88|91|94]

Еквивалентна црвено-црна стабла су дата испод.

Да је стабло било обично Б стабло реда 4, у другом кораку би се позајмљивало од десног брата уместо од левог брата, јер Б стабла немају правило да се прво позајмљује од правог брата. Такође, кључеви 21 и 57 не би стајали у средишњем пољу чвора, већ најлевљем.

• 

  Оригинално црвено-црно стабло

• 

  Црвено-црно стабло након брисања чвора 63

• 

  Црвено-црно стабло након брисања чвора 60

2. задатак

Поставка

У Б+ стабло са слике редом се умећу кључеви 6, 25, 21 и 27, након чега се уклањају кључеви 33, 27 и 6. Приказати ажурирање стабла по корацима.

            [33|64|  ]
          /     |     \
[20|22|33]->[42|64|  ]->[71|81|  ]

Решење

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

Кључ 6 се умеће лево од чвора 20. Долази до прелома и 6 и 20 остају у чвору, 20 иде у родитеља, а 22 и 33 се одвајају у нови чвор.

                  (20|33|64)
            /        |  |     \
[ 6|20|  ]->[22|33|  ]->[42|64|  ]->[71|81|  ]

Кључ 25 се умеће између кључева 22 и 33.

                  (20|33|64)
            /        |  |     \
[ 6|20|  ]->[22|25|33]->[42|64|  ]->[71|81|  ]

Кључ 21 се умеће лево од кључа 22. Долази до прелома, 21 и 22 остају у чвору, 22 иде у родитељски чвор, а 25 и 33 се одвајају у нови чвор. Пошто у родитељу нема места, и он се прелама тако да корен постаје чвор са 22, леви чвор са 20 и десни са 33 и 64.

                         (22|  |  )
                      /              \
          (20|  |  )                   (33|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|33|  ]->[42|64|  ]->[71|81|  ]

Кључ 27 се умеће између кључева 25 и 33.

                         (22|  |  )
                      /              \
          (20|  |  )                   (33|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|27|33]->[42|64|  ]->[71|81|  ]

При уклањању кључа 33, пошто је највећи кључ у чвору, мора се ажурирати родитељски чвор тако да 33 у родитељском чвору постаје 27.

                         (22|  |  )
                      /              \
          (20|  |  )                   (27|64|  )
         /   |                    /       |   \
[ 6|20|  ]->[21|22|  ]->[25|27|  ]->[42|64|  ]->[71|81|  ]

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

                         (22|  |  )
                      /              \
          (20|  |  )                   (64|  |  )
         /   |                    /       |
[ 6|20|  ]->[21|22|  ]->[25|42|64]->[71|81|  ]

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

            (22|64|  )
          /    |       \
[20|21|22]->[25|42|64]->[71|81|  ]

3. задатак

Поставка

Дато дигитално стабло је потребно трансформисати у компактнију форму како би се смањила величина стабла.

1. Предложити и објаснити начин на који се може остварити трансформација дигиталног стабла у компактнију форму и приказати изглед дигиталног стабла након описане трансформације.
2. Имплементирати функцију ТРИЕ ЦОМПАЦТИОН која трансформише стабло на претходно описани начин. Показивач на корен стабла роот је прослеђен функцији. Сматрати да је дигитално стабло представљено по принципу леви син - десни брат.

      A
   /  |  \
  B   C   S
  |   |   |
  K   J   4
 / \  |   |
D   T M   6
|   | |   |
9   * *   A
|         |
3         *
|
*

Решење

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

TRIE COMPACTION(root)
if root ≠ nil then
    compacted_root = COMPACT(root, "")
    if compacted_root ≠ nil then
        root = compacted_root
    end_if
end_if
COMPACT(node, str)
if key(node) = '*' then
    FREENODE(node)
    return str
end_if
compacted_child = COMPACT(left(node), str + key(node))
if right(node) = nil then
    FREENODE(node)
    return compacted_child
else
    COMPACT(right(node), str)
    if compacted_child ≠ nil then
        left(node) = compacted_child
    end_if
    return nil
end_if

4. задатак

Поставка

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

Решење

DELETE(root, m, key)
parent = nil
parent_index = 0
p = root
i = 0
found = false
while (p ≠ nil) and (not found) do
    for i = 1 to num(p) do
        if keys(p)[i] = key then
            found = true
            break
        else if keys(p)[i] > key then
            parent = p
            parent_index = i
            p = pointers(p)[i-1]
            break
        end_if
    end_for
    if i = num(p) + 1 then
        p = pointers(p)[i-1]
    end_if
end_while
if p = nil then
    ERROR(Ključ nije pronađen)
end_if
q = pointers(p)[i]
if q ≠ nil then
    prev = p
    while q ≠ nil do
        parent = prev
        parent_index = 1
        prev = q
        q = pointers(q)[0]
    end_while
    keys(p)[i] = key(prev)
    p = prev
    i = 1
end_if
for j = i to num(p) do
    keys(node)[i-1] = keys(node)[i]
end_for
num(p) = num(p) - 1
if num(p) = 0 then
    FREENODE(p)
    pointers(parent)[parent_index-1] = nil
end_if

5. задатак

Поставка

У Б* стабло реда 5 са слике се умећу кључеви 18, 23, 7, 37, 19. Након тога се редом бришу кључеви 80, 55, 18, 9 и 15. Нацртати изглед стабла након сваке измене.

                            [15|24|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|20|21|  ] [27|33|40|  ] [55|75|  |  ] [93|96|  |  ]

Решење

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

Кључ 18 умећемо између кључева 16 и 20.

                            [15|24|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|18|20|21] [27|33|40|  ] [55|75|  |  ] [93|96|  |  ]

Кључ 23 умећемо десно од кључа 21. Дешава се преливање у десни чвор, 23 завршава у родитељу а 24 у десном чвору.

                            [15|23|41|80]
             /             /      |      \             \
[ 2| 9|10|  ] [16|18|20|21] [24|27|33|40] [55|75|  |  ] [93|96|  |  ]

Кључ 7 умећемо између кључева 2 и 9.

                            [15|23|41|80]
             /             /      |      \             \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|40] [55|75|  |  ] [93|96|  |  ]

Кључ 37 умећемо између кључева 33 и 40. Дешава се преливање у десни чвор, 40 завршава у родитељу а 41 у десном чвору.

                            [15|23|40|80]
             /             /      |      \             \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|37] [41|55|75|  ] [93|96|  |  ]

Кључ 19 умећемо између кључева 18 и 20. Преливање у левог и десног брата је немогуће, па се дешава прелом. Кључеви 16 и 18 остају у чвору, 19 иде у родитељски чвор, 20, 21 и 23 иду у нови чвор, 24 иде у родитељски чвор и 27, 33 и 37 остају у десном брату. Прелом се дешава и у родитељском чвору, тако да 15 и 19 иду у лево дете новог корена, 24 иде у нови корен а 40 и 80 иду у десно дете новог корена.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [40|80|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|37|  ] [41|55|75|  ] [93|96|  |  ]

Кључ 80 мењамо својим следбеником, 93, па га бришемо из листа. У листу остаје недовољно много кључева, па вршимо позајмицу од левог брата. Том приликом се кључ 93 враћа назад у лист у којем је био а 75 долази на место где је раније био кључ 80.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [40|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|37|  ] [41|55|  |  ] [93|96|  |  ]

При брисању кључа 55 из листа остаје недовољно кључева, па позајмљујемо од левог брата. Том приликом кључ 37 долази на место 40 у родитељском чвору а 40 се спушта у лист.

                                                [24|  |  |  ]
                                       /                      \
              [15|19|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|18|  |  ] [20|21|23|  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

При брисању кључа 18 из листа остаје недовољно кључева, па позајмљујемо од десног брата. Том приликом кључ 20 иде у родитељски чвор а кључ 19 се спушта у лист.

                                                [24|  |  |  ]
                                       /                      \
              [15|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7| 9|10] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

Бришемо кључ 9 из листа.

                                                [24|  |  |  ]
                                       /                      \
              [15|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7|10|  ] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

Кључ 15 мењамо својим следбеником, 16, па бришемо кључ из листа. У том листу остаје недовољно много кључева, па се позајмљује од левог брата тако што се кључ 16 врати на своје претходно место а кључ 10 оде у родитељски чвор.

                                                [24|  |  |  ]
                                       /                      \
              [10|20|  |  ]                                           [37|75|  |  ]
             /   |      \                                            /   |      \
[ 2| 7|  |  ] [16|19|  |  ] [21|23|  |  ]               [27|33|  |  ] [40|41|  |  ] [93|96|  |  ]

6. задатак

Поставка

Посматра се база података студената.

1. Уколико се зна да је најчешћи упит над задатом базом дохватање свих студената који су факултет уписали у задатом периоду (између две године), предложити структуру података која би подржала ефикасно извршавање оваквог упита и детаљно описати разлоге.
2. Имплементирати функцију ФИНД_СТУДЕНТС_ИН_РАНГЕ која над одабраном структуром врши претрагу и враћа резултат упита наведеног под тачком а). Параметри функције су показивач на одабрану структуру, почетна година и крајња година траженог периода, респективно. Резултат вратити у форми низа.

Решење

Структура која се овде може употребити је Б+ стабло, јер нам дозвољава лак секвенцијални приступ (за излиставање свих студената у распону од две године) као и брзо проналажење првог кључа (за првог студента из распона). Кључеви оваквог стабла могу бити комбинација године и броја индекса студента, тако да је година примарни а број индекса секундарни кључ.

FIND STUDENTS IN RANGE(structure, year1, year2)
p = structure
while (not IS_LEAF(p)) do
    for i = 1 to num(p) do
        if keys(p)[i] > year1 then
            p = pointers(p)[i-1]
            break
        end_if
    end_for
    if i = num(p)+1 then
        p = pointers(p)[num(p)]
    end_if
end_while
length = 0
q = p
key_index = 1
while (q ≠ nil) and (years(q)[key_index] ≤ year2) do
    length = length + 1
    if node_index = num(q) then
        key_index = 1
        q = next(q)
    else
        key_index = key_index + 1
    end_if
end_while
arr = ALLOCATE(length)
for i = 1 to length do
    j = 1
    while j < num(p) and i < length do
        arr[i] = students(p)[j]
        i = i + 1
        j = j + 1
    end_while
    p = next(p)
end_for
return arr

7. задатак

Поставка

Нека се за индексну структуру датотеке користи Б стабло реда м. У оквиру датотеке се смештају записи величине 256 битова заједно са 32-битним пољем кључа. Нека се на датом систему адресе представљају на 64 бита. Одредити вредности м у зависности од тога да ли се у чвору Б стабла смешта само кључ или читав података, под претпоставком да је величина блока на диску 2КБ. Дискутовати решење.

Решење

Један чвор Б стабла мора стати у један блок на диску, што је 2КиБ, односно 2048Б, односно 16384б. Запис чвора обухвата:

• $m-1$ кључева (32б) заједно са адресама њихових записа (64б), односно у другој варијанти цео запис (256б)
• $m$ адреса (64б) подстабала

Тако је величина једног чвора стабла у првој варијанти једнака $(m-1) \cdot (32 + 64) + m \cdot 64 = m \cdot 96 + m \cdot 64 - 96 = m \cdot 160 - 96$. Ако претпоставимо да је ово једнако величини блока, добијамо $m \cdot 160 = 16480 \implies m = \frac{16480}{160} = 103$.

У другој варијанти, ако претпоставимо да се кључ може закључити из структуре па се не чува одвојено, величина чвора је једнака $(m-1) \cdot 256 + m \cdot 64 = m \cdot 256 - 256 + m \cdot 64 = m \cdot 320 - 256$. Са истом претпоставком добијамо $m \cdot 320 = 16640 \implies m = \frac{16640}{320} = 52$.

8. задатак

Поставка

Хеширање.

1. Како функционише метод дељења и које су његове основне особине? Које вредности делиоца треба избегавати?
2. Нека је дат скуп кључева 19, 10, 4, 37, 49, 52. Уколико је познатао да се приликом хеширања користи метод дељења и величина табеле н = 9, коментарисати избор величине табеле у односу на вероватноћу могућих колизија задатог скупа кључева. Предложити алтернативну, блиску величину табеле како би се вероватноћа колизија смањила.

Решење

Метод дељења функционише тако што хеш функција има облик $h(K) = K mod n$, где је $n$ број улаза табеле. Лоши бројеви $n$ су парни бројеви, бројеви дељиви с 10 и, ако су сви кључеви конгурентни по модулу $d$, бројеви који нису узајамно прости са $d$.

За дати скуп кључева добијамо следећу табелу:

Хеш табела након уметања датог скупа кључева

0	1	2	3	4	5	6	7	8
	19 10 37			4 49			52

Овде се колизија десила у 50% случајева. Предлажемо мало измењен број улаза $n = 8$:

Хеш табела након уметања датог скупа кључева с предложеном хеш функцијом

0	1	2	3	4	5	6	7
	49	10	19	4 52	37

Овде се колизија дешава у 16.66% случајева.