АСП2/К1 2017

Zadaci sa stranice predmeta.

1. zadatak

Postavka

Uporediti metode binarne i višestruke sekvencijalne pretrage nad uređenim nizom celih brojeva 3, 7, 10, 11, 18, 22, 25, 27, 39, 41, 45, 48, 56, 64, 65, 78, 86. Odrediti broj poređenja pri pretrazi ključeva 25 i 44 za obe tehnike.

Tabela iz postavke zadatka.

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

Rešenje

Višestrukom sekvencijalnom pretragom prvo idemo od ključa 3 do ključa 25, čime radimo 7 poređenja na nejednakost i jedno poređenje na jednakost, a zatim idemo od ključa 25 do ključa 45 čime radimo 5 poređenja na nejednakost i jedno poređenje na jednakost, što ukupno daje 14 poređenja na vrednost ključa.

Binarnom pretragom prvo gađamo ključ 39 (2), pa 11 (2), pa 22 (2) i na kraju 25 (1), a zatim u drugoj pretrazi 39 (2), pa 56 (2), pa 45 (2), pa 41 (2) i tu se pretraga završava neuspešno, čime vršimo 15 poređenja na vrednost ključa.

2. zadatak

Postavka

Funkciji FIND_BST prosleđen je pokazivač root na koren jednog kompletnog binarnog stabla. Struktura čvora ovog stabla osim ključa, pokazivača na levo i desno podstablo, sadrži i pokazivač na oca. Implementirati iterativnu funkciju FIND_BST čija povratna vrednost treba da bude pokazivač na koren onog podstabla koje predstavlja stablo binarne pretrage. Ukoliko postoji više ovakvih podstabala, treba vratiti pokazivač na koren onog podstabla sa maksimalnim brojem čvorova. Proveru da li je neko podstablo stablo binarne pretrage izdvojiti u posebnu funkciju. Obavezno kratko prokomentarisati rešenje.

Rešenje

Ovde nam je najpogodnije da postorder obilaskom određujemo da li su čvorovi binarna stabla pretraživanja, jer tako kad stignemo do viših čvorova već znamo da li su im deca ispravna binarna stabla pretraživanja. S tim u vidu, implementacija tražene funkcije za proveru izgleda ovako:

IS BST(node, left_max, right_min)
if left_max < key(node) < right_min then
    return true
end_if
return false

Kao pozivne argumente ove funkcije primamo najveći ključ iz levog podstabla i najmanji ključ iz desnog podstabla, što znači da bi trebalo da te podatke čuvamo u nekom redu kako bismo iz roditelja mogli da tim informacijama pristupimo. Obilazak kreće od reda listova i kreće se tako što svaki list gura svog roditelja u red, a duplikati roditelja se izbacuju iz reda prilikom njihovog obilaska.

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. zadatak

Postavka

Датотека:ASP2 K1 2018 zadatak 3 stablo.png

Crveno-crno stablo iz postavke zadatka.

Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 7 i 10.

4. zadatak

Postavka

Koristeći modifikovanu binarnu pretragu, napisati u pseudukodu iterativnu funkciju koja vraća poziciju prethodnika i sledbenika zadate vrednosti k u zadatom uređenom nizu arr. Vrednost k ne mora postojati u nizu.

Rešenje

Ovde se pretpostavlja da se ključevi u nizu ne mogu ponavljati.

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_if

5. zadatak

Postavka

Neka se u prazno AVL stablo redom ubacuju ključevi 12, 43, 23, 55, 72, 2, 60, 57, 89, a zatim se brišu ključevi 12, 23 i 57. Prilikom brisanja koristiti prethodnika. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju

Rešenje

Konačno stablo je:

     60
    /  \
  43    72
 /  \     \
2   55     89

Postupak možete simulirati u nekom od simulatora za AVL stabla.

6. zadatak

Postavka

Napisati u pseudokodu funkciju koja efikasno proverava da li je dato binarno stablo pretrage bst balansirano po AVL kriterijumu. Pored pokazivača na oca i levog i desnog sina, čvor stabla sadrži i podatke o visini levog i desnog podstabla.

Rešenje

Pošto ne moramo da izračunavamo visine podstabla, ovaj zadatak se svodi na posećivanje svih čvorova kako bismo uporedili sve visine levih i desnih podstabala u jednom čvoru. Ukoliko se u nekom razlikuju za više od 1, stablo nije balansirano po AVL kriterijumu.

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. zadatak

Postavka

Suboptimalno stablo binarnog pretraživanja

1. Objasniti algoritam za određivanje suboptimalnog stabla binarnog pretraživanja koji je zasnovan na težinama podstabala.
2. Ako su za n ključeva date verovatnoće uspešnog pretraživanja u nizu P, a neuspešnog u nizu Q, napisati efikasnu implementaciju funkcije koja nalazi samo koren tog stabla.

Rešenje

Određivanje suboptimalnog stabla binarnog pretraživanja zasnovanog na težinama podstabala, gde je težina podstabla koje uključuje čvorove na pozicijama od $i+1$ do $j$ u tabeli definisana kao $w_{ij} = q_i + p_{i+1} + q_{i+1} + ... + p_j + q_j$, se vrši tako što se prvo odredi ključ koji, kad postavljen za koren, daje najmanju razliku težina levog i desnog podstabla, a zatim se taj proces primeni rekurzivno na levo i desno podstablo (podniz) kako bi se i njihovi koreni odredili.

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_for

8. zadatak

Postavka

Neka se u samopodešavajuće stablo umeću redom ključevi 50, 70, 30, 60, 40, zatim se pretražuje na 70, pa se umeće 45 i, na kraju, pretražuje na 30. Prikazati izgled stabla nakon svake operacije.

Rešenje

Konačno stablo je:

30
  \
   40
     \
      45
        \
         60
        /  \
       50   70

Postupak možete simulirati u nekom od simulatora za samopodešavajuća stabla.