APS Notes 2. Kolokvium

===Hash Tables===

-Struktura za cuvanje na elementi, koja ni ovozmozuva vmetnuvanje, brisenje i prebaruvanje vo O(1) vreme on average, a O(N) vo najlos slucaj.
-Moze da se implementira so niza i lista
-Odlucuvame da se implementira so niza zaradi indeksiranjeto, odnosno ni ovozmozuva random access
-Postojat 2 vida na hash tables:
	a. Closed buckets hash table
	b. Open buckets hash table

*Closed buckets hash table
	-Se implementira so niza i lista. Na sekoj index od nizata imame lista koja ni sluzi da gi smestuvame elementite ako ima kolizija vo istata koficka
	-Average complexity: O(1), worst complexity O(N)
	-Load factor: pretstavuva faktor na popolnetost, odnosno sredniot broj na elementi po koficka, N/M, t.e brojot na elementi podeleno so brojot na koficki.
				  Idealno ovoj faktor sakame da ni bide vo intervalot [0.5-0.75]. Pregolem load factor ni znaci premnogu elementi po koficka,
				  a premal load factor ni znaci deka imame premnogu neiskoristena memorija, odnosno wastame memory na masinata.
	=> Treba da izbereme optimalen broj na koficki i hash funkcija koja ce ni ovozmozi efikasno hashiranje za da imame dobar load factor.

*Open buckets hash table
	-Se implementira isklucivo so niza, imame pretekuvanje na koficki, odnosno ako imame kolizija, togas elementot se stava vo naredno slobodnata koficka.
	-Sostojbi na kofickite:
		a. Nikogas-zafatena - Nikogas nemala element, i momentalno e slobodna
		b. Zafatena - Momentalno ima element
		c. Prethodno-zafatena - Prethodno imala element, koj bil izbrisan i momentalno e slobodna

	-Vazni raboti za OBHT:
		*izbor na hash funkcija
		*izbor na broj na koficki
		*izbor na cekor
	-Cekorot mozeme isto taka da go presmetuvame spored daden kluc, pri sto ovaa postapka se narekuva dvojno heshiranje


===Trees===
-Drva(Opsto)
	*Ako eden jazel ima (vistinski) naslednik, toj se narekuva neterminalen(vnatresen) jazel
	*Ako eden jazel nema (vistinski) naslednici, toj se narekuva terminalen jazel ili list

	*Brojot na poddrva na eden jazel se narekuva stepen na jazelot
	*Stepen na edno drvo e maksimalniot stepen od stepenite na jazlite vo drvoto
	*Visina na jazel e dolzinata na najdolgata pateka od jazelot do listovite
	*Visina na drvo e visinata na korenot
	*Dlabocina na jazelot e dolzinata na edinstvenata pateka od korenot do jazelot
	*Dlabocina na drvoto e definirana so maksimalnata dlabocina na bilo koj jazel od drvoto
	*Nivoto na sekoj jazel e brojot na poddrva preku koi se doagja do nego, odnosno brojot na jazli koi treba da se pominat od korenot do jazelot(zemajki vo predvid deka nivoto na korenot e 0)

	*Mnozestvoto na razlicni (disjunktni) drva se narekuva shuma; Ako dodademe eden jazel i go povrzeme so korenite na drvata, edna suma prerasnuva vo drvo
	*Pateka od eden do drug jazel, niza od jazli
	*Dolzina na patekata pretstavuva brojot na vrski koi se pominuvaat za da se stigne od eden do drug jazel, odnosno dolzinata e za 1 pomala od brojot na jazli na patekata
	*Ako ima pateka od jazelot A do jazelot B, togas A e predok na B
	*Sekoj jazel e i predok i naslednik na samiot sebe; Vistinski naslednik, odnosno predok na jazelot A e sekoj jazel razlicen od A
	*Predci na eden jazol se site jazli dolz patekata od korenot do samiot jazel
	*Koga redosledot na jazli vo edno drvo e vazen, togas tie drva se narekuvaat podredeni drva
-Binarni drva
	*Binarno drvo e drvo vo koe sekoj jazel ima najmnogu 2 poddrva, odnosno e drvo so stepen 2
	*Celosno binarno drvo e binarno drvo cie neterminalni jazli sekogas imaat 2 naslednici

	*Izminuvanje na binarni drva:
		a. Preorder izminuvanje (Root - Left - Right)
		b. Inorder izminuvanje (Left - Root - Right)
		c. Postorder izminuvanje (Left - Right - Root)

	*Povrzani binarni drva
		-Ako e leva neiskoristena vrska togas niskata pokazuva kon prethodnikot vo soodnvetnata notacija
		-Ako e desna neiskoristena vrska togas niskata pokazuva kon sledbenikot vo soodnvetnata notacija
		-Binarnite drva mozat da bidat nanizani vo preorder, inorder ili postorder

===Prebaruvacki drva===

-Balansirani binarni drva
	*Balansirano binarno drvo e binarno drvo vo koe za sekoe poddrvo na proizvolen jazel vazi deka visinite ne se razlikuvaat za povekje od 1
-Heap Binarni drva
	*Pretstavuvaat kompletni binarni drva (se maksimalno popolneti ili ako ne se togas klucevite se na levata strana)
	*Max i min heap binary tree (max -> root e max i site se levo pa desno se po opagjacki redosled, min-> root e min, pa levo pa desn se po rastecki redosled)
	*Complexity for insertion in heap binary tree: O(logn)
	*Complexity of heap sort: O(nlogn)
-Binarni prebaruvacki drva
	*Binarni prebaruvacki drva se onie binarni drva kade klucevite vo levoto poddrvo na eden jazel se pomali od X, a vo desnoto poddrvo se > X
	*Najmaliot element se naogja vo listot do koj se doagja so patuvanje samo po levite vrski od korenot
	*Najgolemiot element se naogja vo listot do koj se doagja so patuvanje samo po desnite vrski od korenot
-AVL(Adelson-Velskii & Landis) drva
	*E binarno prebaruvacko drvo koe e isto taka i balansirano binarno drvo
	*Dlabocinata e od redot, t.e kompleksnosta e O(logn)
	*Se vrsi ednostavna rotacija dokolku dojde do narusuvanje na balansiranosta na AVL drvoto(levo ili desno)
	*Se vrsi dvojna rotacija dokolku ednostavnata ne pomaga vo balansiranjeto na AVL drvoto(levo-desno ili desno-levo)
B - drva
-B-drvo od m red(se misli so stepen m) e drvo so slednite karakteristiki:
	*Korenot e ili list ili ima pomegju 2 i m deca
	*Site vnatresni jazli(osven korenot) imaat pomegju [m/2] i m deca
	*Site listovi se na isto nivo