АСП2/К1 2015
1. задатак
Поставка
Скуп кључева смештен је у стабло бинарног претраживања. Након брисања кључа 12, добијен је изглед стабла приказан на слици. Под претпоставком да је кључ 9 уметнут у стабло након кључа 12, да није било претходних брисања кључева и да се приликом брисања користи следбеник, приказати изглед стабла непосредно пре брисања кључа 12.
6
/ \
5 15
/ / \
3 7 18
\ \ /
4 9 16
/ \
8 17
Решење
6
/ \
5 15
/ / \
3 12 18
\ / /
4 7 16
\ \
9 17
/
8
6
/ \
5 15
/ / \
3 7 18
\ \ /
4 12 16
/ \
9 17
/
8
6
/ \
5 12
/ / \
3 7 15
\ \ \
4 9 18
/ /
8 16
\
17
6
/ \
5 12
/ / \
3 7 18
\ \ /
4 9 15
/ \
8 16
\
17
6
/ \
5 12
/ / \
3 7 18
\ \ /
4 9 16
/ / \
8 15 17
2. задатак
Поставка
Дат је круг К, са центром у тачки C, полупречника р. Дата је дуж D чије је теме Т1 унутар К, а теме Т2 изван К. Користећи методу бинарне претраге као идеју, написати у псеудокоду функцију која приближно одређује тачку пресека К и D. Прецизност апроксимације контролисати посебним параметром функције.
Решење
Користи се модификована бинарна претрага која се извршава док се тачка не нађе на кружници или док је грешка мања од err. Параметар err је прослеђен функцији.
INTERSECT(K, D, err)
low = T1
high = T2
prev = low
while true do
x(mid) = (x(low) + x(high)) / 2
y(mid) = (y(low) + y(high)) / 2
dist = distance(C, mid)
if (dist = r) or (distance(mid, prev) < err) then
return mid
else if dist > r then
high = mid
else
low = mid
end_if
prev = mid
end_while
DISTANCE(A, B)
return sqrt(pow(x(A) - x(B), 2) + pow(y(A) - y(B), 2))
3. задатак
Поставка
Стабла бинарног претраживања
- На који начин се у стабло бинарног претраживања може дозволити уметање кључева са истом вредношћу?
- Написати у псеудокоду итеративну имплементацију функције која умеће вредност x у стабло бинарног претраживања на које показује показивач роот. У стабло је дозвољено уметати кључеве са истом вредношћу.
Решење
Постоје два начина на које се може дозволити уметање кључева са истом вредношћу у бинарно стабло претраживања:
- У сваком чвору стабла се чува низ чворова које имају исту вредност кључа - овим се постиже да се структура стабла не повећава.
- Чворови са истом вредношћу се третирају као већи, односно чувају у десном подстаблу - овим се постиже већа погодност код коришћења за реализацију структура попут приоритетног реда.
BST INSERT MOD(root, x)
node = GETNODE
value(node) = x
if root = nil then
root = node
return
end_if
p = root
while true do
if key(p) ≤ x then
if right(p) = nil then
right(p) = node
break
else
p = right(p)
end_if
else
if left(p) = nil then
left(p) = node
break
else
p = left(p)
end_if
end_if
end_while
4. задатак
Поставка
Црвено-црна стабла
- Дефинисати појам црне висине (енг. блацк хеигхт) неког чвора црвено-црног стабла.
- Написати у псеудокоду функцију која у задатом црвено-црном стаблу одређује црну висину задатог чвора X.
Решење
Црна висина неког чвора је број црних чворова на путу од тог чвора до листова, и по дефиницији црвено-црног стабла је једнака за све путеве до листова.
BH CALC(x)
p = x
bh = 0
while p ≠ nil do
if (black(p)) then
bh = bh + 1
end_if
p = left(p)
end_while
return bh
5. задатак
Поставка
Нека се у празно АВЛ стабло редом умећу кључеви 35, 75, 51, 61, 65, 80, 44, 48, 39, 77, а затим бришу кључеви 65, 44, 80. Приликом брисања, користити следбеника. Приказати изглед стабла након сваког извршеног уметања и брисања.
Решење
Поступак уметања можете симулирати у неком од симулатора за АВЛ стабла. Након уметања добије се следеће стабло:
65
/ \
44 77
/ \ / \
35 51 75 80
\ / \
39 48 61
По брисању чвора 65, његов следбеник чвор 75 долази на његово место:
75
/ \
44 77
/ \ \
35 51 80
\ / \
39 48 61
Затим се брише чвор 44 и његов следбеник чвор 48 долази на његово место:
75
/ \
48 77
/ \ \
35 51 80
\ \
39 61
На крају, брише се чвор 80 чиме чвор 75 постаје критичан чвор па радимо ротацију улево око њега:
48
/ \
35 75
\ / \
39 51 77
\
61
6. задатак
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
Поставка
У црвено-црно стабло са слике се најпре врши уметање кључа 50, а затим врши брисање кључа 13. Приказати изглед стабла након сваке од наведених промена.
Решење
7. задатак
Поставка
Дати псеудокод и објаснити алгоритам одређивања претходника чвора са задатом адресом x у стаблу бинарног претраживања. Напомена: Приликом кретања уз стабло не користити проверу на припадност подстаблу, већ на вредности кључева.
Решење
Прво проверавамо да ли чвор има лево подстабло. Уколико има, враћамо најдеснији чвор у левом подстаблу као претходника чвора. Уколико нема, пењемо се уз стабло поредећи кључ чвора x са кључевима његових родитеља и ако нађемо чвор са мањим кључем вратимо га.
PRED NODE(x)
if left(x) = nil then
p = parent(x)
while p ≠ nil do
if key(p) < key(x) then
return p
end_if
p = parent(p)
end_while
return nil
else
p = left(x)
while right(p) ≠ nil do
p = right(p)
end_while
return p
end_if
8. задатак
Поставка
а) Објаснити једну стратегију за добијање субоптималног стабла бинарног претраживања која укључује и успешна и неуспешна претраживања. б) Поступак илустровати по корацима ако су дати кључеви , са вероватноћама успешног претраживања , (0.1, 0.05, 0.05, 0.1, 0.05, 0.1, респективно) и вероватноћама неуспешног претраживања (0.2, 0.05, 0.05, 0.0, 0.0, 0.05, 0.2, респективно).
Решење
- Можемо формирати субоптимално бинарно стабло претраживања одабирањем корена са најмањом разликом тежина између подстабала и рекурзивно понављати процес за оба подстабла.
-
- Кандидати за корен су нам К3 и К4. К3 нам даје разлику -0.05 између тежина подстабла, а К4 0.1, па зато бирамо К3 и процес настављамо за [1, 2] и [4, 5, 6].
- Са К1 у корену разлика између левог и десног подстабла од левог субоптималног подстабла је -0.05 а са К2 је 0.3, тако да постављамо К1 као корен левог подстабла.
- Са К6 у корену разлика између левог и десног подстабла од десног субоптималног подстабла је 0, са К5 -0.25 а са К4 -0.4, тако да постављамо К6 као корен десног подстабла.
- На крају, са К5 као кореном левог подстабла од десног подстабла добијамо да је разлика тежина 0.05, а са К4 -0.1, тако да К5 постављамо за корен левог подстабла од десног подстабла.
3
/ \
1 6
\ /
2 5
/
4