АСП2/К1 2016
1. zadatak
Postavka
Ako je inorder obilaskom nekog stabla binarnog pretraživanja dobijen niz ključeva 1 5 8 9 11 14 prikazati tri moguća izgleda ovog stabla sa: (a) najmanjom visinom, (b) najvećom visinom i (c) visinom između najmanje i najveće. Obeležiti stablo sa najboljim i najlošijim performansama operacija.
Rešenje
Stablo A ima najbolje performanse operacija:
9 / \ 5 11 / \ \ 1 8 14
Stablo B ima najlošije performanse operacija:
1
\
5
\
8
\
9
\
11
\
14
Stablo C nema ni najbolje ni najlošije performanse operacija:
11
/ \
9 14
/
8
/
5
/
1
2. zadatak
Postavka
Dat je niz celih brojeva. Koristeći stablo binarnog pretraživanja, napisati funkciju koja menja svaki element njegovim sledbenikom. U slučaju da element nema sledbenika, zadržati originalnu vrednost. Rezultat funkcije je niz preuredjen na opisani način.
Rešenje
Ovde prvo prebacujemo zadati niz u binarno stablo pretraživanja koristeći funkciju za umetanje čvora a zatim za svaki element niza pronalazimo sledbenika slično kao u drugom zadatku sa prvog kolokvijuma 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. zadatak
Postavka
Neka je dat rastuće uređeni niz celih brojeva (npr., 1 2 3 5 7 9) ili neka njegova rotacija (npr., 5 7 9 1 2 3). Vrednosti se ne ponavljaju u nizu. Napisati u pseudokodu iterativnu funkciju koja na efikasan način pronalazi minimalnu vrednost u nizu.
Rešenje
Ovaj problem se svodi na binarnu pretragu sa izmenjenim uslovima: sada detektujemo da li se nalazimo levo ili desno od tražene vrednosti poredeći se sa prvim elementom (ukoliko je trenutni element veći od prvog, levo smo od tražene vrednosti) a detekciju tražene vrednosti tako što proverimo da li je element levo od trenutnog veći od njega (to znači da smo došli na početak nerotiranog niza).
FIND MIN(arr, n)
low = 1
high = n
if arr[1] ≤ arr[n] then
return arr[1]
end_if
while low ≤ high do
mid = (high + low) / 2
if arr[mid] < arr[mid-1] then
return arr[mid]
else if arr[mid] < arr[1] then
high = mid - 1
else
low = mid + 1
end_if
end_while
4. zadatak
Postavka
Binarno pretraživanje u povećanoj tabeli
- Objasniti na koji način se vrši umetanje i brisanje u povećanoj tabeli.
- Data je povećana tabela uređena neopadajuće i odgovarajući vektor sa bitovima validnosti. Na slici je prikazano trenutno stanje. Prikazati izgled povećane tabele i vektora validnosti nakon umetanja svakog od kljuceva: 6, 29 i 35, a zatim ukloniti ključeve : 18 i 23 i prikazati finalno stanje.
| 5 | 5 | 9 | 18 | 22 | 22 | 23 | 25 | 28 | 38 | 40 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
Rešenje
Umetanje se vrši tako što prvo uradimo (binarnu) pretragu za neki ključ i ako utvrdimo da postoji (da postoji ključ sa traženom vrednošću u tabeli i da mu je bit validnosti postavljen na 1) bacamo grešku, u suprotnom proveravamo bit validnosti na polju do kojeg smo došli: ako je 1, moramo pomeriti sve validne ključeve koji slede nakon tog polja za jedno mesto unapred kako bismo mogli da ubacimo ključ na to polje. Pri ubacivanju se bit validnosti tog ključa postavi na 1, svi sledeći nevalidni ključevi se postave na tu vrednost a svi prethodni na vrednost prethodnog validnog ključa.
Pri brisanju se nakon pretrage za dati ključ, bit validnosti ključa samo postavi na 0 ukoliko postoji ili baci greška ukoliko ne postoji.
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 28 | 38 | 40 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 25 | 29 | 38 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| Takođe je moguće da se, uz napomenu, pri nailasku na ključ veći od traženog gleda levo umesto desno. | ||||||||||
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 29 | 35 | 38 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Postoje dva načina na koji možemo da rešimo situaciju kad naiđemo na 38 i ne možemo da ga pomerimo udesno:
| ||||||||||
| 5 | 6 | 6 | 18 | 22 | 22 | 23 | 25 | 29 | 35 | 38 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
Brisanjem ključa 23 dešava se greška jer taj ključ ne postoji.
5. zadatak
Postavka
Dato je stablo binarnog pretraživanja. Da li stablo zadato na slici zadovoljava kriterijum AVL stabla? Ukoliko ne, izvršiti balansiranje stabla po AVL kriterijumu, a zatim iz dobijenog stabla obrisati ključeve 55 i 20, pa u stablo umetnuti ključ 30. Prilikom brisanja, koristiti sledbenika. Prikazati izgled stabla nakon svake izvršene izmene.
20
/ \
17 32
/ / \
10 25 33
/ / \ \
5 22 27 57
/ \
55 71
Rešenje
Vidimo da su kritični čvorovi ovde 17 i 33. Prvo radimo desnu rotaciju oko čvora 17:
20
/ \
10 32
/ \ / \
5 17 25 33
/ \ \
22 27 57
/ \
55 71
čime taj čvor više nije kritičan, ali zbog skraćivanja dužine levog podstabla čvor 20 postaje kritičan. Zatim radimo levu rotaciju oko čvora 33:
20
/ \
10 32
/ \ / \
5 17 25 57
/ \ / \
22 27 33 71
\
55
čime čvor 33 više nije kritičan. Na kraju, radimo levu rotaciju oko čvora 20:
32
/ \
20 57
/ \ / \
10 25 33 71
/ \ / \ \
5 17 22 27 55
Briše se čvor 55. Čvor je list tako da je brisanje trivijalno. Stablo ostaje balansirano nakon brisanja ovog čvora.
32
/ \
20 57
/ \ / \
10 25 33 71
/ \ / \
5 17 22 27
Brišemo čvor 20. Na njegovo mesto stavljamo njegovog sledbenika 22.
32
/ \
22 57
/ \ / \
10 25 33 71
/ \ \
5 17 27
Umećemo čvor 30 kao desnog sina 27.
32
/ \
22 57
/ \ / \
10 25 33 71
/ \ \
5 17 27
\
30
Njegovim umetanjem čvor 25 postaje kritičan pa zato radimo rotaciju ulevo oko njega i time dobijamo...
Konačno stablo:
32
/ \
22 57
/ \ / \
10 27 33 71
/ \ / \
5 17 25 30
6. zadatak
Postavka
U crveno-crnom stablu sa slike se najpre izvrši brisanje ključa 35, a zatim umetanje ključeva 9, 43, 10. Prikazati izgled stabla nakon svake od navedenih promena.
Rešenje
7. zadatak
Postavka
- U pseudokodu napisati funkciju koja za AVL stablo zadate visine h izračunava najmanji broj čvorova koje stablo može da sadrži.
- Na kojoj visini može da se nalazi list najbliži korenu?
- Kako se nazivaju ovakva stabla i po čemu su dobila ime?
Rešenje
- Pseudokod je dat ispod.
- ceil(h / 2). Ovo je zato što su podstabla Fibonačijevih stabala isto Fibonačijeva stabla, tako da se najmanja visina lista izračunava kao najmanja visina lista Fibonačijevog stabla čija je visina za 2 manja od trenutnog uvećana za 1.
- Ovakva stabla, koja su najgori slučajevi AVL stabala, dobila su ime po Fibonačijevim brojevima čija se rekurzivna definicija veoma malo razlikuje od rekurzivne definicije broja čvorova ovakvih stabala u zavisnosti od njihove visine.
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. zadatak
Postavka
Za stablo binarnog pretraživanja koje sadrži ključeve K1 < K2 < ... < Kn i čiji je koren ključ Kr izvesti vezu cene stabla i cena podstabla. Obavezno objasniti postupak.
Rešenje
Cena podstabla se definiše kao:
gde su verovatnoće uspešnog, neuspešnog pretraživanja a visine čvorova .
Uzimamo da su prvi čvor levog podstabla i poslednji čvor desnog podstabla trenutnog čvora po inorder poretku i a trenutni čvor . Pošto je visina u formuli za cene levog i desnog podstabla sada povećana za 1, dobijamo da je ukupna cena trenutnog čvora jednaka: