АСП2/К1 2018

Задаци на страници предмета.

1. задатак

Поставка

Оптимално стабло бинарног претраживања

1. Навести формулу за израчунавање цене оптималног стабла бинарног претраживања и објаснити је.
2. Уколико се посматрају три кључа $K_1 < K_2 < K_3$ са познатим вероватноћама успешног претраживања п1 = 0.2, п2 = 0.05, п3 = 0.1 и неуспешног претраживања q0 = 0.15, q1 = 0.2, q2 = 0.1 и q3 = 0.2, одредити и нацртати оптимално стабло бинарног претраживања.

Решење

Формула је написана и објашњена у осмом задатку на првом колоквијуму 2019. године.

Постоји пет распореда ових чворова ($p_i$ означавају кључеве а $q_i$ екстерне чворове стабла):

   p1
  /  \
q0    p2
     /  \
   q1    p3
        /  \
      q2    q3

$C = 1 \cdot 0.2 + 2 \cdot 0.05 + 3 \cdot 0.1 +$

$+ 1 \cdot 0.15 + 2 \cdot 0.2 + 3 \cdot 0.1 + 3 \cdot 0.2 =$

$= 0.2 + 0.1 + 0.3 + 0.15 + 0.4 + 0.3 + 0.6 = 2.05$

       p2
    /      \
   p1       p3
  /  \     /  \
q0    q1 q2    q3

$C = 2 \cdot 0.2 + 1 \cdot 0.05 + 2 \cdot 0.1 +$

$+ 2 \cdot 0.15 + 2 \cdot 0.2 + 2 \cdot 0.1 + 2 \cdot 0.2 =$

$= 0.4 + 0.05 + 0.2 + 0.3 + 0.4 + 0.2 + 0.4 = 1.95$

         p3
        /  \
      p2    q3
     /  \
   p1    q2
  /  \
q0    q1

$C = 3 \cdot 0.2 + 2 \cdot 0.05 + 1 \cdot 0.1 +$

$+ 3 \cdot 0.15 + 3 \cdot 0.2 + 2 \cdot 0.1 + 1 \cdot 0.2 =$

$= 0.6 + 0.1 + 0.1 + 0.45 + 0.6 + 0.2 + 0.2 = 2.25$

   p1
  /  \
q0    p3
     /  \
   p2    q3
  /  \
q1    q2

$C = 1 \cdot 0.2 + 3 \cdot 0.05 + 2 \cdot 0.1 +$

$+ 1 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 2 \cdot 0.2 =$

$= 0.2 + 0.15 + 0.2 + 0.15 + 0.6 + 0.3 + 0.4 = 2$

      p3
     /  \
   p1    q3
  /  \
q0    p2
     /  \
   q1    q2

$C = 2 \cdot 0.2 + 3 \cdot 0.05 + 1 \cdot 0.1 +$

$+ 2 \cdot 0.15 + 3 \cdot 0.2 + 3 \cdot 0.1 + 1 \cdot 0.2 =$

$= 0.4 + 0.15 + 0.1 + 0.3 + 0.6 + 0.3 + 0.2 = 2.05$

Овим добијамо да је оптимално стабло бинарног претраживања за ова три кључа стабло у којем је $K_2$ у корену.

2. задатак

Поставка

Написати у псеудокоду ефикасну итеративну имплементацију функције која у стаблу бинарног претраживања на чији корен указује показивач роот проналази следбеника чвора који садржи кључ кеy. У оквиру чвора стабла не постоји показивач на оца.

Решење

Идеја је да уместо инордер обиласка искористимо чињеницу да се следбеник чвора са кључем кеy може пронаћи једним спуштањем низ стабло у претрази за кључем кеy. Постоје два случаја:

1. када чвор са кључем кеy има десно подстабло, знамо да се у њему сигурно налази његов следбеник као најлевље дете десног подстабла, и
2. када тај чвор нема десно подстабло, узимамо последњи чвор код кога смо утврдили да му је кључ већи од кључа који тражимо (последњи чвор код кога смо "отишли лево").

FIND BST SUCC(root, key)
p = root
succ = nil
while (key(p) ≠ key) do
    if (key(p) < key) then
        p = right(p)
    else if (key(p) > key) then
        succ = p
        p = left(p)
    end_if
end_while
if (right(p) ≠ nil) then
    p = right(p)
    while (p ≠ nil) do
        succ = p
        p = left(p)
    end_while
end_if
return succ

3. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Црвено-црно стабло из поставке задатка.

Нека се посматра црвено-црно стабло са слике. Приказати изглед стабла по корацима након уметања кључева 81 и 79 и уклањања кључа 23.

4. задатак

Поставка

У стаблу бинарне претраге грешком су два чвора заменила своје позиције. Имплементирати функцију ЦОРРЕЦТ_БСТ која исправља грешку и враћа ова два чвора на своје праве позиције. Сваки чвор осим целобројног кључа и показивача на лево и десно подстабло садржи и показивач на оца.

Решење

Под заменом чворова се не мисли само на замену кључева у тим чворовима већ на замену заједно са подстаблима, тако да једна замена не може имати каскадне последице већ ће само два чвора остати неконзистентна.

Идеја је на стек гурамо децу чворова за које одредимо да упадају у границе претраге по стаблу бинарног претраживања, а ако не упадају сместимо их у једну од две променљиве и након тога заменимо, пазећи да заменимо и показиваче на родитеље и родитељске показиваче.

CORRECT BST(root)
STACK_INIT(S_nodes)
STACK_INIT(S_low)
STACK_INIT(S_high)
PUSH(S_nodes, root)
PUSH(S_low, -∞)
PUSH(S_high, +∞)
while not STACK_EMPTY(S_nodes) do
    node = POP(S_nodes)
    low = POP(S_low)
    high = POP(S_high)
    if low < key(node) < high then
        if left(node) ≠ nil then
            PUSH(S_nodes, left(node))
            PUSH(S_low, low)
            PUSH(S_high, key(node))
        end_if
        if right(node) ≠ node then
            PUSH(S_nodes, right(node))
            PUSH(S_low, key(node))
            PUSH(S_high, high)
        end_if
    else
        if first = nil then
            first = node
        else
            second = node
            break
        end_if
    end_if
end_while
tmp = parent(first)
parent(first) = parent(second)
parent(second) = tmp
if left(parent(first)) = second then
    left(parent(first)) = first
else
    right(parent(first)) = first
end_if
if left(parent(second)) = first then
    left(parent(second)) = second
else
    right(parent(second)) = second
end_if

5. задатак

Поставка

Нека се у празно АВЛ стабло редом убацују кључеви 27, 12, 7, 34, 31, 5, 6, а затим се бришу кључеви 31, 34, 12. Приликом брисања користити претходника. Приказати изглед стабла након сваког извршеног корака при уметању и брисању.

Решење

Коначно стабло је:

    7
   / \
  6   27
 /
5

Поступак можете симулирати у неком од симулатора за АВЛ стабла.

6. задатак

Поставка

Користећи методу бинарне претраге као идеју, написати у псеудокоду функцију која ефикасно проверава да ли је тачка Т теме н-тоугла M. Многоугао M се задаје помоћу низа тачака – темена. Тачке су одређене координатама x и y. Низ темена многоугла је уређен растуће по вредности координате x, при чему за исту вредност координате x важи растућа уређеност по вредности координате y.

Решење

Овде се ради обична бинарна претрага с тим што се услови за одлазак улево или удесно мењају: уколико је x координата тренутне тачке већа од тражене, или уколико су исте али је y координата већа од тражене, иде се улево, а уколико је x координата тренутне тачке мања од тражене, или уколико су исте али је y координата мања од тражене, иде се удесно.

CHECK VERTEX(M, n, T)
low = 1
high = n
while low ≤ high do
    mid = (high + low) / 2
    if (x(M[mid]) = x(T)) and (y(M[mid]) = y(T)) then
        return true
    else if (x(M[mid]) < x(T)) or ((x(M[mid]) = x(T)) and (y(M[mid]) < y(T))) then
        low = mid + 1
    else
        high = mid - 1
    end_if
end_while
return false

Поступак се могао поједноставити уколико се претпостави да не може постојати више од две тачке са истом x координатом, јер би у том случају те тачке биле колинеарне и не би могле да буду темена н-тоугла.

7. задатак

Поставка

Дат је неуређени низ А дужине н целобројних кључева у опсегу вредности 1..100 који се претражује и неуређени низ кључева К много веће дужине м на које се врши претрага. У низу К има велики број поновљених кључева. Због неравномерне вероватноће претраге кључева, користи се следећа техника оптимизације. Након сваког успешног претраживања, врши се пребацивање за п позиција унапред, где је п број успешних налажења тог кључа. Написати у псеудокоду функцију која редом претражује низ А на кључеве из низа К и враћа просечан број поређења по нађеном кључу.

Решење

SEARCH(A, K, n, m)
for i = 1 to 100 do
    P[i] = 0
end_for
sum = 0
num = 0
for i = 1 to m do
    key = K[i]
    found = 0
    for j = 1 to n do
        if A[j] = key then
            found = j
            break
        end_if
    end_for
    if found ≠ 0 then
        sum = sum + j
        num = num + 1
        P[key] = P[key] + 1
        for k = found downto found - P[key] + 1 do
            A[k] = A[k-1]
        end_for
        A[found - P[key]] = key
    end_if
end_for
if num = 0 then
    return 0
else
    return sum/num
end_if

8. задатак

Поставка

Образложити да ли је следећа секвенца кључева валидна у стаблу бинарног претраживања:

1. Ако се приликом успешног претраживања у једном стаблу редом проверавају кључеви 23, 87, 158, 348, 160, 200, 150, 158.
2. Ако се приликом неуспешног претраживања у другом стаблу редом проверавају кључеви 546, 453, 427, 68, 415, 231, 247, 417, 300.

Решење

Овде гледамо наш силазак низ потенцијални БСТ и на основу претходно погледаних чворова одређујемо границе хигх и лоw у којима се морају налазити наредни кључеви како би стабло било валидан БСТ. Добијамо да оба случаја нису могућа у бинарном стаблу претраживања.

1. 1. 23 → 87, лоw = 23, хигх = +∞
   2. 87 → 158, лоw = 87, хигх = +∞
   3. 158 → 348, лоw = 158, хигх = +∞
   4. 348 → 160, лоw = 158, хигх = 348
   5. 160 → 200, лоw = 160, хигх = 348
   6. 200 → 150, 150 < лоw => ⚡
2. 1. 546 → 453, лоw = -∞, хигх = 546
   2. 453 → 427, лоw = -∞, хигх = 453
   3. 427 → 68, лоw = -∞, хигх = 427
   4. 68 → 415, лоw = 68, хигх = 427
   5. 415 → 231, лоw = 68, хигх = 415
   6. 231 → 247, лоw = 231, хигх = 415
   7. 247 → 417, 417 > хигх => ⚡