АСП2/К1 2017
1. задатак
Поставка
Упоредити методе бинарне и вишеструке секвенцијалне претраге над уређеним низом целих бројева 3, 7, 10, 11, 18, 22, 25, 27, 39, 41, 45, 48, 56, 64, 65, 78, 86. Одредити број поређења при претрази кључева 25 и 44 за обе технике.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 7 | 10 | 11 | 18 | 22 | 25 | 27 | 39 | 41 | 45 | 48 | 56 | 64 | 65 | 78 | 86 |
Решење
Вишеструком секвенцијалном претрагом прво идемо од кључа 3 до кључа 25, чиме радимо 7 поређења на неједнакост и једно поређење на једнакост, а затим идемо од кључа 25 до кључа 45 чиме радимо 5 поређења на неједнакост и једно поређење на једнакост, што укупно даје 14 поређења на вредност кључа.
Бинарном претрагом прво гађамо кључ 39 (2), па 11 (2), па 22 (2) и на крају 25 (1), а затим у другој претрази 39 (2), па 56 (2), па 45 (2), па 41 (2) и ту се претрага завршава неуспешно, чиме вршимо 15 поређења на вредност кључа.
2. задатак
Поставка
Функцији ФИНД_БСТ прослеђен је показивач роот на корен једног комплетног бинарног стабла. Структура чвора овог стабла осим кључа, показивача на лево и десно подстабло, садржи и показивач на оца. Имплементирати итеративну функцију ФИНД_БСТ чија повратна вредност треба да буде показивач на корен оног подстабла које представља стабло бинарне претраге. Уколико постоји више оваквих подстабала, треба вратити показивач на корен оног подстабла са максималним бројем чворова. Проверу да ли је неко подстабло стабло бинарне претраге издвојити у посебну функцију. Обавезно кратко прокоментарисати решење.
Решење
Овде нам је најпогодније да постордер обиласком одређујемо да ли су чворови бинарна стабла претраживања, јер тако кад стигнемо до виших чворова већ знамо да ли су им деца исправна бинарна стабла претраживања. С тим у виду, имплементација тражене функције за проверу изгледа овако:
IS BST(node, left_child_valid_bst, right_child_valid_bst)
if (not left_child_valid_bst) or (not right_child_valid_bst) or (node = nil) then
return false
end_if
if key(left(node)) < key(node) < key(right(node)) then
return true
end_if
return falseКао позивне аргументе ове функције примамо да ли су нам лево и десно дете чвора валидни БСТ, што би значило да треба да те податке чувамо у неком реду како бисмо из родитеља могли да тим информацијама приступимо. Обилазак креће од реда листова и креће се тако што сваки лист гура свог родитеља у ред, а дупликати родитеља се избацују из реда приликом њиховог обиласка.
FIND BST(root)
if root = nil then
return nil
end_if
last_bst = nil
QUEUE_INIT(Q_valid_bst)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_inv_nodes)
INSERT(Q_nodes, root)
while (not QUEUE_EMPTY(Q_nodes)) do
node = DELETE(Q_nodes)
if left(node) ≠ nil then
INSERT(Q_nodes, left(node))
INSERT(Q_nodes, right(node))
else
INSERT(Q_inv_nodes, node)
end_if
end_while
while (not QUEUE_EMPTY(Q_inv_nodes)) do
node = DELETE(Q_inv_nodes)
if left(node) = nil then
left_valid = true
right_valid = true
else
DELETE(Q_inv_nodes)
left_valid = DELETE(Q_valid_bst)
right_valid = DELETE(Q_valid_bst)
end_if
valid_bst = IS_BST(node, left_valid, right_valid)
if valid_bst then
last_bst = node
end_if
INSERT(Q_valid_bst, valid_bst)
INSERT(Q_inv_nodes, parent(node))
end_while
return last_bst3. задатак
Поставка
Нека се посматра црвено-црно стабло са слике. Приказати изглед стабла по корацима након уметања кључева 7 и 10.
Решење
4. задатак
Поставка
Користећи модификовану бинарну претрагу, написати у псеудукоду итеративну функцију која враћа позицију претходника и следбеника задате вредности к у задатом уређеном низу арр. Вредност к не мора постојати у низу.
Решење
Овде се претпоставља да се кључеви у низу не могу понављати.
ARR PRED SUCC(arr, k)
while high >= low do
mid = (high + low) / 2
if arr[mid] = k then
return mid-1, mid+1
else if arr[mid] < k then
low = mid + 1
else
high = mid - 1
end_if
end_while
if arr[mid] < k then
return mid, mid+1
else
return mid-1, mid
end_if5. задатак
Поставка
Нека се у празно АВЛ стабло редом убацују кључеви 12, 43, 23, 55, 72, 2, 60, 57, 89, а затим се бришу кључеви 12, 23 и 57. Приликом брисања користити претходника. Приказати изглед стабла након сваког извршеног корака при уметању и брисању
Решење
Коначно стабло је:
60
/ \
43 72
/ \ \
2 55 89
Поступак можете симулирати у неком од симулатора за АВЛ стабла.
6. задатак
Поставка
Написати у псеудокоду функцију која ефикасно проверава да ли је дато бинарно стабло претраге бст балансирано по АВЛ критеријуму. Поред показивача на оца и левог и десног сина, чвор стабла садржи и податке о висини левог и десног подстабла.
Решење
Пошто не морамо да израчунавамо висине подстабла, овај задатак се своди на посећивање свих чворова како бисмо упоредили све висине левих и десних подстабала у једном чвору. Уколико се у неком разликују за више од 1, стабло није балансирано по АВЛ критеријуму.
CHECK AVL BALANCED(bst)
INIT_STACK(S)
PUSH(S, bst)
while (not STACK_EMPTY(S)) do
node = POP(S)
if abs(height_l(node) - height_r(node)) > 1 then
return false
end_if
if height_l(node) > 2 then
PUSH(S, left(node))
end_if
if height_r(node) > 2 then
PUSH(S, right(node))
end_if
end_while
return true7. задатак
Поставка
Субоптимално стабло бинарног претраживања
- Објаснити алгоритам за одређивање субоптималног стабла бинарног претраживања који је заснован на тежинама подстабала.
- Ако су за н кључева дате вероватноће успешног претраживања у низу П, а неуспешног у низу Q, написати ефикасну имплементацију функције која налази само корен тог стабла.
Решење
Одређивање субоптималног стабла бинарног претраживања заснованог на тежинама подстабала, где је тежина подстабла које укључује чворове на позицијама од до у табели дефинисана као , се врши тако што се прво одреди кључ који, кад постављен за корен, даје најмању разлику тежина левог и десног подстабла, а затим се тај процес примени рекурзивно на лево и десно подстабло (подниз) како би се и њихови корени одредили.
FIND ROOT(P, Q, n)
min_key = 1
left = Q[1]
right = 1 - left - P[1]
min_diff = abs(right - left)
for i = 2 to n do
left = left + Q[i] + P[i-1]
right = 1 - left - P[i]
diff = abs(right - left)
if diff < min_diff then
min_diff = diff
min_key = i
end_if
end_for
return min_key
end_for8. задатак
Поставка
Нека се у самоподешавајуће стабло умећу редом кључеви 50, 70, 30, 60, 40, затим се претражује на 70, па се умеће 45 и, на крају, претражује на 30. Приказати изглед стабла након сваке операције.
Решење
Коначно стабло је:
30
\
40
\
45
\
60
/ \
50 70
Поступак можете симулирати у неком од симулатора за самоподешавајућа стабла.