- bud je implementovane v poli - vyhladavanie pulenim, sekvencne vyhladavanie
- alebo je implementovane v binarnom vyhladavacom strome
Sekvencne vyhladavanie - vyhladavanie v poli, prechadzanie polom prvok za prvkom a jedneho dna narazim na ten spravny prvok ..
- moze byt v
nezoradenom poli - v kazdom kroku sa pytame, ci sme nasli ten spravny prvok, ak ano, tak vyborne :)
- zlozitost je O(n) pre vsetko, okrem vlozenia
- vlozenie je O(1), pretoze tam ten prvok proste len niekam jebnem a nic ine ma nezaujima
nezoradenom poli so zarazkou - na koniec pola si dame hladany prvok/zarazku, cim zamedzime, aby sme prekrocili hranice pola a hladany prvok vzdy najdeme. Takto usetrime test na koniec pola, ale zlozitost bude stale rovnaka
vyhladavanie pulenim - jedna sa o binarne vyhladavanie, ktore vyuziva metodu rozpolovania intervalu. V takomto poli uz mame zoradene prvky. Vyhladavanie zahajime v polovicke pola a postupujeme vpravo/vlavo, podla toho, ako je pole zoradene. Postup vpravo/vlavo znamena rozdelenie zostavjucej casti pola na dve casti a znova - top-down approach command and conquer. Vyhladavanie takto limitujeme na O(log(n)) a minimum a maximum dokazeme urcit okamzite O(1)
dalsou moznostou asociativneho vyhladavania je Binary Search Tree
- usporiadany, korenovy, binarny strom
- lavy uzol je vzdy mensi ako koren, pravy je vacsi => vsetko vlavo je mensie ako koren a vsetko vpravo je vacise ako koren (alebo uzol, z ktoreho vetvime)
- pamatove zlozitost je O(n), vsetky ostatne su O(h) a h = log(n) u vyvazeneho stromu, n u nudle
- BVS preto vyvazujeme - idealny pripad je, ak pocet uzlov laveho podstromu je rovny poctu uzlov praveho podstromu - toto je prilis silnou podmienkou a preto uvazujeme slabsie podmienky. Vyvazuje sa podla
vysky - AVL strom
vysky a poctu potomkov - 1-2 stromy
vahy podstromu - vahovo vyvazene stromy
pri vyvazovani stromu vlastne rotujeme prvky => leva a prava rotace a levo-prave/pravo-lave rotacie
AVL strom
- vyskovo vyvazeny strom
- prazdny strom = -1
- neprazdny = 1 + vyska dlhsieho potomka
- k vyvazovaniu rotaciou pristupujeme az ked je nahodou uzol mimo <-1,1>
vahovo vyvazene stromy
- oznacene ako stromy s ohranicenym vyvazenim
- list - vaha 1/2
- inak w = (|Ul| + 1) / (|U| + 1), kde Ul je pocet uzlov vlavo a U je pocet uzlov podstromu (vcitane u)
- musime nejako urcit hranicu, ako ma byt strom vyvazeny a to je alfa <= w(u) <= 1-alfa a alfa sa zvacsa urcije ako 0 <= alfa <= 1/2. toto sa vola ohranicene vyvazovanie a strom je stromom s ohranicenym vyvazovanim
dalsim pripadom BVS je cerveno-cierny strom
- uzel je cerveny alebo cierny
- kazdy list je cierny
- ak je uzol cerveny, tak jeho potomkovia su cierny
- kazda jednoducha cesta z u do listu obsahuje rovnaky pocet ciernych uzlov
- koren je cierny
=> cierna vyska stromu, a to je pocet ciernych uzlov na ceste z u -> v (u sa nepocita, alebo je 0)
