АСП2/К1 2019

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

1. задатак

Поставка

Дата је неопадајуће уређена проширена табела и одговарајући вектор битова валидности. Приказати изглед повећане табеле и вектора валидности након уметања сваког од кључева: 5, 28 и 29, а затим уклонити кључеве: 14 и 15 и приказати финално стање.

Стање низа из поставке задатка

4	7	10	14	15	15	21	24	25	40	45
1	0	0	1	0	0	0	1	0	1	0

Решење

Стање низа након уноса броја 5

4	5	5	14	15	15	21	24	25	40	45
1	1	0	1	0	0	0	1	0	1	0

Стање низа након уноса броја 28

4	5	5	14	15	15	21	24	25	28	40
1	1	0	1	0	0	0	1	0	1	1
Такође је могуће да се, уз напомену, при наиласку на кључ већи од траженог гледа лево уместо десно.

Стање низа након уноса броја 29

4	5	5	14	15	15	21	24	28	29	40
1	1	0	1	0	0	0	1	1	1	1
Постоје два начина на који можемо да решимо ситуацију кад наиђемо на 40 и не можемо да га померимо удесно: кажемо да се десила грешка пошто не можемо даље да умећемо, или померимо кључ 28 улево (препоручено).

Стање низа након брисања броја 14

4	5	5	14	15	15	21	24	28	29	40
1	1	0	0	0	0	0	1	1	1	1

При брисању кључа 15 дешава се грешка јер тај кључ не постоји.

2. задатак

Поставка

Нека је дат веома велики уређени низ арр дужине н. Познато је да вероватноћа претраживања кључева монотоно опада од почетка ка крају низа.

1. Предложити и кратко објаснити технику бинарног претраживања која обећава навећу^[сиц] ефикасност под задатим условима.
2. Написати у псеудокоду итеративну имплементацију функције која имплементира бинарно претраживање низа арр дужине н у складу са техником предложеном под а).

Решење

Начин за ефикасно бинарно претраживање овог низа јесте тако што се прво испитују кључеви на позицијама $2^i, i \in \mathbb{N}, 2^m \leq 2^n \leq n$ и затим када се одреде $m, n \in \mathbb{N}$ тако да $arr[2^m] < k < arr[2^n]$ на интервалу од $2^m$ до $2^n$ се спроводи бинарна претрага.

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

BINARY SEARCH PROB(arr, n, k)
low = 1
high = 2
while (high ≤ n) and (arr[high] < k) do
    low = high
    high = 2 * high
end_while
if (high > n) then
    high = n
end_if
while (low ≤ high) do
    mid = (low + high) / 2
    if (arr[mid] = k) then
        return mid
    else if (arr[mid] < k) then
        low = mid + 1
    else
        high = mid - 1
    end_if
end_while
return nil

3. задатак

Поставка

На слици је дато стабло бинарног претраживања. Потребно је трансформисати ово стабло у АВЛ стабло. Приказати трансформацију стабла по корацима.

   25
  /  \
 9    38
     /  \
    36   49
   /    /
  31   42
 /    /  \
27   40   45
            \
             47

Решење

Прво пронађемо критичне чворове у стаблу:

   25
  /  \
 9    38
     /  \
    36   49
   /    /
  31   42
 /    /  \
27   40   45
            \
             47

Затим радимо ротацију удесно око чвора 36 (његово лево дете нагиње на леву страну):

  25
 /  \
9    38
   /    \
  31     49
 /  \   /
27  36 42
      /  \
     40   45
            \
             47

чиме постижемо да чвор 36 више није критичан. Затим радимо ротацију улево око чвора 42 (лево дете чвора 49 нагиње на десну страну):

  25
 /  \
9    38
   /    \
  31     49
 /  \   /
27  36 45
      /  \
     42   47
    /
   40

па ротацију удесно око чвора 49:

    25
  /    \
 9      38
      /    \
     31     45
    /  \   /  \
   27  36 42   49
         /    /
        40  47

чиме постижемо да чвор 49 више није критичан. На крају радимо ротацију улево око чвора 25 (његово десно дете нагиње на десну страну) и добијамо...

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

        38
    /        \
  25          45
 /  \        /  \
9    31     42   49
    /  \   /    /
   27  36 40  47

4. задатак

Поставка

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

    10
   /  \
  5   18
 /   /  \
3   14  20
     \
     15
      \
      17

Решење

    10
   /  \
  5   18
 /   /  \
3   14  19
     \   \
     15  20
      \
      17

     10
   /    \
  5      18
 /     /    \
3     14    20
       \    /
       15  19
        \
        17

    10
   /  \
  5   19
 /   /  \
3   18  20
    /
   14
    \
    15
     \
     17

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     15
      \
      17
       \
       18

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     18
     /
    15
     \
      17

    10
   /  \
  5   19
 /   /  \
3   14  20
     \
     15
      \
      18
      /
     17

5. задатак

Поставка

Нека се у дато самоподешавајуће стабло редом убацују кључеви 37, 32, 34, након чега се претражује на кључеве 33 и 20, а затим се бришу кључеви 60 и 31. Приказати изглед стабла након сваког извршеног корака при уметању и брисању.

    50
   /  \
  30   60
 /  \
20  40

Решење

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

      32
     /  \
   30    34
  /        \
20          50
           /
         37
           \
            40

6. задатак

Поставка

Посматра се самоподешавајуће стабло дато показивачем на корен роот. Написати псеудокод операције сплит, која од једног датог стабла прави два нова тако да се у једном стаблу налазе сви кључеви мањи или једнаки од задатог кључа к, а у другом стаблу се налазе сви кључеви већи од кључа к. Сам кључ к не мора да се налази у почетном стаблу. Сматрати да операција СПЛАY(x) која врши ширење задатог чвора x постоји већ имплементирана.

Решење

SPLAY SPLIT(root, k)
if (root = nil) then
    return nil, nil
end_if
x = root
prev = left = right = nil
while (x ≠ nil) do
    prev = x
    if (key(x) = k) then
        break
    else if (key(x) < k) then
        x = right(x)
    else
        x = left(x)
    end_if
end_while
SPLAY(prev)
if key(prev) ≤ k then
    left = prev
    right = right(prev)
    right(left) = nil
else
    right = prev
    left = left(prev)
    left(right) = nil
end_if
return left, right

7. задатак

Поставка

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

Решење

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

8. задатак

Поставка

Нека се посматра стабло бинарног претраживања са слике са познатим вероватноћама успешног претраживања $p_i$ и неуспешног претраживања $q_i$ у табелама у прилогу.

   25
  /  \
12    33
  \
   19

$K_i$	12	19	25	33
$p_i$	0.2	0.2	0.15	0.05

$K_i$	$K_i < 12$	$12 < K_i < 19$	$19 < K_i < 25$	$25 < K_i < 33$	$33 < K_i$
$q_i$	0.05	0.1	0.15	0.05	0.05

1. Формално дефинисати, а затим израчунати цену C овог стабла.
2. Уколико се од кључева у стаблу формира субоптимално стабло бинарног претраживања код кога се корен бира тако да разлика тежина левог и десног подстабла буде минимална, одредити такво стабло и образложити одговор.

Решење

Цена бинарног стабла претраживања дефинише се као: $C = \sum_{i = 0}^{n} (p_i (h_i + 1) + q_i h_i)$ где су:

• $p_i$ вероватноће претраживања за неки од постојећих кључева ($i$ одговара позицији кључа у уређеном низу кључева),
• $q_i$ вероватноће претраживања које ће завршити у једном од екстерних чворова стабла бинарног претраживања ($i$ одговара позицији екстерног чвора при инордер обиласку свих екстерних чворова) и
• $h_i$ одговара нивоу чвора.

С горњом дефиницијом у виду, стаблу можемо доцртати екстерне чворове:

      p3
    /    \
  p1      p4
 /  \    /  \
q1   p2 q4  q5
    /  \
   q2  q3

и затим израчунати цену по формули:

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

$+ 2 \cdot 0.05 + 3 \cdot 0.1 + 3 \cdot 0.15 + 2 \cdot 0.05 + 2 \cdot 0.05 =$

$= 0.4 + 0.6 + 0.15 + 0.1 + 0.1 + 0.3 + 0.45 + 0.1 + 0.1 = 2.3$

У зависности од избора корена имаћемо различите чворове у левом и десном подстаблу. Израчунавамо разлику тежина у датом стаблу као $(p_1 + p_2 + q_1 + q_2 + q_3) - (p_4 + q_4 + q_5) = (0.2 + 0.2 + 0.05 + 0.1 + 0.15) - (0.05 + 0.05 + 0.05) = 0.7 - 0.15 = 0.55$. Пребацивањем корена на чвор 33 видимо да ће доћи до још мањег баланса тежина, стога корен пребацујемо на чвор 19 и добијамо стабло испод:

      p2
    /    \
  p1      p3
 /  \    /  \
q1  q2  q3   p4
            /  \
           q4  q5

За ово стабло израчунавамо разлику тежина као $(p_1 + q_1 + q_2) - (p_3 + p_4 + q_3 + q_4 + q_5) = (0.2 + 0.05 + 0.1) - (0.15 + 0.05 + 0.15 + 0.05 + 0.05) = 0.35 - 0.45 = -0.1$. Сада видимо да је баланс већи и да је прешао на другу страну, тако да знамо да ће пребацивањем корена на чвор 12 баланс бити мањи.