АСП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_max, right_min) if left_max < key(node) < right_min 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) QUEUE_INIT(Q_max) QUEUE_INIT(Q_min) 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 valid_bst = true curr_max = key(node) curr_min = key(node) else DELETE(Q_inv_nodes) left_valid = DELETE(Q_valid_bst) right_valid = DELETE(Q_valid_bst) left_min = DELETE(Q_min) right_min = DELETE(Q_min) left_max = DELETE(Q_max) right_max = DELETE(Q_max) if left_valid and right_valid and IS_BST(node, left_max, right_min) then valid_bst = true else valid_bst = false end_if curr_max = max(key(node), left_max, right_max) curr_min = min(key(node), left_min, right_min) end_if if valid_bst then last_bst = node end_if INSERT(Q_valid_bst, valid_bst) INSERT(Q_inv_nodes, parent(node)) INSERT(Q_min, curr_min) INSERT(Q_max, curr_max) end_while return last_bst
3. задатак
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
Поставка
Нека се посматра црвено-црно стабло са слике. Приказати изглед стабла по корацима након уметања кључева 7 и 10.
Решење
4. задатак
Поставка
Користећи модификовану бинарну претрагу, написати у псеудукоду итеративну функцију која враћа позицију претходника и следбеника задате вредности к у задатом уређеном низу арр. Вредност к не мора постојати у низу.
Решење
Овде се претпоставља да се кључеви у низу не могу понављати.
ARR PRED SUCC(arr, k) while (low ≤ high) 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_if
5. задатак
Поставка
Нека се у празно АВЛ стабло редом убацују кључеви 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 true
7. задатак
Поставка
Субоптимално стабло бинарног претраживања
- Објаснити алгоритам за одређивање субоптималног стабла бинарног претраживања који је заснован на тежинама подстабала.
- Ако су за н кључева дате вероватноће успешног претраживања у низу П, а неуспешног у низу 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
8. задатак
Поставка
Нека се у самоподешавајуће стабло умећу редом кључеви 50, 70, 30, 60, 40, затим се претражује на 70, па се умеће 45 и, на крају, претражује на 30. Приказати изглед стабла након сваке операције.
Решење
Коначно стабло је:
30 \ 40 \ 45 \ 60 / \ 50 70
Поступак можете симулирати у неком од симулатора за самоподешавајућа стабла.