АСП2/К2 2017 - Историја измена

KockaBot: Замена начина истицања милокода.

2024-09-13T00:09:12Z

Замена начина истицања милокода.

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 25:		Ред 25:
	=== Rešenje ===		=== Rešenje ===
	Prvo pronalazimo list u koji umećemo, čuvajući indeks našeg podstabla u roditeljskom čvoru (<code>parent_index</code>) i bacajući grešku ukoliko naiđemo na postojeći ključ s istom vrednošću. Zatim formiramo stablo ukoliko roditeljski čvor ne postoji ili formiramo novi poredak ključeva u čvoru u pomoćnom nizu (<code>arr</code>) sa dovoljno alociranog mesta. Ako se radi o umetanju u pun čvor, u starom čvoru ostavljamo pola ključeva, alociramo novi čvor u koji ubacujemo drugo pola ključeva a najveći ključ ubacujemo u roditeljski čvor i ažuriramo pokazivače i ulančanu listu.		Prvo pronalazimo list u koji umećemo, čuvajući indeks našeg podstabla u roditeljskom čvoru (<code>parent_index</code>) i bacajući grešku ukoliko naiđemo na postojeći ključ s istom vrednošću. Zatim formiramo stablo ukoliko roditeljski čvor ne postoji ili formiramo novi poredak ključeva u čvoru u pomoćnom nizu (<code>arr</code>) sa dovoljno alociranog mesta. Ako se radi o umetanju u pun čvor, u starom čvoru ostavljamo pola ključeva, alociramo novi čvor u koji ubacujemo drugo pola ključeva a najveći ključ ubacujemo u roditeljski čvor i ažuriramo pokazivače i ulančanu listu.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	B PLUS INSERT(root, m, key)		B PLUS INSERT(root, m, key)
	new_key_index = ceil(m/2) + 1		new_key_index = ceil(m/2) + 1
Ред 83:		Ред 83:
	end_if		end_if
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 108:		Ред 108:
	=== Rešenje ===		=== Rešenje ===
	Odvajamo na slučajeve 2-čvora, 3-čvora i 4-čvora i rekurzivno transformišemo čvorove crveno-crnog stabla.		Odvajamo na slučajeve 2-čvora, 3-čvora i 4-čvora i rekurzivno transformišemo čvorove crveno-crnog stabla.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TRANSFORM(root)		TRANSFORM(root)
	if root = nil then		if root = nil then
Ред 140:		Ред 140:
	end_if		end_if
	return new_node		return new_node
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 148:		Ред 148:
	=== Rešenje ===		=== Rešenje ===
	Odvajamo rešenje na tri rekurzivne funkcije, traženu, funkciju za silazak niz stablo do čvora sa traženim prefiksom i funkciju za brisanje svih čvorova u podstablu.		Odvajamo rešenje na tri rekurzivne funkcije, traženu, funkciju za silazak niz stablo do čvora sa traženim prefiksom i funkciju za brisanje svih čvorova u podstablu.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DELETE KEYS(prefix)		DELETE KEYS(prefix)
	TRAVERSE(prefix, root, nil)		TRAVERSE(prefix, root, nil)
	</~~syntaxhighlight~~>		</nowiki>}}
	Funkcija za silazak niz stablo kao treći i četvrti argument prima pokazivače na bratski i/ili roditeljski čvor u kojima je potrebno ažurirati pokazivače na čvor koji se izbacuje.		Funkcija za silazak niz stablo kao treći i četvrti argument prima pokazivače na bratski i/ili roditeljski čvor u kojima je potrebno ažurirati pokazivače na čvor koji se izbacuje.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TRAVERSE(prefix, root, parent, sibling)		TRAVERSE(prefix, root, parent, sibling)
	if root = nil then		if root = nil then
Ред 173:		Ред 173:
	TRAVERSE(prefix, right(root), nil, root)		TRAVERSE(prefix, right(root), nil, root)
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DELETE(root)		DELETE(root)
	if root ≠ nil then		if root ≠ nil then
Ред 181:		Ред 181:
	FREENODE(root)		FREENODE(root)
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 206:		Ред 206:
	=== Rešenje ===		=== Rešenje ===
	Za osnovu u koju konvertujemo biramo 13, jer je uzajamno prosto sa 10.		Za osnovu u koju konvertujemo biramo 13, jer je uzajamno prosto sa 10.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	H(key)		H(key)
	q = 13		q = 13
Ред 218:		Ред 218:
	end_while		end_while
	return num % 100		return num % 100
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	EQUIV CLASS(K, n)		EQUIV CLASS(K, n)
	for i = 0 to 99 do		for i = 0 to 99 do
Ред 233:		Ред 233:
	end_for		end_for
	return num_classes		return num_classes
	</~~syntaxhighlight~~>		</nowiki>}}

	[[Категорија:АСП2]]		[[Категорија:АСП2]]
	[[Категорија:Рокови]]		[[Категорија:Рокови]]

KockaAdmiralac: SVG i konzistentno imenovanje

2022-02-13T20:33:44Z

SVG i konzistentno imenovanje

← Старија измена		Верзија на датум 13. фебруар 2022. у 22:33
Ред 9:		Ред 9:
	Ispod su data trie stabla nakon umetanja i nakon brisanja. Broj pristupa pri pretraživanju na ključ 35 je 3, pri pretraživanju na 128 i 125 je 4 a pri pretraživanju na 1236 je 5, tako da je prosečan broj pristupa pri uspešnom pretraživanju <math>\frac{3 + 4 + 4 + 5}{4} = 4</math>.		Ispod su data trie stabla nakon umetanja i nakon brisanja. Broj pristupa pri pretraživanju na ključ 35 je 3, pri pretraživanju na 128 i 125 je 4 a pri pretraživanju na 1236 je 5, tako da je prosečan broj pristupa pri uspešnom pretraživanju <math>\frac{3 + 4 + 4 + 5}{4} = 4</math>.
	<gallery>		<gallery>
	ASP2 K2 2017 1~~. zadatak~~ stablo umetanje.~~png~~ \| Trie stablo dobijeno nakon umetanja.		ASP2 K2 2017 zadatak 1 stablo umetanje.svg \| Trie stablo dobijeno nakon umetanja.
	ASP2 K2 2017 1~~. zadatak~~ stablo brisanje.~~png~~ \| Trie stablo dobijeno nakon brisanja.		ASP2 K2 2017 zadatak 1 stablo brisanje.svg \| Trie stablo dobijeno nakon brisanja.
	</gallery>		</gallery>

KockaAdmiralac: Ispravka geometrijske progresije (od `<@382584584572895234>`)

2021-01-28T15:12:05Z

Ispravka geometrijske progresije (od `<@382584584572895234>`)

← Старија измена		Верзија на датум 28. јануар 2021. у 17:12
Ред 193:		Ред 193:
	=== Rešenje ===		=== Rešenje ===
	<div class="abc-list">		<div class="abc-list">
	# Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa ''m-1'' ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina <math>h = \left\lceil\frac{n}{m-1}\right\rceil</math>. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se <math>m^h</math> čvorova, tako da za stablo visine <math>h</math> imamo da je ukupan broj čvorova <math>m^0 + m^1 + m^2 + ... + m^h = m^{h+1} - 1 = \left\lceil\frac{n}{m-1}\right\rceil</math>, iz čega dobijamo <math>h = \left\lceil\log_m\left(~~\frac{~~n~~}{m-1}~~ + 1\right)\right\rceil - 1</math>.		# Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa ''m-1'' ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina <math>h = \left\lceil\frac{n}{m-1}\right\rceil</math>. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se <math>m^h</math> čvorova, tako da za stablo visine <math>h</math> imamo da je ukupan broj čvorova <math>m^0 + m^1 + m^2 + ... + m^h = \frac{m^{h+1} - 1}{m-1} = \left\lceil\frac{n}{m-1}\right\rceil</math>, iz čega dobijamo <math>h = \left\lceil\log_m\left(n + 1\right)\right\rceil - 1</math>.
	# Broj ključeva potrebnih da bi se napravilo <math>m</math> čvorova je <math>2m-2</math>, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano <math>n</math> jednako <math>m \cdot \frac{n-1}{2m-2}</math>. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.		# Broj ključeva potrebnih da bi se napravilo <math>m</math> čvorova je <math>2m-2</math>, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano <math>n</math> jednako <math>m \cdot \frac{n-1}{2m-2}</math>. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.
	</div>		</div>

KockaAdmiralac: Sad je 13 zapravo izbačen

2021-01-24T16:57:17Z

Sad je 13 zapravo izbačen

← Старија измена		Верзија на датум 24. јануар 2021. у 18:57
Ред 97:		Ред 97:
	/ / \ \		/ / \ \
	[6 \|13\| \| ] [37\|54\| \| ] [60\|65\| \| ] [80\|85\|90\| ]		[6 \|13\| \| ] [37\|54\| \| ] [60\|65\| \| ] [80\|85\|90\| ]
	Zatim izbacujemo ključ 13. Dešava se spajanje tako što tretiramo 6~~, 13~~, 27, 37, 54, 57, 60, 65 kao sortiran niz, njegov srednji ključ šaljemo u koren, njegovu levu polovinu u levo dete a desnu u desno dete tog srednjeg ključa.		Zatim izbacujemo ključ 13. Dešava se spajanje tako što tretiramo 6, 27, 37, 54, 57, 60, 65 kao sortiran niz, njegov srednji ključ šaljemo u koren, njegovu levu polovinu u levo dete a desnu u desno dete tog srednjeg ključa.
	[37\|78\| \| ]		[54\|78\| \| ]
	/ / \		/ / \
	[6 \|13\|27\| ] [~~54\|~~57\|60\|65] [80\|85\|90\| ]		[6 \|27\|37\| ] [57\|60\|65\| ] [80\|85\|90\| ]

	== 5. zadatak ==		== 5. zadatak ==

KockaAdmiralac: Ispravka formule

2021-01-19T21:19:30Z

Ispravka formule

← Старија измена		Верзија на датум 19. јануар 2021. у 23:19
Ред 193:		Ред 193:
	=== Rešenje ===		=== Rešenje ===
	<div class="abc-list">		<div class="abc-list">
	# Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa ''m-1'' ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina <math>h = \left\lceil\frac{n}{m-1}\right\rceil</math>. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se <math>m^h</math> čvorova, tako da za stablo visine <math>h</math> imamo da je ukupan broj čvorova <math>m^0 + m^1 + m^2 + ... + m^h = m^{h+1} - 1 = \left\lceil\frac{n}{m-1}\right\rceil</math>, iz čega dobijamo <math>h = \left\lceil\log_m\left(\frac{n}{m-1}\right)\right\rceil + 1</math>.		# Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa ''m-1'' ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina <math>h = \left\lceil\frac{n}{m-1}\right\rceil</math>. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se <math>m^h</math> čvorova, tako da za stablo visine <math>h</math> imamo da je ukupan broj čvorova <math>m^0 + m^1 + m^2 + ... + m^h = m^{h+1} - 1 = \left\lceil\frac{n}{m-1}\right\rceil</math>, iz čega dobijamo <math>h = \left\lceil\log_m\left(\frac{n}{m-1} + 1\right)\right\rceil - 1</math>.
	# Broj ključeva potrebnih da bi se napravilo <math>m</math> čvorova je <math>2m-2</math>, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano <math>n</math> jednako <math>m \cdot \frac{n-1}{2m-2}</math>. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.		# Broj ključeva potrebnih da bi se napravilo <math>m</math> čvorova je <math>2m-2</math>, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano <math>n</math> jednako <math>m \cdot \frac{n-1}{2m-2}</math>. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.
	</div>		</div>

KockaAdmiralac: +{{tocright}}

2021-01-19T21:16:54Z

+{{tocright}}

← Старија измена		Верзија на датум 19. јануар 2021. у 23:16
Ред 1:		Ред 1:
			{{tocright}}
	[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1718.pdf Postavka zadataka na stranici predmeta.]		[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1718.pdf Postavka zadataka na stranici predmeta.]

KockaAdmiralac: Fali 2.

2021-01-19T21:12:45Z

Fali 2.

Нова страница

[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1718.pdf Postavka zadataka na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
U trie stablo umetnuti ključeve 35, 128, 1236, 1234 i 125, a zatim obrisati ključ 1234. Prikazati izgled stabla nakon poslednjeg umetanja i nakon brisanja. Izračunati prosečan broj pristupa pri uspešnoj pretrazi.

=== Rešenje ===
Ispod su data trie stabla nakon umetanja i nakon brisanja. Broj pristupa pri pretraživanju na ključ 35 je 3, pri pretraživanju na 128 i 125 je 4 a pri pretraživanju na 1236 je 5, tako da je prosečan broj pristupa pri uspešnom pretraživanju <math>\frac{3 + 4 + 4 + 5}{4} = 4</math>.
<gallery>
ASP2 K2 2017 1. zadatak stablo umetanje.png | Trie stablo dobijeno nakon umetanja.
ASP2 K2 2017 1. zadatak stablo brisanje.png | Trie stablo dobijeno nakon brisanja.
</gallery>

== 2. zadatak ==
=== Postavka ===
Neka se uz ključeve B stabla reda ''m'' čuva i broj pristupa podatku pridruženom tom čvoru. Ključevi čijim podacima se češće pristupa treba da se nađu što bliže korenu stabla. Objasniti kako bi trebalo modifikovati strukturu i operacije pretraživanja i brisanja da bi se to realizovalo.

=== Rešenje ===

== 3. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju za umetanje ključa u B+ stablo reda ''m'' na čiji koren ukazuje pokazivač ''root''. Pretpostaviti da otac lista u koji se vrši umetanje nije maksimalno popunjen. Smatrati da je struktura čvora fiksna i da čvor sadrži alociran prostor za maksimalan broj ključeva i pokazivača. Dodatno, svaki čvor sadrži pokazivač na oca i podatak o broju ključeva smeštenih u njemu.

=== Rešenje ===
Prvo pronalazimo list u koji umećemo, čuvajući indeks našeg podstabla u roditeljskom čvoru (<code>parent_index</code>) i bacajući grešku ukoliko naiđemo na postojeći ključ s istom vrednošću. Zatim formiramo stablo ukoliko roditeljski čvor ne postoji ili formiramo novi poredak ključeva u čvoru u pomoćnom nizu (<code>arr</code>) sa dovoljno alociranog mesta. Ako se radi o umetanju u pun čvor, u starom čvoru ostavljamo pola ključeva, alociramo novi čvor u koji ubacujemo drugo pola ključeva a najveći ključ ubacujemo u roditeljski čvor i ažuriramo pokazivače i ulančanu listu.
<syntaxhighlight lang="milo">
B PLUS INSERT(root, m, key)
new_key_index = ceil(m/2) + 1
p = root
prev = nil
while p ≠ nil do
for i = 1 to num(p) do
if keys(p)[i] = key then
ERROR(Key already inserted)
else if keys(p)[i] > key then
prev = p
p = pointers(p)[i-1]
parent_index = i-1
end_if
end_for
if i = num(p)+1 then
prev = p
p = pointers(p)[i-1]
parent_index = i-1
end_if
end_while
if prev = nil then
root = GETNODE
num(root) = 1
keys(root)[1] = key
else
inserted = false
for i = 1 to m do
if ((i = m) or (keys(prev)[i] = nil) or (keys(prev)[i] > key)) and (not inserted) then
inserted = true
arr[i] = key
end_if
end_for
if num(prev) = m-1 then
for i = 1 to new_key_index-1 do
keys(prev)[i] = arr[i]
end_for
new_node = GETNODE
num(new_node) = m + 1 - new_key_index
num(prev) = new_key_index-1
for i = new_key_index to m do
keys(new_node)[i-new_key_index+1] = arr[i]
end_for
for i = num(parent(prev)) downto parent_index do
pointers(parent(prev))[i+1] = pointers(parent(prev))[i]
keys(parent(parent))[i] = keys(parent(parent))[i-1]
end_for
keys(parent(prev))[parent_index+1] = keys(prev)[num(prev)]
pointers(parent(prev))[parent_index+1] = new_node
next(new_node) = next(prev)
next(prev) = new_node
else
for i = 1 to num(prev)+1 do
keys(prev)[i] = arr[i]
end_for
num(prev) = num(prev)+1
end_if
end_if
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Na primeru B* stabla reda 5 sa slike, prikazati i objasniti situaciju brisanja ključa kada dolazi do spajanja čvorova po sistemu „3-u-2“.
[13|54|78| ]
/ / \ \
[6 |9 | | ] [27|37| | ] [57|60|65| ] [80|85|90| ]

=== Rešenje ===
Iz datog primera nije moguće odmah izvršiti brisanje tako da se spoje čvorovi, tako da prvo brišemo ključ 9. Dešava se pozajmica od drugog desnog brata, tako da 13 silazi u čvor iz kojeg je izbačeno, 27 ide u koren, 54 silazi u čvor iz kojeg je izašlo 27 a 57 ide u koren.
[27|57|78| ]
/ / \ \
[6 |13| | ] [37|54| | ] [60|65| | ] [80|85|90| ]
Zatim izbacujemo ključ 13. Dešava se spajanje tako što tretiramo 6, 13, 27, 37, 54, 57, 60, 65 kao sortiran niz, njegov srednji ključ šaljemo u koren, njegovu levu polovinu u levo dete a desnu u desno dete tog srednjeg ključa.
[37|78| | ]
/ / \
[6 |13|27| ] [54|57|60|65] [80|85|90| ]

== 5. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju koja crveno-crno stablo, dato pokazivačem na koren ''root'', pretvara u 2-3-4 stablo i vraća pokazivač na njegov koren. Čvor crveno-crnog stabla sadrži informaciju o boji.

=== Rešenje ===
Odvajamo na slučajeve 2-čvora, 3-čvora i 4-čvora i rekurzivno transformišemo čvorove crveno-crnog stabla.
<syntaxhighlight lang="milo">
TRANSFORM(root)
if root = nil then
return nil
end_if
new_node = GETNODE
if (left(root) ≠ nil) and (red(left(root))) and (right(root) ≠ nil) and (red(right(root))) then
keys(new_node)[1] = key(left(root))
keys(new_node)[2] = key(root)
keys(new_node)[3] = key(right(root))
pointers(new_node)[0] = TRANSFORM(left(left(root)))
pointers(new_node)[1] = TRANSFORM(right(left(root)))
pointers(new_node)[2] = TRANSFORM(left(right(root)))
pointers(new_node)[3] = TRANSFORM(right(right(root)))
else if (left(root) ≠ nil) and (red(left(root))) then
keys(new_node)[1] = key(left(root))
keys(new_node)[2] = key(root)
pointers(new_node)[0] = TRANSFORM(left(left(root)))
pointers(new_node)[1] = TRANSFORM(right(left(root)))
pointers(new_node)[2] = TRANSFORM(right(root))
else if (right(root) ≠ nil) and (red(right(root))) then
keys(new_node)[2] = key(root)
keys(new_node)[3] = key(right(root))
pointers(new_node)[1] = TRANSFORM(left(root))
pointers(new_node)[2] = TRANSFORM(left(right(root)))
pointers(new_node)[3] = TRANSFORM(right(right(root)))
else
keys(new_node)[2] = key(root)
pointers(new_node)[1] = TRANSFORM(left(root))
pointers(new_node)[2] = TRANSFORM(right(root))
end_if
return new_node
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
U digitalnom stablu implementiranom po principu levi sin – desni brat smeštaju se ključevi sa alfa-numeričkim vrednostima. Implemetirati funkciju za uklanjanje svih ključeva koji počinju prefiksom koji je prosleđen kao parametar funkcije. Vrednosti znakova koji predstavljaju „braću“ u stablu uređene su rastuće prema leksikografskom poretku.

=== Rešenje ===
Odvajamo rešenje na tri rekurzivne funkcije, traženu, funkciju za silazak niz stablo do čvora sa traženim prefiksom i funkciju za brisanje svih čvorova u podstablu.
<syntaxhighlight lang="milo">
DELETE KEYS(prefix)
TRAVERSE(prefix, root, nil)
</syntaxhighlight>
Funkcija za silazak niz stablo kao treći i četvrti argument prima pokazivače na bratski i/ili roditeljski čvor u kojima je potrebno ažurirati pokazivače na čvor koji se izbacuje.
<syntaxhighlight lang="milo">
TRAVERSE(prefix, root, parent, sibling)
if root = nil then
return
end_if
len = STRING_LENGTH(prefix)
if (len = 1) and (prefix[0] = value(root)) then
if parent ≠ nil then
left(parent) = right(root)
end_if
if sibling ≠ nil then
right(sibling) = right(root)
end_if
DELETE(left(root))
FREENODE(root)
else if (len > 1) and (prefix[0] = value(root)) then
TRAVERSE(prefix+1, left(root), root, nil)
else
TRAVERSE(prefix, right(root), nil, root)
end_if
</syntaxhighlight>
<syntaxhighlight lang="milo">
DELETE(root)
if root ≠ nil then
DELETE(left(root))
DELETE(right(root))
FREENODE(root)
end_if
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Neka ''top-down'' stablo ''m''-arnog pretraživanja ima ''n'' ključeva:
<div class="abc-list">
# Izvesti i objasniti izraze za maksimalnu i minimalnu visinu ovog stabla.
# Koliko najmanje i koliko najviše čvorova može imati ovo stablo. Objasniti.
</div>

=== Rešenje ===
<div class="abc-list">
# Maksimalna visina ovakvog stabla se dobija kada napravimo degenerisano stablo umetanjem sortiranog niza ključeva u njega. Tom prilikom će svaki čvor biti popunjen sa ''m-1'' ključeva (osim možda čvora na poslednjem nivou) i na svakom nivou će biti po jedan čvor, čime se dobija visina <math>h = \left\lceil\frac{n}{m-1}\right\rceil</math>. Minimalna visina se dobija u skoro-kompletnom stablu. Na svakom nivou takvog stabla nalazi se <math>m^h</math> čvorova, tako da za stablo visine <math>h</math> imamo da je ukupan broj čvorova <math>m^0 + m^1 + m^2 + ... + m^h = m^{h+1} - 1 = \left\lceil\frac{n}{m-1}\right\rceil</math>, iz čega dobijamo <math>h = \left\lceil\log_m\left(\frac{n}{m-1}\right)\right\rceil + 1</math>.
# Broj ključeva potrebnih da bi se napravilo <math>m</math> čvorova je <math>2m-2</math>, tako što napunimo jedan čvor a zatim u njegovu decu stavimo po još jedan ključ (ne računajući jedan ključ koji iskoristimo da formiramo koren), tako da je najveći broj čvorova za fiksirano <math>n</math> jednako <math>m \cdot \frac{n-1}{2m-2}</math>. S druge strane, najmanji broj čvorova dobijamo kada popunimo svaki čvor do maksimuma, što je jednako maksimalnoj visini ovakvog stabla.
</div>

== 8. zadatak ==
=== Postavka ===
<div class="abc-list">
# Neka je dat neki celobrojni ključ ''key''. Interpretirati ga kao broj u dekadnom sistemu, a zatim napisati heš funkciju H(''key'') koja po metodu konverzije osnove hešira ključ u tabelu T od 100 ulaza.
# Ako ''n'' ključeva iz niza ''K'' treba da se mapira u heš tabelu gornjom funkcijom, napisati funkciju koja izračunava broj klasa ekvivalencije.
</div>

=== Rešenje ===
Za osnovu u koju konvertujemo biramo 13, jer je uzajamno prosto sa 10.
<syntaxhighlight lang="milo">
H(key)
q = 13
p = key
num = 0
exp = 1
while p > 0 do
num = num + (p % 10) * exp
p = p / 10
exp = exp * 13
end_while
return num % 100
</syntaxhighlight>
<syntaxhighlight lang="milo">
EQUIV CLASS(K, n)
for i = 0 to 99 do
arr[i] = false
end_for
num_classes = 0
for i = 1 to n do
k = H(K[i])
if (not arr[k]) then
num_classes = num_classes + 1
end_if
arr[k] = true
end_for
return num_classes
</syntaxhighlight>

[[Категорија:АСП2]]
[[Категорија:Рокови]]