АСП2/К1 2019
1. задатак
Поставка
Дата је неопадајуће уређена проширена табела и одговарајући вектор битова валидности. Приказати изглед повећане табеле и вектора валидности након уметања сваког од кључева: 5, 28 и 29, а затим уклонити кључеве: 14 и 15 и приказати финално стање.
4 | 7 | 10 | 14 | 15 | 15 | 21 | 24 | 25 | 40 | 45 |
1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
Решење
4 | 5 | 5 | 14 | 15 | 15 | 21 | 24 | 25 | 40 | 45 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
4 | 5 | 5 | 14 | 15 | 15 | 21 | 24 | 25 | 28 | 40 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Такође је могуће да се, уз напомену, при наиласку на кључ већи од траженог гледа лево уместо десно. |
4 | 5 | 5 | 14 | 15 | 15 | 21 | 24 | 28 | 29 | 40 |
1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Постоје два начина на који можемо да решимо ситуацију кад наиђемо на 40 и не можемо да га померимо удесно:
|
4 | 5 | 5 | 14 | 15 | 15 | 21 | 24 | 28 | 29 | 40 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
При брисању кључа 15 дешава се грешка јер тај кључ не постоји.
2. задатак
Поставка
Нека је дат веома велики уређени низ арр дужине н. Познато је да вероватноћа претраживања кључева монотоно опада од почетка ка крају низа.
- Предложити и кратко објаснити технику бинарног претраживања која обећава навећу[сиц] ефикасност под задатим условима.
- Написати у псеудокоду итеративну имплементацију функције која имплементира бинарно претраживање низа арр дужине н у складу са техником предложеном под а).
Решење
Начин за ефикасно бинарно претраживање овог низа јесте тако што се прво испитују кључеви на позицијама и затим када се одреде тако да на интервалу од до се спроводи бинарна претрага.
У поставци функције у задатку није био дат параметар к, односно кључ који се претражује, али је овде додат.
BINARY SEARCH PROB(arr, n, k) low = 1 high = 2 while (high ≤ n) and (arr[high] < k) do low = high high = 2 * high end_while if (high > n) then high = n end_if while (low ≤ high) do mid = (low + high) / 2 if (arr[mid] = k) then return mid else if (arr[mid] < k) then low = mid + 1 else high = mid - 1 end_if end_while return nil
3. задатак
Поставка
На слици је дато стабло бинарног претраживања. Потребно је трансформисати ово стабло у АВЛ стабло. Приказати трансформацију стабла по корацима.
25 / \ 9 38 / \ 36 49 / / 31 42 / / \ 27 40 45 \ 47
Решење
Прво пронађемо критичне чворове у стаблу:
25 / \ 9 38 / \ 36 49 / / 31 42 / / \ 27 40 45 \ 47
Затим радимо ротацију удесно око чвора 36 (његово лево дете нагиње на леву страну):
25 / \ 9 38 / \ 31 49 / \ / 27 36 42 / \ 40 45 \ 47
чиме постижемо да чвор 36 више није критичан. Затим радимо ротацију улево око чвора 42 (лево дете чвора 49 нагиње на десну страну):
25 / \ 9 38 / \ 31 49 / \ / 27 36 45 / \ 42 47 / 40
па ротацију удесно око чвора 49:
25 / \ 9 38 / \ 31 45 / \ / \ 27 36 42 49 / / 40 47
чиме постижемо да чвор 49 више није критичан. На крају радимо ротацију улево око чвора 25 (његово десно дете нагиње на десну страну) и добијамо...
Коначно стабло:
38 / \ 25 45 / \ / \ 9 31 42 49 / \ / / 27 36 40 47
4. задатак
Поставка
На слици је приказано стабло бинарног претраживања након брисања кључа 19. Ако је познато да се приликом брисања користи претходник, приказати све могуће изгледе стабла непосредно пре брисања наведеног кључа.
10 / \ 5 18 / / \ 3 14 20 \ 15 \ 17
Решење
10 / \ 5 18 / / \ 3 14 19 \ \ 15 20 \ 17
10 / \ 5 18 / / \ 3 14 20 \ / 15 19 \ 17
10 / \ 5 19 / / \ 3 18 20 / 14 \ 15 \ 17
10 / \ 5 19 / / \ 3 14 20 \ 15 \ 17 \ 18
10 / \ 5 19 / / \ 3 14 20 \ 18 / 15 \ 17
10 / \ 5 19 / / \ 3 14 20 \ 15 \ 18 / 17
5. задатак
Поставка
Нека се у дато самоподешавајуће стабло редом убацују кључеви 37, 32, 34, након чега се претражује на кључеве 33 и 20, а затим се бришу кључеви 60 и 31. Приказати изглед стабла након сваког извршеног корака при уметању и брисању.
50 / \ 30 60 / \ 20 40
Решење
Прво додајемо чвор 37 у стабло:
50 / \ 30 60 / \ 20 40 / 37
Пошто од деде до оца и од оца до сине воде гране у супротним смеровима, прво ротирамо удесно око чвора 40:
50 / \ 30 60 / \ 20 40 \ 37
а затим улево око чвора 30:
50 / \ 37 60 / \ 30 40 / 20
Пошто још увек нисмо у корену, ротирамо улево око чвора 50:
37 / \ 30 50 / / \ 20 40 60
Затим додајемо чвор 32:
37 / \ 30 50 / \ / \ 20 32 40 60
Пошто од деде до оца и од оца до сине воде гране у супротним смеровима, прво ротирамо улево око чвора 30:
37 / \ 32 50 / / \ 30 40 60 / 20
а онда удесно око чвора 37:
32 / \ 30 37 / \ 20 50 / \ 40 60
Додајемо чвор 34:
32 / \ 30 37 / / \ 20 34 50 / \ 40 60
Пошто од деде до оца и од оца до сине воде гране у супротним смеровима, прво ротирамо удесно око чвора 37:
32 / \ 30 34 / \ 20 37 \ 50 / \ 40 60
а затим улево око чвора 32:
34 / \ 32 37 / \ 30 50 / / \ 20 40 60
Претражујемо кључ 33 путем 34 → 32 → нил, па 32 морамо да померимо до корена, тако да радимо ротацију удесно око 34:
32 / \ 30 34 / \ 20 37 \ 50 / \ 40 60
Претражујемо кључ 20 путем 32 → 30 → 20. Пошто грана од оца до сина и од деде до оца имају исти смер, радимо ротацију удесно око 32.
30 / \ 20 32 \ 34 \ 37 \ 50 / \ 40 60
а затим ротацију удесно око 30:
20 \ 30 \ 32 \ 34 \ 37 \ 50 / \ 40 60
Затим бришемо чвор 60. Прво радимо ротацију улево око 37:
20 \ 30 \ 32 \ 34 \ 50 / \ 37 60 \ 40
а затим ротацију улево око 50:
20 \ 30 \ 32 \ 34 \ 60 / 50 / 37 \ 40
60 и даље није у корену, тако да радимо ротацију улево око 32:
20 \ 30 \ 34 / \ 32 60 / 50 / 37 \ 40
па ротацију улево око 34:
20 \ 30 \ 60 / 34 / \ 32 50 / 37 \ 40
60 и даље није у корену, па радимо ротацију улево око 20:
30 / \ 20 60 / 34 / \ 32 50 / 37 \ 40
а затим ротацију улево око 30:
60 / 30 / \ 20 34 / \ 32 50 / 37 \ 40
Пошто 60 има само једно дете, само га уклањамо:
30 / \ 20 34 / \ 32 50 / 37 \ 40
Затим бришемо чвор 31, пролазећи путем 30 → 34 → 32 → нил. Пошто је 32 последњи чвор којем смо приступили, њега гурамо у корен тако да прво радимо ротацију удесно око 34:
30 / \ 20 32 \ 34 \ 50 / 37 \ 40
а затим ротацију улево око 30, чиме добијамо...
Коначно стабло:
32 / \ 30 34 / \ 20 50 / 37 \ 40
6. задатак
Поставка
Посматра се самоподешавајуће стабло дато показивачем на корен роот. Написати псеудокод операције сплит, која од једног датог стабла прави два нова тако да се у једном стаблу налазе сви кључеви мањи или једнаки од задатог кључа к, а у другом стаблу се налазе сви кључеви већи од кључа к. Сам кључ к не мора да се налази у почетном стаблу. Сматрати да операција СПЛАY(x) која врши ширење задатог чвора x постоји већ имплементирана.
Решење
SPLAY SPLIT(root, k) if (root = nil) then return nil, nil end_if x = root prev = left = right = nil while (x ≠ nil) do prev = x if (key(x) = k) then break else if (key(x) < k) then x = right(x) else x = left(x) end_if end_while SPLAY(prev) if key(prev) ≤ k then left = prev right = right(prev) right(left) = nil else right = prev left = left(prev) left(right) = nil end_if return left, right
7. задатак
Поставка
Написати у псеудокоду итеративну имплементацију функције која у стаблу бинарног претраживања на које указује показивач роот проналази чвор који садржи највећи кључ који је једнак или мањи од задатог кључа кеy. Кључ кеy не мора постојати у стаблу.
Решење
FIND BST FLOOR(root, key) largest = nil p = root while (p ≠ nil) do if (key(p) = key) then return key else if (key(p) < key) then largest = p p = right(p) else p = left(p) end_if end_while if (largest ≠ nil) then return key(largest) end_if return nil
8. задатак
Поставка
Нека се посматра стабло бинарног претраживања са слике са познатим вероватноћама успешног претраживања и неуспешног претраживања у табелама у прилогу.
25 / \ 12 33 \ 19
12 | 19 | 25 | 33 | |
---|---|---|---|---|
0.2 | 0.2 | 0.15 | 0.05 |
0.05 | 0.1 | 0.15 | 0.05 | 0.05 |
- Формално дефинисати, а затим израчунати цену C овог стабла.
- Уколико се од кључева у стаблу формира субоптимално стабло бинарног претраживања код кога се корен бира тако да разлика тежина левог и десног подстабла буде минимална, одредити такво стабло и образложити одговор.
Решење
Цена бинарног стабла претраживања дефинише се као: где су:
- вероватноће претраживања за неки од постојећих кључева ( одговара позицији кључа у уређеном низу кључева),
- вероватноће претраживања које ће завршити у једном од екстерних чворова стабла бинарног претраживања ( одговара позицији екстерног чвора при инордер обиласку свих екстерних чворова) и
- одговара нивоу чвора.
С горњом дефиницијом у виду, стаблу можемо доцртати екстерне чворове:
p3 / \ p1 p4 / \ / \ q1 p2 q4 q5 / \ q2 q3
и затим израчунати цену по формули:
У зависности од избора корена имаћемо различите чворове у левом и десном подстаблу. Израчунавамо разлику тежина у датом стаблу као . Пребацивањем корена на чвор 33 видимо да ће доћи до још мањег баланса тежина, стога корен пребацујемо на чвор 19 и добијамо стабло испод:
p2 / \ p1 p3 / \ / \ q1 q2 q3 p4 / \ q4 q5
За ово стабло израчунавамо разлику тежина као . Сада видимо да је баланс већи и да је прешао на другу страну, тако да знамо да ће пребацивањем корена на чвор 12 баланс бити мањи.