АСП2/К1 2016
1. задатак
Поставка
Ако је инордер обиласком неког стабла бинарног претраживања добијен низ кључева 1 5 8 9 11 14 приказати три могућа изгледа овог стабла са: (а) најмањом висином, (б) највећом висином и (ц) висином између најмање и највеће. Обележити стабло са најбољим и најлошијим перформансама операција.
Решење
Стабло А има најбоље перформансе операција:
9 / \ 5 11 / \ \ 1 8 14
Стабло Б има најлошије перформансе операција:
1
\
5
\
8
\
9
\
11
\
14
Стабло C нема ни најбоље ни најлошије перформансе операција:
11
/ \
9 14
/
8
/
5
/
1
2. задатак
Поставка
Дат је низ целих бројева. Користећи стабло бинарног претраживања, написати функцију која мења сваки елемент његовим следбеником. У случају да елемент нема следбеника, задржати оригиналну вредност. Резултат функције је низ преуредјен на описани начин.
Решење
Овде прво пребацујемо задати низ у бинарно стабло претраживања користећи функцију за уметање чвора а затим за сваки елемент низа проналазимо следбеника слично као у другом задатку са првог колоквијума 2018.
ARR TRANSFORM(arr, n)
bst = nil
for i = 1 to n do
BST-INSERT(bst, arr[i])
end_for
for i = 1 to n do
key = arr[i]
p = bst
prev = nil
while (p ≠ nil) and (key(p) ≠ key) do
if key(p) > key then
prev = p
p = left(p)
else
p = right(p)
end_if
end_while
p = right(p)
while p ≠ nil do
prev = p
p = left(p)
end_while
if prev ≠ nil then
arr[i] = key(prev)
end_if
end_for
BST-INSERT(bst, key)
node = GETNODE
key(node) = key
if bst = nil then
bst = node
else
p = bst
while true do
if key(p) > key then
if left(p) = nil then
left(p) = node
break
else
p = left(p)
end_if
else
if right(p) = nil then
right(p) = node
break
else
p = right(p)
end_if
end_if
end_while
end_if
3. задатак
Поставка
Нека је дат растуће уређени низ целих бројева (нпр., 1 2 3 5 7 9) или нека његова ротација (нпр., 5 7 9 1 2 3). Вредности се не понављају у низу. Написати у псеудокоду итеративну функцију која на ефикасан начин проналази минималну вредност у низу.
Решење
Овај проблем се своди на бинарну претрагу са измењеним условима: сада детектујемо да ли се налазимо лево или десно од тражене вредности поредећи се са првим елементом (уколико је тренутни елемент већи од првог, лево смо од тражене вредности) а детекцију тражене вредности тако што проверимо да ли је елемент лево од тренутног већи од њега (то значи да смо дошли на почетак неротираног низа).
FIND MIN(arr, n)
low = 1
high = n
if arr[1] ≤ arr[n] then
return arr[1]
end_if
while low ≤ high do
mid = (high + low) / 2
if arr[mid] < arr[mid-1] then
return arr[mid]
else if arr[mid] < arr[1] then
high = mid - 1
else
low = mid + 1
end_if
end_while
4. задатак
Поставка
Бинарно претраживање у повећаној табели
- Објаснити на који начин се врши уметање и брисање у повећаној табели.
- Дата је повећана табела уређена неопадајуће и одговарајући вектор са битовима валидности. На слици је приказано тренутно стање. Приказати изглед повећане табеле и вектора валидности након уметања сваког од кљуцева: 6, 29 и 35, а затим уклонити кључеве : 18 и 23 и приказати финално стање.
| 5 | 5 | 9 | 18 | 22 | 22 | 23 | 25 | 28 | 38 | 40 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
Решење
Уметање се врши тако што прво урадимо (бинарну) претрагу за неки кључ и ако утврдимо да постоји (да постоји кључ са траженом вредношћу у табели и да му је бит валидности постављен на 1) бацамо грешку, у супротном проверавамо бит валидности на пољу до којег смо дошли: ако је 1, морамо померити све валидне кључеве који следе након тог поља за једно место унапред како бисмо могли да убацимо кључ на то поље. При убацивању се бит валидности тог кључа постави на 1, сви следећи невалидни кључеви се поставе на ту вредност а сви претходни на вредност претходног валидног кључа.
При брисању се након претраге за дати кључ, бит валидности кључа само постави на 0 уколико постоји или баци грешка уколико не постоји.
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 28 | 38 | 40 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 25 | 29 | 38 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| Такође је могуће да се, уз напомену, при наиласку на кључ већи од траженог гледа лево уместо десно. | ||||||||||
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 29 | 35 | 38 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Постоје два начина на који можемо да решимо ситуацију кад наиђемо на 38 и не можемо да га померимо удесно:
| ||||||||||
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 29 | 35 | 38 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Брисањем кључа 23 дешава се грешка јер тај кључ не постоји.
5. задатак
Поставка
Дато је стабло бинарног претраживања. Да ли стабло задато на слици задовољава критеријум АВЛ стабла? Уколико не, извршити балансирање стабла по АВЛ критеријуму, а затим из добијеног стабла обрисати кључеве 55 и 20, па у стабло уметнути кључ 30. Приликом брисања, користити следбеника. Приказати изглед стабла након сваке извршене измене.
20
/ \
17 32
/ / \
10 25 33
/ / \ \
5 22 27 57
/ \
55 71
Решење
Видимо да су критични чворови овде 17 и 33. Прво радимо десну ротацију око чвора 17:
20
/ \
10 32
/ \ / \
5 17 25 33
/ \ \
22 27 57
/ \
55 71
чиме тај чвор више није критичан, али због скраћивања дужине левог подстабла чвор 20 постаје критичан. Затим радимо леву ротацију око чвора 33:
20
/ \
10 32
/ \ / \
5 17 25 57
/ \ / \
22 27 33 71
\
55
чиме чвор 33 више није критичан. На крају, радимо леву ротацију око чвора 20:
32
/ \
20 57
/ \ / \
10 25 33 71
/ \ / \ \
5 17 22 27 55
Брише се чвор 55. Чвор је лист тако да је брисање тривијално. Стабло остаје балансирано након брисања овог чвора.
32
/ \
20 57
/ \ / \
10 25 33 71
/ \ / \
5 17 22 27
Бришемо чвор 20. На његово место стављамо његовог следбеника 22.
32
/ \
22 57
/ \ / \
10 25 33 71
/ \ \
5 17 27
Умећемо чвор 30 као десног сина 27.
32
/ \
22 57
/ \ / \
10 25 33 71
/ \ \
5 17 27
\
30
Његовим уметањем чвор 25 постаје критичан па зато радимо ротацију улево око њега и тиме добијамо...
Коначно стабло:
32
/ \
22 57
/ \ / \
10 27 33 71
/ \ / \
5 17 25 30
6. задатак
Поставка
У црвено-црном стаблу са слике се најпре изврши брисање кључа 35, а затим уметање кључева 9, 43, 10. Приказати изглед стабла након сваке од наведених промена.
Решење
7. задатак
Поставка
- У псеудокоду написати функцију која за АВЛ стабло задате висине х израчунава најмањи број чворова које стабло може да садржи.
- На којој висини може да се налази лист најближи корену?
- Како се називају оваква стабла и по чему су добила име?
Решење
- Псеудокод је дат испод.
- цеил(х / 2). Ово је зато што су подстабла Фибоначијевих стабала исто Фибоначијева стабла, тако да се најмања висина листа израчунава као најмања висина листа Фибоначијевог стабла чија је висина за 2 мања од тренутног увећана за 1.
- Оваква стабла, која су најгори случајеви АВЛ стабала, добила су име по Фибоначијевим бројевима чија се рекурзивна дефиниција веома мало разликује од рекурзивне дефиниције броја чворова оваквих стабала у зависности од њихове висине.
AVL MIN NODES(h)
if h = 0 then
return 1
else if h = 1 then
return 2
else
return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1
end_if
8. задатак
Поставка
За стабло бинарног претраживања које садржи кључеве К1 < К2 < ... < Кн и чији је корен кључ Кр извести везу цене стабла и цена подстабла. Обавезно објаснити поступак.
Решење
Цена подстабла се дефинише као:
где су вероватноће успешног, неуспешног претраживања а висине чворова .
Узимамо да су први чвор левог подстабла и последњи чвор десног подстабла тренутног чвора по инордер поретку и а тренутни чвор . Пошто је висина у формули за цене левог и десног подстабла сада повећана за 1, добијамо да је укупна цена тренутног чвора једнака: