АСП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. Прецизност апроксимације контролисати посебним параметром функције.
Решење
Овде је идеја да нагађамо на ком се делу дужи, у процентима, налази пресек с кружницом. За свако нагађање рачунамо раздаљину од центра и ако је већа од полупречника то значи да смо ван круга, односно да треба да идемо ближе тачки Т1, у супротном треба да идемо ближе тачки Т2. Параметар p нам овде означава прецизност апроксимације у процентима дужине дужи.
INTERSECT(K, D)
p = 0.05
low = 0
high = 1
mid_x = 0
mid_y = 0
while high - low ≥ p do
mid = (high + low) / 2
mid_x = (x(T2) - x(T1)) * mid + x(T1)
mid_y = (y(T2) - y(T1)) * mid + y(T1)
diff = sqrt((mid_x - x(C)) * (mid_x - x(C)) + (mid_y - y(C)) * (mid_y - y(C)))
if diff = r then
return mid_x, mid_y
else if diff < r then
low = mid
else
high = mid
end_if
end_while
return mid_x, mid_y3. задатак
Поставка
Стабла бинарног претраживања
- На који начин се у стабло бинарног претраживања може дозволити уметање кључева са истом вредношћу?
- Написати у псеудокоду итеративну имплементацију функције која умеће вредност 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
right(node) = right(p)
right(p) = node
break
else 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_while4. задатак
Поставка
Црвено-црна стабла
- Дефинисати појам црне висине (енг. блацк хеигхт) неког чвора црвено-црног стабла.
- Написати у псеудокоду функцију која у задатом црвено-црном стаблу одређује црну висину задатог чвора X.
Решење
5. задатак
Поставка
Нека се у празно АВЛ стабло редом умећу кључеви 35, 75, 51, 61, 65, 80, 44, 48, 39, 77, а затим бришу кључеви 65, 44, 80. Приликом брисања, користити следбеника. Приказати изглед стабла након сваког извршеног уметања и брисања.
Решење
Поступак уметања можете симулирати у неком од симулатора за АВЛ стабла. Након уметања добије се следеће стабло:
65
/ \
44 77
/ \ / \
35 51 75 80
\ / \
39 48 60
По брисању чвора 65, његов следбеник чвор 75 долази на његово место:
75
/ \
44 77
/ \ \
35 51 80
\ / \
39 48 60
Затим се брише чвор 44 и његов следбеник чвор 48 долази на његово место:
75
/ \
48 77
/ \ \
35 51 80
\ \
39 60
На крају, брише се чвор 80 чиме чвор 75 постаје критичан чвор па радимо ротацију улево око њега:
48
/ \
35 75
\ / \
39 51 77
\
61
6. задатак
Поставка
У црвено-црно стабло са слике се најпре врши уметање кључа 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_if8. задатак
Поставка
а) Објаснити једну стратегију за добијање субоптималног стабла бинарног претраживања која укључује и успешна и неуспешна претраживања. б) Поступак илустровати по корацима ако су дати кључеви , са вероватноћама успешног претраживања , (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.1 између тежина подстабла, а К4 0.05, па зато бирамо К4 и процес настављамо за [1, 2, 3] и [5, 6].
- Једини кандидат за корен левог подстабла нам је К2, и зато њега постављамо као корен, К1 његово лево дете а К3 његово десно.
- Кандидат К6 је бољи од К5 јер омогућава разлику од 0.05 између тежина подстабала за разлику од 0.1, па њега постављамо као корен а К5 као његово лево дете и добијамо коначно стабло:
4 / \ 2 6 / \ / 1 3 5