# AVL strom

### Z Wikipédie

Príklad stromu, ktorý nie je AVL

AVL strom 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.

Rovnaký strom po výškovom vyvážení

## [úprava] Operácie

Zá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í".

### [úprava] Vkladanie

Vkladanie 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 vá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 krát lg n uzlov a každá AVL rotácia trvá konštantnú dobu, celý proces vkladania trvá O(log n).

### [úprava] Mazanie

Mazanie 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 lg n uzlov a každá AVL rotácia trvá konštantnú dobu, celý proces mazania trvá O(log n).

### [úprava] Vyhľadanie

Vyhľ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).

## [úprava] Pozri aj

- Rotácia stromu
- Splay strom
- Červeno-čierny strom
- B-strom

## [úprava] Referencie

- G. Adelson-Velskii a E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962 (po rusky). Anglický preklad Myron J. Ricci v Soviet Math. Doklady, 3:1259–1263, 1962.
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, tretie vydanie. Addison-Wesley, 1997. ISBN 0-201-89685-0. Str. 458–475 kapitoly 6.2.3: Balanced Trees. Knuth nazýva AVL stromy jednoducho "vyvážené stromy".

## [úprava] Externé odkazy

Po slovensky:

- AVL strom (PDF) na stránke predmetu Údajové štruktúry
- Prednášky z ÚŠ KZVI UK

Po anglicky:

- Description from the Dictionary of Algorithms and Data Structures
- AVL Tree Traversal
- Linked AVL tree
- C++ AVL Tree Template and C AVL TREE "Generic Package" by Walt Karas
- A Visual Basic AVL Tree Container Class by Jim Harris
- AVL Trees: Tutorial and C++ Implementation by Brad Appleton
- Ulm's Oberon Library: AVLTrees
- The AVL TREE Data Type
- CNAVLTree Class Reference
- GNU libavl
- AVL-trees - balanced binary trees by Alex Konshin
- Simulation of AVL Trees
- AVL tree applet
- Simulation of AVL Trees (DYNAMIC)
- AVL, Splay and Red/Black Applet

Zdroj: "http://sk.wikipedia.org../../../a/v/l/AVL_strom_a9e5.html"

Kategórie: Údajové štruktúry | Stromy (štruktúra)

##### Views

- Stránka
- Diskusia
- Aktuálna verzia

##### Hľadaj

##### Iné jazyky

- Česky
- Dansk
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- Lietuvių
- Polski
- Português
- Русский
- Slovenščina
- Svenska
- 中文