АСП2/К1 2016

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

1. задатак

Поставка

Ако је инордер обиласком неког стабла бинарног претраживања добијен низ кључева 1 5 8 9 11 14 приказати три могућа изгледа овог стабла са: (а) најмањом висином, (б) највећом висином и (ц) висином између најмање и највеће. Обележити стабло са најбољим и најлошијим перформансама операција.

Решење

Стабло А има најбоље перформансе операција:

    9
   / \
  5   11
 / \    \
1   8    14

Стабло Б има најлошије перформансе операција:

1
 \
  5
   \
    8
     \
      9
       \
        11
          \
           14

Стабло C нема ни најбоље ни најлошије перформансе операција:

        11
       /  \
      9    14
     /
    8
   /
  5
 /
1

2. задатак

Поставка

Дат је низ целих бројева. Користећи стабло бинарног претраживања, написати функцију која мења сваки елемент његовим следбеником. У случају да елемент нема следбеника, задржати оригиналну вредност. Резултат функције је низ преуредјен на описани начин.

Решење

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

ARR TRANSFORM(arr, n)
bst = nil
for i = 1 to n do
    BST-INSERT(bst, arr[i])
end_for
for i = 1 to n do
    key = arr[i]
    p = bst
    prev = nil
    while (p ≠ nil) and (key(p) ≠ key) do
        if key(p) > key then
            prev = p
            p = left(p)
        else
            p = right(p)
        end_if
    end_while
    p = right(p)
    while p ≠ nil do
        prev = p
        p = left(p)
    end_while
    if prev ≠ nil then
        arr[i] = key(prev)
    end_if
end_for

BST-INSERT(bst, key)
node = GETNODE
key(node) = key
if bst = nil then
    bst = node
else
    p = bst
    while true do
        if key(p) > key then
            if left(p) = nil then
                left(p) = node
                break
            else
                p = left(p)
            end_if
        else
            if right(p) = nil then
                right(p) = node
                break
            else
                p = right(p)
            end_if
        end_if
    end_while
end_if

3. задатак

Поставка

Нека је дат растуће уређени низ целих бројева (нпр., 1 2 3 5 7 9) или нека његова ротација (нпр., 5 7 9 1 2 3). Вредности се не понављају у низу. Написати у псеудокоду итеративну функцију која на ефикасан начин проналази минималну вредност у низу.

Решење

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

FIND MIN(arr, n)
low = 1
high = n
if arr[1] ≤ arr[n] then
    return 1
end_if
while low ≤ high do
    mid = (high + low) / 2
    if arr[mid] < arr[mid-1] then
        return mid
    else if arr[mid] < arr[1] then
        high = high - 1
    else
        low = low + 1
    end_if
end_while

4. задатак

Поставка

Бинарно претраживање у повећаној табели

1. Објаснити на који начин се врши уметање и брисање у повећаној табели.
2. Дата је повећана табела уређена неопадајуће и одговарајући вектор са битовима валидности. На слици је приказано тренутно стање. Приказати изглед повећане табеле и вектора валидности након уметања сваког од кљуцева: 6, 29 и 35, а затим уклонити кључеве : 18 и 23 и приказати финално стање.

Почетно стање повећане табеле

5	5	9	18	22	22	23	25	28	38	40
1	0	0	1	0	0	0	1	0	1	0

Решење

Уметање се врши тако што прво урадимо (бинарну) претрагу за неки кључ и ако утврдимо да постоји (да постоји кључ са траженом вредношћу у табели и да му је бит валидности постављен на 1) бацамо грешку, у супротном проверавамо бит валидности на пољу до којег смо дошли: ако је 1, морамо померити све валидне кључеве који следе након тог поља за једно место унапред како бисмо могли да убацимо кључ на то поље. При убацивању се бит валидности тог кључа постави на 1, сви следећи невалидни кључеви се поставе на ту вредност а сви претходни на вредност претходног валидног кључа.

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

Стање повећане табеле након уноса кључа 6

5	6	9	18	22	22	23	25	28	38	40
1	1	0	1	0	0	0	1	0	1	0

Стање повећане табеле након уноса кључа 29

5	6	9	18	22	22	23	25	29	38	40
1	1	0	1	0	0	0	1	1	1	0

Стање повећане табеле након уноса кључа 35

5	6	9	18	22	22	23	25	29	35	38
1	1	0	1	0	0	0	1	1	1	1

Стање повећане табеле након уклањања кључа 18

5	6	9	18	22	22	23	25	29	35	38
1	1	0	0	0	0	0	1	1	1	1

Брисањем кључа 23 дешава се грешка јер тај кључ не постоји.

5. задатак

Поставка

Дато је стабло бинарног претраживања. Да ли стабло задато на слици задовољава критеријум АВЛ стабла? Уколико не, извршити балансирање стабла по АВЛ критеријуму, а затим из добијеног стабла обрисати кључеве 55 и 20, па у стабло уметнути кључ 30. Приликом брисања, користити следбеника. Приказати изглед стабла након сваке извршене измене.

        20
       /  \
     17    32
    /     /  \
  10    25    33
 /     /  \     \
5     22  27     57
                /  \
               55  71

Решење

Видимо да су критични чворови овде 17, 32 и 33. Прво радимо десну ротацију око чвора 17:

      20
    /    \
  10      32
 /  \    /  \
5   17 25    33
      /  \     \
     22  27     57
               /  \
              55  71

чиме тај чвор више није критичан, али због скраћивања дужине левог подстабла чвор 20 постаје критичан. Затим радимо леву ротацију око чвора 33:

      20
    /    \
  10       32
 /  \    /    \
5   17 25      57
      /  \    /  \
     22  27  33   71
               \
                55

чиме чворови 32 и 33 више нису критични. На крају, радимо леву ротацију око чвора 20:

             32
          /      \
      20           57
   /      \       /  \
  10      25    33    71
 /  \    /  \     \
5   17  22  27     55

6. задатак

Поставка

Датотека:АСП2 К1 2016 задатак 6 стабло.пнг

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

У црвено-црном стаблу са слике се најпре изврши брисање кључа 35, а затим уметање кључева 9, 43, 10. Приказати изглед стабла након сваке од наведених промена.

7. задатак

Поставка

1. У псеудокоду написати функцију која за АВЛ стабло задате висине х израчунава најмањи број чворова које стабло може да садржи.
2. На којој висини може да се налази лист најближи корену?
3. Како се називају оваква стабла и по чему су добила име?

Решење

1. Псеудокод је дат испод.
2. цеил(х / 2)
3. Оваква стабла, која су најгори случајеви АВЛ стабала, добила су име по Фибоначијевим бројевима чија се рекурзивна дефиниција веома мало разликује са рекурзивном дефиницијом броја чворова оваквих стабала у зависности од њихове висине.

AVL MIN NODES(h)
if h = 0 then
    return 1
else if h = 1 then
    return 2
else
    return AVL_MIN_NODES(h - 1) + AVL_MIN_NODES(h - 2) + 1
end_if

8. задатак

Поставка

За стабло бинарног претраживања које садржи кључеве К1 < К2 < ... < Кн и чији је корен кључ Кр извести везу цене стабла и цена подстабла. Обавезно објаснити поступак.

Решење

Цена подстабла које садржи кључеве $K_{i+1}, K_{i+2}, ..., K_j$ означава се са $T_{ij}$ и има вредност $q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j$, што је заправо збир вероватноћа претраживања свих интерних и екстерних чворова тог подстабла. Пошто један чвор има своју вероватноћу претраживања као и два подстабла, добијамо да је цена целог стабла чији је корен $K_r$ рекурзивно дефинисана са $T = T_{1,r} + p_r + T_{r+1,n}$.