АСП2/Проширена табела - Историја измена

TopOfKeks: kategorizacija

2021-10-31T22:44:52Z

kategorizacija

← Старија измена		Верзија на датум 1. новембар 2021. у 00:44
Ред 35:		Ред 35:

	[[Категорија:АСП2]]		[[Категорија:АСП2]]
			[[Категорија:Водичи]]

KockaAdmiralac: +napomena za ažuriranje i u slučaju da je moralo da se radi pomeranje

2020-11-03T02:24:51Z

+napomena za ažuriranje i u slučaju da je moralo da se radi pomeranje

← Старија измена		Верзија на датум 3. новембар 2020. у 04:24
Ред 26:		Ред 26:
	*# umetanje čvora na sredinu intervala do kojeg se došlo, kako bi se umanjila potreba za pomeranjem ključeva u budućnosti (preporučeno).		*# umetanje čvora na sredinu intervala do kojeg se došlo, kako bi se umanjila potreba za pomeranjem ključeva u budućnosti (preporučeno).
	* Nakon uspešnog određivanja mesta za umetanje ključa, potrebno je postaviti bit validnosti tog ključa na 1, sve prividne ključeve koji slede tom ključu postaviti na vrednost tog ključa i sve prividne ključeve koji prethode tom ključu postaviti na vrednost prethodnog validnog ključa. Ukoliko prethodni validan ključ ne postoji, ne raditi ništa.<ref>Po rečima Milice Despotović. Ukoliko ovo bude pravilo problem prilikom primene preporučenog pristupa za umetanje čvora kada se prilikom pretrage naiđe na prividan čvor, iskoristiti drugi pristup.</ref>		* Nakon uspešnog određivanja mesta za umetanje ključa, potrebno je postaviti bit validnosti tog ključa na 1, sve prividne ključeve koji slede tom ključu postaviti na vrednost tog ključa i sve prividne ključeve koji prethode tom ključu postaviti na vrednost prethodnog validnog ključa. Ukoliko prethodni validan ključ ne postoji, ne raditi ništa.<ref>Po rečima Milice Despotović. Ukoliko ovo bude pravilo problem prilikom primene preporučenog pristupa za umetanje čvora kada se prilikom pretrage naiđe na prividan čvor, iskoristiti drugi pristup.</ref>
			** U knjizi ne piše da se tabela na ovaj način ažurira i ukoliko se nakon neuspešne pretrage završilo na validnom ključu. Pri odluci oko primenjivanja procedure iznad u tom slučaju obavezno napomenuti interpretaciju tog dela knjige.

	== Brisanje ==		== Brisanje ==

KockaAdmiralac: Kategorizacija

2020-11-03T01:37:32Z

Kategorizacija

← Старија измена		Верзија на датум 3. новембар 2020. у 03:37
Ред 32:		Ред 32:
	== Fusnote ==		== Fusnote ==
	<references />		<references />

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

KockaAdmiralac: KockaAdmiralac преместио је страницу „Корисник:KockaAdmiralac/Tabela” на „АСП2/Проширена табела” без остављања преусмерења: Izgleda je dovoljno korisna za ovo

2020-11-03T01:34:24Z

KockaAdmiralac преместио је страницу „Корисник:KockaAdmiralac/Tabela” на „АСП2/Проширена табела” без остављања преусмерења: Izgleda je dovoljno korisna za ovo

← Старија измена	Верзија на датум 3. новембар 2020. у 03:34
(нема разлике)

KockaAdmiralac: nije -> jeste

2020-11-03T01:28:22Z

nije -> jeste

← Старија измена		Верзија на датум 3. новембар 2020. у 03:28
Ред 15:		Ред 15:
	Pri umetanju se vrši algoritam poput onog za pretragu, s tim što se pri uspešnoj pretrazi baca greška jer ključ već postoji u tabeli. Na mestu gde se stalo s neuspešnom pretragom se počinje sa umetanjem.		Pri umetanju se vrši algoritam poput onog za pretragu, s tim što se pri uspešnoj pretrazi baca greška jer ključ već postoji u tabeli. Na mestu gde se stalo s neuspešnom pretragom se počinje sa umetanjem.
	* Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 1, proverava se da li je ključ na kojem se završilo manji ili veći od ključa koji se umeće:		* Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 1, proverava se da li je ključ na kojem se završilo manji ili veći od ključa koji se umeće:
	*# Ukoliko je manji, proverava se da li je sledeći čvor validan. Ukoliko nije validan, umetanje se izvršava na tom mestu, a ukoliko ~~nije~~ taj ključ i svi naredni validni ključevi se pomeraju za jedno mesto udesno.		*# Ukoliko je manji, proverava se da li je sledeći čvor validan. Ukoliko nije validan, umetanje se izvršava na tom mestu, a ukoliko jeste taj ključ i svi naredni validni ključevi se pomeraju za jedno mesto udesno.
	*# Ukoliko je veći, postoje dva moguća pristupa, i oba bi trebalo napomenuti ukoliko se primenjuju:		*# Ukoliko je veći, postoje dva moguća pristupa, i oba bi trebalo napomenuti ukoliko se primenjuju:
	*## pomeriti taj i sve naredne validne ključeve za jedno mesto udesno, ili		*## pomeriti taj i sve naredne validne ključeve za jedno mesto udesno, ili

KockaAdmiralac: To je valjda to

2020-11-03T01:12:36Z

To je valjda to

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

{{tocright}}
Proširena tabela,<ref>U originalu: povećana tabela.</ref> jedan od najbeskorisnijih izuma čovečanstva i jedan od čestih zadataka na kolokvijumima iz [[АСП2|Algoritama i struktura podataka 2]], prvi put je formalno definisana na strani 218 knjige "Algoritmi i strukture podataka" Mila V. Tomaševića kao struktura koju je pogodno koristiti "kada je maksimalni broj ključeva u tabeli poznat". Ideja povećane tabele jeste uvođenje niza bitova pored sortiranog niza koji govore da li je ključ na nekoj poziciji u tom nizu validan, tj. da li on zapravo postoji u tom nizu ili je samo prividan ključ proširene tabele.

Nažalost, profesorima i saradnicima na predmetu je trebalo nekoliko godina da se dogovore oko toga kako se vrše operacije nad ovom tabelom, i na ovoj strani se skupljaju dosadašnji zaključci o načinu njihove upotrebe kako bi se na kolokvijumima i integralnim ispitima ostvario maksimum bodova na ovim zadacima.

== Pretraga ==
Pretraga u proširenoj tabeli se vrši kao binarna pretraga, s tim što ukoliko se naiđe na ključ čiji je bit validnosti 0 moraju se proveriti (način provere nije određen) prethodni (algoritam za umetanje nam garantuje da će samo prvi ključ u sekvenci istih ključeva biti validan) ključevi sa tom vrednošću, ako se nađe jedan sa bitom validnosti 1 pretraga je uspešna, u suprotnom je pretraga neuspešna.

Važno je napomenuti da binarna pretraga '''ne sme da se radi odokativno'''.
# Mora se vršiti po algoritmu iz knjige. Ukoliko se ne vrši po algoritmu iz knjige, preporučuje se ispisivanje algoritma binarne pretrage po kojem se ta pretraga vrši.
# Pošto indeksiranje ključeva može da izmeni krajnji ključ do kojeg se dolazi, bitno je na barem jednoj tabeli naznačiti da li se ključevi indeksiraju od 0 ili od 1.
# Pri deljenju neparnog broja sa 2 u binarnoj pretrazi moguće je zaokružiti ili na niži ili na viši broj, sa napomenom na koji se broj zaokružuje. Nikako nije dozvoljeno zaokruživati čas na niži a čas na viši broj.

== Umetanje ==
Pri umetanju se vrši algoritam poput onog za pretragu, s tim što se pri uspešnoj pretrazi baca greška jer ključ već postoji u tabeli. Na mestu gde se stalo s neuspešnom pretragom se počinje sa umetanjem.
* Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 1, proverava se da li je ključ na kojem se završilo manji ili veći od ključa koji se umeće:
*# Ukoliko je manji, proverava se da li je sledeći čvor validan. Ukoliko nije validan, umetanje se izvršava na tom mestu, a ukoliko nije taj ključ i svi naredni validni ključevi se pomeraju za jedno mesto udesno.
*# Ukoliko je veći, postoje dva moguća pristupa, i oba bi trebalo napomenuti ukoliko se primenjuju:
*## pomeriti taj i sve naredne validne ključeve za jedno mesto udesno, ili
*## pogledati da li levo od trenutnog polja postoji ključ koji nije validan i na tom mestu postaviti ključ. Ukoliko ovo nije moguće, preporučuje se konzistentno primenjivanje prvog pristupa.
* Ukoliko pomeranje čvorova za jedno mesto udesno nije moguće, ponovo su dostupna dva pristupa koja je potrebno napomenuti pri primeni:
*# bacanje greške (čvor se neće umetnuti u tabelu uopšte), ili
*# pomeranje čvorova koji su potrebni za oslobađanje mesta za novi čvor ulevo (preporučeno).
* Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 0, opet postoje dva pristupa umetanju u ovom slučaju:
*# umetanje čvora na mesto do kojeg se došlo, ili
*# umetanje čvora na sredinu intervala do kojeg se došlo, kako bi se umanjila potreba za pomeranjem ključeva u budućnosti (preporučeno).
* Nakon uspešnog određivanja mesta za umetanje ključa, potrebno je postaviti bit validnosti tog ključa na 1, sve prividne ključeve koji slede tom ključu postaviti na vrednost tog ključa i sve prividne ključeve koji prethode tom ključu postaviti na vrednost prethodnog validnog ključa. Ukoliko prethodni validan ključ ne postoji, ne raditi ništa.<ref>Po rečima Milice Despotović. Ukoliko ovo bude pravilo problem prilikom primene preporučenog pristupa za umetanje čvora kada se prilikom pretrage naiđe na prividan čvor, iskoristiti drugi pristup.</ref>

== Brisanje ==
Brisanje je jedina jednostavna operacija sa ovom tabelom. Prilikom brisanja, prvo proveriti da li ključ postoji u tabeli i da li mu je bit validnosti postavljen na 1. Ako postoji i jeste postavljen, postaviti bit validnosti na 0, u suprotnom baciti grešku.

== Fusnote ==
<references />