Strom AVL vynašli GM Adelson - Velsky a EM Landis v roku 1962. Strom je pomenovaný AVL na počesť jeho vynálezcov.
AVL strom možno definovať ako výškovo vyvážený binárny vyhľadávací strom, v ktorom je každý uzol spojený s faktorom rovnováhy, ktorý sa vypočíta odpočítaním výšky jeho pravého podstromu od výšky jeho ľavého podstromu.
návratový typ v jazyku Java
O strome sa hovorí, že je vyvážený, ak je faktor rovnováhy každého uzla v rozmedzí -1 až 1, inak bude strom nevyvážený a bude potrebné ho vyvážiť.
Faktor vyváženia (k) = výška (vľavo (k)) - výška (vpravo (k))
Ak je koeficient rovnováhy ktoréhokoľvek uzla 1, znamená to, že ľavý podstrom je o jednu úroveň vyššie ako pravý podstrom.
Ak je koeficient vyváženia ktoréhokoľvek uzla 0, znamená to, že ľavý podstrom a pravý podstrom majú rovnakú výšku.
Ak je koeficient rovnováhy ktoréhokoľvek uzla -1, znamená to, že ľavý podstrom je o úroveň nižšie ako pravý podstrom.
AVL strom je uvedený na nasledujúcom obrázku. Vidíme, že faktor rovnováhy spojený s každým uzlom je medzi -1 a +1. preto je to príklad stromu AVL.
Zložitosť
| Algoritmus | Priemerný prípad | V najhoršom prípade |
|---|---|---|
| Priestor | o (n) | o (n) |
| Vyhľadávanie | o (log n) | o (log n) |
| Vložiť | o (log n) | o (log n) |
| Odstrániť | o (log n) | o (log n) |
Operácie na strome AVL
Vzhľadom na skutočnosť, že strom AVL je tiež binárny vyhľadávací strom, preto sa všetky operácie vykonávajú rovnakým spôsobom, ako sa vykonávajú v binárnom vyhľadávacom strome. Vyhľadávanie a prechádzanie nevedie k narušeniu vlastníctva stromu AVL. Vkladanie a odstraňovanie sú však operácie, ktoré môžu túto vlastnosť narušiť, a preto je potrebné ich prehodnotiť.
| SN | Prevádzka | Popis |
|---|---|---|
| 1 | Vkladanie | Vkladanie do stromu AVL sa vykonáva rovnakým spôsobom, ako sa vykonáva v strome binárneho vyhľadávania. Môže to však viesť k porušeniu vlastnosti stromu AVL, a preto môže byť potrebné strom vyvážiť. Strom môže byť vyvážený použitím rotácií. |
| 2 | Vymazanie | Vymazanie môže byť tiež vykonané rovnakým spôsobom, ako sa vykonáva v binárnom vyhľadávacom strome. Vymazanie môže tiež narušiť rovnováhu stromu, preto sa na opätovné vyváženie stromu používajú rôzne typy rotácií. |
Prečo AVL Tree?
AVL strom riadi výšku binárneho vyhľadávacieho stromu tým, že ho nenechá zošikmiť. Čas potrebný na všetky operácie v binárnom vyhľadávacom strome s výškou h je O(h) . Dá sa však rozšíriť na O(n) ak sa BST stane skresleným (t. j. najhorší prípad). Obmedzením tejto výšky na log n strom AVL uvalí na každú operáciu hornú hranicu O (log n) kde n je počet uzlov.
AVL rotácie
Rotáciu v AVL strome vykonávame iba v prípade, ak je Balance Factor iný ako -1, 0 a 1 . V zásade existujú štyri typy rotácií, ktoré sú nasledovné:
- L L rotácia: Vložený uzol je v ľavom podstrome ľavého podstromu A
- R R rotácia: Vložený uzol je v pravom podstrome pravého podstromu A
- Rotácia L R: Vložený uzol je v pravom podstrome ľavého podstromu A
- R L rotácia: Vložený uzol je v ľavom podstrome pravého podstromu A
Kde uzol A je uzol, ktorého súčiniteľ rovnováhy je iný ako -1, 0, 1.
Prvé dve rotácie LL a RR sú jednoduché rotácie a ďalšie dve rotácie LR a RL sú dvojité rotácie. Aby bol strom nevyvážený, minimálna výška musí byť aspoň 2. Pochopme každé otočenie
1. Rotácia RR
Keď sa BST stane nevyváženým, pretože uzol je vložený do pravého podstromu pravého podstromu A, potom vykonáme rotáciu RR, rotácia RR je rotácia proti smeru hodinových ručičiek, ktorá sa aplikuje na hranu pod uzlom s faktorom rovnováhy -2
Vo vyššie uvedenom príklade má uzol A faktor rovnováhy -2, pretože uzol C je vložený do pravého podstromu A pravého podstromu. Rotáciu RR vykonávame na okraji pod A.
2. Rotácia LL
Keď sa BST stane nevyváženým, v dôsledku vloženia uzla do ľavého podstromu ľavého podstromu C, potom vykonáme rotáciu LL, rotácia LL je rotácia v smere hodinových ručičiek, ktorá sa aplikuje na hranu pod uzlom s faktorom rovnováhy 2.
Vo vyššie uvedenom príklade má uzol C faktor rovnováhy 2, pretože uzol A je vložený do ľavého podstromu ľavého podstromu C. Rotáciu LL vykonávame na okraji pod A.
3. Rotácia LR
Dvojité otáčanie je o niečo tvrdšie ako jednoduché otáčanie, ktoré už bolo vysvetlené vyššie. LR rotácia = RR rotácia + LL rotácia, t.j. najprv sa vykoná rotácia RR na podstrome a potom sa rotácia LL vykoná na plnom strome, pod úplným stromom rozumieme prvý uzol z dráhy vloženého uzla, ktorého koeficient vyváženia je iný ako -1 , 0 alebo 1.
Pochopme každý jeden krok veľmi jasne:
| Štát | Akcia |
|---|---|
 | Uzol B bol vložený do pravého podstromu A ľavého podstromu C, vďaka čomu sa C stal nevyváženým uzlom s faktorom rovnováhy 2. V tomto prípade ide o rotáciu L R, kde: Vložený uzol je v pravom podstrome ľavého podstromu stromu C |
 | Keďže rotácia LR = rotácia RR + LL, preto sa najskôr vykoná RR (proti smeru hodinových ručičiek) na podstrome s koreňom v A. Tým, že urobíte RR rotáciu, uzol A , sa stal ľavým podstromom B . |
 | Po vykonaní rotácie RR je uzol C stále nevyvážený, t. j. má vyvážený faktor 2, keďže vložený uzol A je vľavo od C |
 | Teraz vykonáme LL rotáciu v smere hodinových ručičiek na plnom strome, teda na uzle C. uzol C sa teraz stal pravým podstromom uzla B, A je ľavým podstromom B |
 | Faktor rovnováhy každého uzla je teraz buď -1, 0 alebo 1, t. j. BST je teraz vyvážený. |
4. Rotácia RL
Ako už bolo uvedené, dvojité otáčanie je o niečo tvrdšie ako jednoduché otáčanie, ktoré už bolo vysvetlené vyššie. R L rotácia = LL rotácia + RR rotácia, t.j. najprv sa vykoná rotácia LL na podstrome a potom rotácia RR na celom strome, pod úplným stromom rozumieme prvý uzol z dráhy vloženého uzla, ktorého súčiniteľ vyváženia je iný ako -1 , 0 alebo 1.
| Štát | Akcia |
|---|---|
 | Uzol B bol vložený do ľavého podstromu z C pravý podstrom A , kvôli ktorému sa A stal nevyváženým uzlom s faktorom rovnováhy - 2. V tomto prípade ide o rotáciu RL, kde: Vložený uzol je v ľavom podstrome pravého podstromu A |
 | Ako rotácia RL = rotácia LL + rotácia RR, teda LL (v smere hodinových ručičiek) na podstrome s koreňom C sa vykonáva ako prvý. Tým, že urobíte RR rotáciu, uzol C sa stal správnym podstromom B . |
 | Po vykonaní rotácie LL uzol A je stále nevyvážený, t. j. má faktor rovnováhy -2, čo je spôsobené pravým podstromom uzla pravého podstromu A. |
 | Teraz vykonáme rotáciu RR (rotáciu proti smeru hodinových ručičiek) na plnom strome, teda na uzle A. uzol C sa teraz stal pravým podstromom uzla B a uzol A sa stal ľavým podstromom uzla B. |
 | Faktor rovnováhy každého uzla je teraz buď -1, 0 alebo 1, t. j. BST je teraz vyvážený. |
Otázka: Vytvorte strom AVL s nasledujúcimi prvkami
H, I, J, B, A, E, C, F, D, G, K, L
1. Vložte H, I, J
Po vložení vyššie uvedených prvkov, najmä v prípade H, sa BST stane nevyváženým, pretože Balančný faktor H je -2. Keďže BST je skosený doprava, vykonáme rotáciu RR na uzle H.
Výsledný strom bilancie je:
2. Vložte B, A
Po vložení vyššie uvedených prvkov, najmä v prípade A, sa BST stane nevyváženým, pretože Balančný faktor H a I je 2, uvažujeme prvý uzol z posledného vloženého uzla, t. j. H. Keďže BST z H je skosený doľava, vykonáme rotáciu LL na uzle H.
Výsledný strom bilancie je:
3. Vložte E
Po vložení E sa BST stane nevyváženým, pretože Balančný faktor I je 2, pretože ak cestujeme z E do I, zistíme, že je vložený do ľavého podstromu pravého podstromu I, vykonáme rotáciu LR na uzle I. LR = rotácia RR + LL
3 a) Najprv vykonáme rotáciu RR na uzle B
Výsledný strom po rotácii RR je:
3b) Najprv vykonáme rotáciu LL na uzle I
Výsledný vyvážený strom po rotácii LL je:
4. Vložte C, F, D
Po vložení C, F, D, BST sa stane nevyváženým, pretože Balančný faktor B a H je -2, pretože ak cestujeme z D do B, zistíme, že je vložený do pravého podstromu ľavého podstromu B, vykonáme RL Rotácia na uzle I. RL = LL + RR rotácia.
4a) Najprv vykonáme rotáciu LL na uzle E
Výsledný strom po rotácii LL je:
4b) Potom vykonáme rotáciu RR na uzle B
Výsledný vyvážený strom po rotácii RR je:
5. Vložte G
Po vložení G sa BST stane nevyváženým, pretože Balančný faktor H je 2, pretože ak cestujeme z G do H, zistíme, že je vložený do ľavého podstromu pravého podstromu H, vykonáme rotáciu LR na uzle I. LR = rotácia RR + LL.
5 a) Najprv vykonáme rotáciu RR na uzle C
Výsledný strom po rotácii RR je:
5 b) Potom vykonáme rotáciu LL na uzle H
Výsledný vyvážený strom po rotácii LL je:
6. Vložte K
Po vložení K sa BST stane nevyváženým, pretože Balančný faktor I je -2. Keďže BST je skosený doprava od I do K, preto vykonáme rotáciu RR na uzle I.
Výsledný vyvážený strom po rotácii RR je:
7. Vložte L
rolovacie koliesko nefunguje
Po vložení je strom L stále vyvážený, pretože Balančný faktor každého uzla je teraz buď -1, 0, +1. Strom je teda vyvážený strom AVL
