|
AVL strom AVL strom (pomenovaný podľa vynálezcov Adelson-Velsky and Landis) v informatike je údajová štruktúra, prvý vynájdený samovyvažovací binárny vyhľadávací strom. V AVL strome sa pre každý uzol rozdiel výšky dvoch podstromov detských uzlov líšia najviac o jednotku, preto je známy aj ako výškovo vyvážený. Hľadanie, vkladanie, a mazanie majú zložitosť 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áciami stromu. AVL strom je pomenovaný po jeho dvoch vynálezcoch, G. M. Adelson-Velskym a E. M. Landisovi, ktorí ho publikovali v ich dokumente z roku 1962 Algoritmus pre organizáciu informácií. Koeficient vyváženia uzla je výška jeho pravého podstromu mínus výška jeho ľavého podstromu. Uzol s koeficientom vyváženia 1, 0 alebo -1 sa považuje za vyvážený. Uzol s koeficientom vyváženia -2 alebo 2 sa považuje za nevyvážený a vyžaduje vyváženie stromu. Koeficient vyváženia sa buď ukladá priamo v každom uzle alebo sa počíta z výšiek podstromov, ktoré sú prípadne uložené v uzloch.  OperácieZákladné operácie nad AVL stromom zvyčajne vykonávajú rovnaké operácie ako by sa vykonali nad nevyváženým binárnym vyhľadávacím stromom, ale predchádza alebo nasleduje jedna z takzvaných "AVL rotácií". VkladanieVkladanie do AVL stromu je možné vykonať nasledovne: vložiť hodnotu do stromu ako keby bol nevyvážený binárny vyhľadávací strom, potom sa vrátiť ku koreňu a rotovať uzly, ktoré sa počas vkladania stali nevyváženými (pozri rotácia stromu). Keďže sa počas cesty späť ku koreňu prechádza najviac cez 1,44 x log n uzlov a každá AVL rotácia trvá konštantnú dobu, celý proces vkladania trvá O(log n). MazanieMazanie z AVL stromu je možné vykonať rotáciou uzla, ktorý má byť vymazaný dolu do listu a následne jeho priamym odseknutím. Keďže bude rotovaných najviac log n uzlov a každá AVL rotácia trvá konštantnú dobu, celý proces mazania trvá O(log n). VyhľadanieVyhľadanie v AVL strome sa vykonáva rovnako ako v nevyváženom binárnom vyhľadávacom strome a tak trvá O(log n), keďže AVL strom je vždy vyvážený. Netreba klásť žiadne zvláštne predpoklady a vyhľadávanie nemení štruktúru stromu (na rozdiel vyhľadávania v splay strome, ktoré mení jeho štruktúru). Pozri ajReferencie
Externé odkazyPo anglicky: |
Portal di Ensiklopedia Dunia
