АСП2/К1 2018
1. zadatak
Postavka
Optimalno stablo binarnog pretraživanja
- Navesti formulu za izračunavanje cene optimalnog stabla binarnog pretraživanja i objasniti je.
- Ukoliko se posmatraju tri ključa sa poznatim verovatnoćama uspešnog pretraživanja p1 = 0.2, p2 = 0.05, p3 = 0.1 i neuspešnog pretraživanja q0 = 0.15, q1 = 0.2, q2 = 0.1 i q3 = 0.2, odrediti i nacrtati optimalno stablo binarnog pretraživanja.
Rešenje
Formula je napisana i objašnjena u osmom zadatku na prvom kolokvijumu 2019. godine.
Postoji pet rasporeda ovih čvorova ( označavaju ključeve a eksterne čvorove stabla):
p1
/ \
q0 p2
/ \
q1 p3
/ \
q2 q3
p2
/ \
p1 p3
/ \ / \
q0 q1 q2 q3
p3
/ \
p2 q3
/ \
p1 q2
/ \
q0 q1
p1
/ \
q0 p3
/ \
p2 q3
/ \
q1 q2
p3
/ \
p1 q3
/ \
q0 p2
/ \
q1 q2
Ovim dobijamo da je optimalno stablo binarnog pretraživanja za ova tri ključa stablo u kojem je u korenu.
2. zadatak
Postavka
Napisati u pseudokodu efikasnu iterativnu implementaciju funkcije koja u stablu binarnog pretraživanja na čiji koren ukazuje pokazivač root pronalazi sledbenika čvora koji sadrži ključ key. U okviru čvora stabla ne postoji pokazivač na oca.
Rešenje
Ideja je da umesto inorder obilaska iskoristimo činjenicu da se sledbenik čvora sa ključem key može pronaći jednim spuštanjem niz stablo u pretrazi za ključem key. Postoje dva slučaja:
- kada čvor sa ključem key ima desno podstablo, znamo da se u njemu sigurno nalazi njegov sledbenik kao najlevlje dete desnog podstabla, i
- kada taj čvor nema desno podstablo, uzimamo poslednji čvor kod koga smo utvrdili da mu je ključ veći od ključa koji tražimo (poslednji čvor kod koga smo "otišli levo").
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. zadatak
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Postavka
Neka se posmatra crveno-crno stablo sa slike. Prikazati izgled stabla po koracima nakon umetanja ključeva 81 i 79 i uklanjanja ključa 23.
Rešenje
4. zadatak
Postavka
U stablu binarne pretrage greškom su dva čvora zamenila svoje pozicije. Implementirati funkciju CORRECT_BST koja ispravlja grešku i vraća ova dva čvora na svoje prave pozicije. Svaki čvor osim celobrojnog ključa i pokazivača na levo i desno podstablo sadrži i pokazivač na oca.
Rešenje
Pod zamenom čvorova se ne misli samo na zamenu ključeva u tim čvorovima već na zamenu zajedno sa podstablima, tako da jedna zamena ne može imati kaskadne posledice već će samo dva čvora ostati nekonzistentna.
Ideja je na stek guramo decu čvorova za koje odredimo da upadaju u granice pretrage po stablu binarnog pretraživanja, a ako ne upadaju smestimo ih u jednu od dve promenljive i nakon toga zamenimo, pazeći da zamenimo i pokazivače na roditelje i roditeljske pokazivače.
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. zadatak
Postavka
Neka se u prazno AVL stablo redom ubacuju ključevi 27, 12, 7, 34, 31, 5, 6, a zatim se brišu ključevi 31, 34, 12. Prilikom brisanja koristiti prethodnika. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.
Rešenje
Konačno stablo je:
7 / \ 6 27 / 5
Postupak možete simulirati u nekom od simulatora za AVL stabla.
6. zadatak
Postavka
Koristeći metodu binarne pretrage kao ideju, napisati u pseudokodu funkciju koja efikasno proverava da li je tačka T teme n-tougla M. Mnogougao M se zadaje pomoću niza tačaka – temena. Tačke su određene koordinatama x i y. Niz temena mnogougla je uređen rastuće po vrednosti koordinate x, pri čemu za istu vrednost koordinate x važi rastuća uređenost po vrednosti koordinate y.
Rešenje
Ovde se radi obična binarna pretraga s tim što se uslovi za odlazak ulevo ili udesno menjaju: ukoliko je x koordinata trenutne tačke veća od tražene, ili ukoliko su iste ali je y koordinata veća od tražene, ide se ulevo, a ukoliko je x koordinata trenutne tačke manja od tražene, ili ukoliko su iste ali je y koordinata manja od tražene, ide se udesno.
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
Postupak se mogao pojednostaviti ukoliko se pretpostavi da ne može postojati više od dve tačke sa istom x koordinatom, jer bi u tom slučaju te tačke bile kolinearne i ne bi mogle da budu temena n-tougla.
7. zadatak
Postavka
Dat je neuređeni niz A dužine n celobrojnih ključeva u opsegu vrednosti 1..100 koji se pretražuje i neuređeni niz ključeva K mnogo veće dužine m na koje se vrši pretraga. U nizu K ima veliki broj ponovljenih ključeva. Zbog neravnomerne verovatnoće pretrage ključeva, koristi se sledeća tehnika optimizacije. Nakon svakog uspešnog pretraživanja, vrši se prebacivanje za p pozicija unapred, gde je p broj uspešnih nalaženja tog ključa. Napisati u pseudokodu funkciju koja redom pretražuje niz A na ključeve iz niza K i vraća prosečan broj poređenja po nađenom ključu.
Rešenje
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. zadatak
Postavka
Obrazložiti da li je sledeća sekvenca ključeva validna u stablu binarnog pretraživanja:
- Ako se prilikom uspešnog pretraživanja u jednom stablu redom proveravaju ključevi 23, 87, 158, 348, 160, 200, 150, 158.
- Ako se prilikom neuspešnog pretraživanja u drugom stablu redom proveravaju ključevi 546, 453, 427, 68, 415, 231, 247, 417, 300.
Rešenje
Ovde gledamo naš silazak niz potencijalni BST i na osnovu prethodno pogledanih čvorova određujemo granice high i low u kojima se moraju nalaziti naredni ključevi kako bi stablo bilo validan BST. Dobijamo da oba slučaja nisu moguća u binarnom stablu pretraživanja.
-
- 23 → 87, low = 23, high = +∞
- 87 → 158, low = 87, high = +∞
- 158 → 348, low = 158, high = +∞
- 348 → 160, low = 158, high = 348
- 160 → 200, low = 160, high = 348
- 200 → 150, 150 < low => ⚡
-
- 546 → 453, low = -∞, high = 546
- 453 → 427, low = -∞, high = 453
- 427 → 68, low = -∞, high = 427
- 68 → 415, low = 68, high = 427
- 415 → 231, low = 68, high = 415
- 231 → 247, low = 231, high = 415
- 247 → 417, 417 > high => ⚡