AVL strom: Rozdiel medzi revíziami

Pridaných 77 bajtov ,  pred 2 mesiacmi
d
názov
d (linky)
d (názov)
 
[[Image:Unbalanced binary tree.svg|thumb|Príklad stromu, ktorý '''nie je AVL''']]
 
'''AVL strom''' (pomenovaný podľa vynálezcov '''A'''delson-'''V'''elsky and '''L'''andis) v [[informatika|informatike]] je [[údajová štruktúra]], prvý vynájdený [[samovyvažovací binárny vyhľadávací strom|samovyvažovací]] [[binárny vyhľadávací strom]]. V AVL strome sa pre každý uzol rozdiel výšky dvoch podstromov [[detský uzol|detských uzlov]] líšia najviac o jednotku, preto je známy aj ako [[výškovo vyvážený strom|výškovo vyvážený]]. Hľadanie, vkladanie, a mazanie majú [[výpočtová zložitosť|zložitosť]] [[Notácia veľké O|O]](log ''n'') v priemernom aj najhoršom prípade. Pridávanie a mazanie môže vyžadovať vyváženie stromu jednou alebo viacerými [[rotácia stromu|rotáciami stromu]].
 
AVL strom je pomenovaný po jeho dvoch vynálezcoch, [[Georgii Adelson-Velsky|G. M. Adelson-Velskym]] a [[Yevgeniy Landis|E. M. Landisovi]], ktorí ho publikovali v ich dokumente z roku [[1962]] ''Algoritmus pre organizáciu informácií''.
43 291

úprav