An AVL strom definované ako samovyvažovanie Rozdiel medzi výškami ľavého podstromu a pravého podstromu pre ľubovoľný uzol je známy ako faktor rovnováhy uzla.
Strom AVL je pomenovaný po svojich vynálezcoch Georgy Adelson-Velsky a Evgenii Landis, ktorí ho publikovali vo svojom článku z roku 1962 An algorithm for the organization of information.
Príklad AVL stromov:
AVL strom
Vyššie uvedený strom je AVL, pretože rozdiely medzi výškami ľavého a pravého podstromu pre každý uzol sú menšie alebo rovné 1.
Operácie na strome AVL:
Otáčanie podstromov v strome AVL:
Strom AVL sa môže otáčať jedným z nasledujúcich štyroch spôsobov, aby sa udržal v rovnováhe:
Ľavá rotácia :
Keď sa do pravého podstromu pravého podstromu pridá uzol, ak sa strom dostane z rovnováhy, vykonáme jedno otočenie doľava.
Otočenie doľava v strome AVL
Pravé otáčanie :
Ak sa do ľavého podstromu ľavého podstromu pridá uzol, strom AVL sa môže vyviesť z rovnováhy, vykonáme jedno otočenie doprava.
Pravá rotácia v strome AVL
Rotácia doľava-doprava :
Rotácia zľava doprava je kombinácia, v ktorej sa prvé otočenie zľava uskutoční po vykonaní rotácie doprava.
Otočenie zľava doprava v strome AVL
Pravo-ľavé otáčanie :
Pravo-ľavé otáčanie je kombinácia, v ktorej sa prvé otočenie doprava uskutoční po vykonaní otočenia doľava.
Otočenie doprava-doľava v strome AVL
Aplikácie AVL Tree:
- Používa sa na indexovanie obrovských záznamov v databáze a tiež na efektívne vyhľadávanie v nej.
- Pre všetky typy zbierok v pamäti vrátane sád a slovníkov sa používajú stromy AVL.
- Databázové aplikácie, kde sú vkladanie a mazanie menej bežné, ale je potrebné časté vyhľadávanie údajov
- Softvér, ktorý vyžaduje optimalizované vyhľadávanie.
- Používa sa v podnikových oblastiach a príbehových hrách.
Výhody AVL Tree:
- AVL stromy sa dokážu samy vyvážiť.
- Určite to nie je skreslené.
- Poskytuje rýchlejšie vyhľadávanie ako Red-Black Trees
- Lepšia časová zložitosť vyhľadávania v porovnaní s inými stromami, ako je binárny strom.
- Výška nemôže prekročiť log(N), kde N je celkový počet uzlov v strome.
Nevýhody AVL Tree:
- Je to náročné na realizáciu.
- Pre niektoré operácie má vysoké konštantné faktory.
- Menej používané v porovnaní s červeno-čiernymi stromami.
- Vďaka svojej pomerne prísnej rovnováhe poskytujú stromy AVL komplikované operácie vkladania a vyberania, pretože sa vykonáva viac rotácií.
- Vykonajte viac spracovania na vyváženie.
Súvisiace články:
- Úvod do binárnych vyhľadávacích stromov – Štruktúra údajov a návody na algoritmy
- Vloženie do stromu AVL
- Odstránenie v strome AVL
