Úvod do stromu AVL v dátovej štruktúre
Strom AVL v dátovej štruktúre odkazuje na strom Adelson, Velski & Landis. Toto je vylepšená verzia stromu binárneho vyhľadávania. Má všetky vlastnosti ako v binárnom vyhľadávacom strome, ale líši sa iba tým, že zachováva rozdiel medzi výškou ľavého podpriemyslu a pravého podpriemyslu a tiež zaisťuje, že jeho hodnota je v strome <= 1, táto hodnota sa nazýva Zostatok. Factor.
Balance Factor = height(left-subtree) − height(right-subtree)
Napríklad: Zvážte nasledujúce stromy
Vo vyššie uvedenom príklade je výška pravého podre stromu = 2 a doľava = 3, takže BF = 2, čo je <= 1, sa teda považuje za vyvážený.
Prečo potrebujeme strom AVL v DS?
Pri práci so stromom binárneho vyhľadávania narazíme na scenár, v ktorom sú prvky usporiadané. V takých prípadoch sú všetky prvky poľa usporiadané na jednej strane koreňa, čo vedie k zvýšeniu časovej zložitosti prehľadávania prvku v poli a zložitosť sa stáva-O (n), tj najhoršia zložitosť stromu., Aby sa také problémy vyriešili a skrátil čas vyhľadávania, stromy AVL vynašli Adelson, Velski & Landis.
Príklad:
Na obrázku vyššie bola výška ľavého podstromu = 3
Výška pravého podstromu = 0
Balančný faktor = 3-0 = 3. Hľadanie prvku v takomto stromu má teda O (n) zložitosti, ktorá je podobná lineárnemu vyhľadávaniu. Aby sa predišlo zložitému vyhľadávaniu, bol zavedený strom AVL, v ktorom je potrebné udržiavať každý uzol v strome
vyrovnávací faktor <= 1, inak sa musia vykonať rôzne techniky rotácie na vyrovnanie takéhoto stromu.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Typy rotácií
Ak faktor vyváženia stromu nespĺňa podmienky <= 1, je potrebné vykonať na nich rotácie, aby sa z neho stal vyvážený strom.
Existujú 4 typy rotácie:
1. Rotácia doľava: Ak pridanie uzla napravo od stromu spôsobuje nerovnováhu, potom je potrebné vykonať rotáciu doľava.
2. Pravá rotácia: Ak pridanie uzla naľavo od stromu spôsobuje nerovnováhu uzla, musí sa vykonať pravá rotácia. Inými slovami, keď sa počet uzlov zvyšuje na ľavej strane, potom je potrebné posunúť prvky na pravú stranu, aby sa vyrovnali, takže sa hovorí, že ide o pravú rotáciu.
3. Rotácia zľava: Tento typ rotácie je kombináciou vyššie uvedených 2 rotácií. Tento typ rotácie nastane, keď je jeden prvok pridaný do pravého podstromu ľavého stromu.
V takom prípade najskôr vykonajte rotáciu vľavo na podstromu a potom pravú rotáciu ľavého stromu.
4. Rotácia doprava a doľava: Tento typ rotácie sa tiež skladá zo sekvencie nad 2 rotácie. Tento typ rotácie je potrebný, keď je prvok pridaný doľava od pravého podstromu a strom je nevyvážený. V takom prípade najprv urobíme pravú rotáciu na pravom podstrome a potom ľavú rotáciu na pravom strome.
Operácie na strome AVL v DS
Nižšie ako 3 operácie, ktoré možno vykonať na strome AVL: -
1. Vyhľadajte
Táto operácia je podobná ako pri vyhľadávaní v binárnom vyhľadávacom strome. Nasledujú nasledujúce kroky:
- Prečítajte si prvok poskytnutý používateľom vyslovte x.
- Porovnajte prvok z koreňa, ak je rovnaký, potom ukončite inak prejdite na ďalší krok.
- Ak x
Inak choďte na to pravé dieťa a porovnajte znova.
Postupujte podľa procesov B a C, kým nenájdete element a neskončíte.
Tento proces má zložitosť O (log n).
Príklad:
 | Zoberme si tento strom, kde musíme vykonať vyhľadávanie hodnoty uzla 9. Najprv nechajte x = 9, koreňová hodnota (12)> x, potom musí byť táto hodnota v ľavej podstrome koreňového prvku. |
 | Teraz je x porovnané s hodnotou uzla 3 x> 3, preto musíme pristúpiť k správnemu podstromu. |
 | Teraz je x porovnané s uzlom (9), kde 9 == 9 vráti true. Vyhľadávanie prvkov sa teda v strome dokončí. |
2. Vloženie
Pri vkladaní prvku do stromu AVL musíme nájsť umiestnenie konkrétneho prvku, ktorý treba vložiť, a potom sa prvok pripojí rovnako ako vloženie do BST, ale potom sa skontroluje, či je strom stále vyvážený alebo nie. tj vyrovnávací faktor uzla je <= 1. Konkrétne rotácie sa vykonávajú podľa potreby.
Zložitosť je O (log n).
Príklad: Zvážte strom uvedený nižšie,
 | Každý uzol má vyrovnávací faktor ako 0, -1 alebo 1, takže strom je vyrovnaný. Teraz povieme, čo sa stane, keď sa vloží uzol s hodnotou 1. Prvý strom prechádza, aby našiel miesto, kam ho treba vložiť … 1 <2 je teda zapísané ako ľavé dieťa uzla (2). |
 | Po vložení sa uzol (9) stane nevyváženým s faktorom vyváženia = 2. Teraz je podrobený pravému otočeniu. |
 | Strom sa stane rovnováhou po otočení doprava a operácia vkladania je úspešne dokončená. |
3. Vymazanie
Vymazanie prvku v strome AVL zahŕňa aj vyhľadanie prvku v strome a jeho vymazanie. Vyhľadávacia operácia je rovnaká ako pri BST a po nájdení prvku, ktorý sa má odstrániť, sa zo stromu odstráni prvok a prvky sa upravia tak, aby sa znova stal BST. Potom, čo sa tieto prvky skontrolujú, aby mali vyvážený faktor 0, -1 alebo 1, a teda sa vykonajú vhodné rotácie, aby sa dosiahol vyváženie.
Zložitosť, ak O (log n).
 | Zoberme si daný strom, ktorého všetky majú koeficient vyváženia 0, -1 alebo 1. Teraz odstránime uzol s hodnotou 16. Prvý strom prechádza, aby našiel uzol s hodnotou 16 rovnakou ako vyhľadávací algoritmus. |
 | Uzol 16 bude nahradený inorder predchodcom tohto uzla, ktorý je najväčším prvkom z ľavého podstromu, tj 12 Strom je nevyvážený, preto je potrebné vykonať rotáciu LL. |
 | Teraz sa každý uzol vyrovnal. |
Záver - strom AVL v dátovej štruktúre
Strom AVL je potomkom Binárneho vyhľadávacieho stromu, ale v prípade triedenia prvkov prekonáva jeho nevýhodu zvyšujúcej sa zložitosti. Monitoruje vyvažovací faktor stromu na 0 alebo 1 alebo -1. V prípade, že sa strom stane nevyváženým, vykonajú sa príslušné rotačné techniky na vyváženie stromu.
Odporúčané články
Toto je sprievodca stromom AVL v dátovej štruktúre. Tu diskutujeme úvod, operácie na AVL strome v DS a typy rotácií. Viac informácií nájdete aj v ďalších súvisiacich článkoch -
- jQuery Elements
- Čo je to Data Science
- Typy stromov v dátovej štruktúre
- C # Typy údajov