Drevo AVL sta leta 1962 izumila GM Adelson - Velsky in EM Landis. Drevo je v čast svojih izumiteljev poimenovano AVL.
Drevo AVL je mogoče definirati kot višinsko uravnoteženo binarno iskalno drevo, v katerem je vsako vozlišče povezano s faktorjem ravnovesja, ki se izračuna tako, da se višina njegovega desnega poddrevesa odšteje od višine njegovega levega poddrevesa.
Drevo naj bi bilo uravnoteženo, če je faktor ravnovesja vsakega vozlišča med -1 in 1, sicer bo drevo neuravnoteženo in ga bo treba uravnotežiti.
Faktor ravnotežja (k) = višina (levo (k)) - višina (desno (k))
Če je faktor ravnotežja katerega koli vozlišča 1, to pomeni, da je levo poddrevo eno raven višje od desnega poddrevesa.
Če je faktor ravnotežja katerega koli vozlišča 0, to pomeni, da imata levo poddrevo in desno poddrevo enako višino.
Če je faktor ravnotežja katerega koli vozlišča -1, to pomeni, da je levo poddrevo eno raven nižje od desnega poddrevesa.
Drevo AVL je podano na naslednji sliki. Vidimo lahko, da je faktor ravnotežja, povezan z vsakim vozliščem, med -1 in +1. zato je primer drevesa AVL.
Kompleksnost
| Algoritem | Povprečen primer | V najslabšem primeru |
|---|---|---|
| Vesolje | o(n) | o(n) |
| Iskanje | o (log n) | o (log n) |
| Vstavi | o (log n) | o (log n) |
| Izbriši | o (log n) | o (log n) |
Operacije na drevesu AVL
Ker je drevo AVL tudi binarno iskalno drevo, se vse operacije izvajajo na enak način, kot se izvajajo v binarnem iskalnem drevesu. Iskanje in prečkanje ne vodita do kršitve lastnosti drevesa AVL. Vendar pa sta operaciji vstavljanja in brisanja, ki lahko kršita to lastnost, zato ju je treba ponovno pregledati.
| SN | Delovanje | Opis |
|---|---|---|
| 1 | Vstavljanje | Vstavljanje v drevo AVL se izvaja na enak način, kot se izvaja v binarnem iskalnem drevesu. Vendar pa lahko povzroči kršitev lastnosti drevesa AVL, zato je drevo morda treba uravnotežiti. Drevo je mogoče uravnotežiti z uporabo rotacije. |
| 2 | Izbris | Izbris se lahko izvede tudi na enak način, kot se izvede v binarnem iskalnem drevesu. Izbris lahko tudi poruši ravnotežje drevesa, zato se za ponovno uravnoteženje drevesa uporabljajo različne vrste vrtenja. |
Zakaj AVL Tree?
Drevo AVL nadzoruje višino binarnega iskalnega drevesa tako, da ne dovoli, da bi bilo poševno. Čas, potreben za vse operacije v binarnem iskalnem drevesu višine h je O(h) . Vendar pa se lahko razširi na O(n) če se BST zamakne (tj. najslabši primer). Z omejitvijo te višine na log n drevo AVL naloži zgornjo mejo za vsako operacijo, ki naj bo O(log n) kjer je n število vozlišč.
Rotacije AVL
Vrtenje v drevesu AVL izvajamo samo v primeru, če je faktor ravnotežja drugačen od -1, 0 in 1 . V bistvu obstajajo štiri vrste rotacije, ki so naslednje:
- Vrtenje L L: Vstavljeno vozlišče je v levem poddrevesu levega poddrevesa A
- R R rotacija: vstavljeno vozlišče je v desnem poddrevesu desnega poddrevesa A
- Vrtenje L R: vstavljeno vozlišče je v desnem poddrevesu levega poddrevesa A
- Vrtenje R L: vstavljeno vozlišče je v levem poddrevesu desnega poddrevesa A
Pri čemer je vozlišče A vozlišče, katerega faktor ravnotežja ni -1, 0, 1.
Prvi dve rotaciji LL in RR sta enojni rotaciji, naslednji dve rotaciji LR in RL pa sta dvojni rotaciji. Da je drevo neuravnoteženo, mora biti najmanjša višina vsaj 2. Razumejmo vsako rotacijo
1. Vrtenje RR
Ko postane BST neuravnotežen, ker je vozlišče vstavljeno v desno poddrevo desnega poddrevesa A, potem izvedemo rotacijo RR, rotacija RR je rotacija v nasprotni smeri urnega kazalca, ki se uporablja na robu pod vozliščem, ki ima faktor ravnotežja -2
V zgornjem primeru ima vozlišče A faktor ravnovesja -2, ker je vozlišče C vstavljeno v desno poddrevo desnega poddrevesa A. Rotacijo RR izvedemo na robu pod A.
2. Vrtenje LL
Ko BST postane neuravnotežen, ker je vozlišče vstavljeno v levo poddrevo levega poddrevesa C, potem izvedemo rotacijo LL, rotacija LL je rotacija v smeri urinega kazalca, ki se uporabi na robu pod vozliščem, ki ima faktor ravnotežja 2.
V zgornjem primeru ima vozlišče C faktor ravnotežja 2, ker je vozlišče A vstavljeno v levo poddrevo levega poddrevesa C. Rotacijo LL izvedemo na robu pod A.
3. Vrtenje LR
Dvojna rotacija je nekoliko težja od enojne rotacije, kar je že razloženo zgoraj. LR rotacija = RR rotacija + LL rotacija, tj. prva RR rotacija se izvede na poddrevesu in nato LL rotacija se izvede na celotnem drevesu, s polnim drevesom mislimo na prvo vozlišče s poti vstavljenega vozlišča, katerega faktor ravnovesja ni -1 , 0 ali 1.
Naj jasno razumemo vsak korak posebej:
pridobi dolžino niza v c
| Država | Akcija |
|---|---|
 | Vozlišče B je bilo vstavljeno v desno poddrevo A levega poddrevesa C, zaradi česar je C postalo neuravnoteženo vozlišče s faktorjem ravnotežja 2. Ta primer je rotacija L R, kjer je: Vstavljeno vozlišče je v desnem poddrevesu levega poddrevesa C |
 | Ker je rotacija LR = rotacija RR + LL, se torej najprej izvede RR (v nasprotni smeri urinega kazalca) na poddrevesu s korenino A. Z vrtenjem RR, vozlišče A , je postalo levo poddrevo od B . |
 | Po izvedbi rotacije RR je vozlišče C še vedno neuravnoteženo, tj. ima faktor ravnotežja 2, saj je vstavljeno vozlišče A levo od leve C |
 | Zdaj izvedemo LL rotacijo v smeri urinega kazalca na celotnem drevesu, tj. na vozlišču C. vozlišču C je zdaj postalo desno poddrevo vozlišča B, A je levo poddrevo B |
 | Faktor ravnotežja vsakega vozlišča je zdaj -1, 0 ali 1, kar pomeni, da je BST zdaj uravnotežen. |
4. Vrtenje RL
Kot smo že omenili, so dvojne rotacije nekoliko težje od enojne rotacije, kar je bilo že razloženo zgoraj. R L rotacija = LL rotacija + RR rotacija, tj. najprej se LL rotacija izvede na poddrevesu in nato RR rotacija se izvede na celotnem drevesu, s polnim drevesom mislimo na prvo vozlišče s poti vstavljenega vozlišča, katerega faktor ravnovesja ni -1 , 0 ali 1.
| Država | Akcija |
|---|---|
 | Vozlišče B je bil vstavljen v levo poddrevo C desno poddrevo od A , zaradi česar je A postalo neuravnoteženo vozlišče s faktorjem ravnotežja - 2. Ta primer je vrtenje RL, kjer je: Vstavljeno vozlišče je v levem poddrevesu desnega poddrevesa A |
 | Ker je rotacija RL = rotacija LL + rotacija RR, torej LL (v smeri urinega kazalca) na poddrevesu s korenino C se izvaja najprej. Z rotacijo RR, vozlišče C je postalo desno poddrevo B . |
 | Po izvedbi rotacije LL, vozl A je še vedno neuravnotežen, tj. ima faktor ravnovesja -2, kar je posledica desnega poddrevesa vozlišča A desnega poddrevesa. |
 | Zdaj izvedemo RR rotacijo (rotacija v nasprotni smeri urinega kazalca) na celotnem drevesu, tj. na vozlišču A. C je zdaj postalo desno poddrevo vozlišča B, vozlišče A pa je postalo levo poddrevo B. |
 | Faktor ravnotežja vsakega vozlišča je zdaj -1, 0 ali 1, kar pomeni, da je BST zdaj uravnotežen. |
V: Sestavite drevo AVL z naslednjimi elementi
H, I, J, B, A, E, C, F, D, G, K, L
1. Vstavi H, I, J
Ob vstavitvi zgornjih elementov, zlasti v primeru H, BST postane neuravnotežen, saj je faktor uravnoteženosti H -2. Ker je BST nagnjen v desno, bomo izvedli vrtenje RR na vozlišču H.
Nastalo ravnotežno drevo je:
2. Vstavite B, A
Pri vstavitvi zgornjih elementov, zlasti v primeru A, BST postane neuravnotežen, saj je faktor ravnovesja H in I 2, upoštevamo prvo vozlišče od zadnjega vstavljenega vozlišča, tj. H. Ker je BST iz H nagnjen levo, izvedli bomo LL rotacijo na vozlišču H.
Nastalo ravnotežno drevo je:
3. Vstavite E
Ko vstavimo E, postane BST neuravnotežen, saj je faktor ravnovesja I 2, ker če potujemo od E do I ugotovimo, da je vstavljen v levo poddrevo desnega poddrevesa I, bomo izvedli LR rotacijo na vozlišču I. LR = vrtenje RR + LL
3 a) Najprej izvedemo RR rotacijo na vozlišču B
Nastalo drevo po rotaciji RR je:
3b) Najprej izvedemo LL rotacijo na vozlišču I
Nastalo uravnoteženo drevo po rotaciji LL je:
4. Vstavite C, F, D
Pri vstavljanju C, F, D postane BST neuravnotežen, saj je faktor ravnovesja B in H -2, ker če potujemo od D do B, ugotovimo, da je vstavljen v desno poddrevo ali levo poddrevo B, bomo izvedli RL Rotacija na vozlišču I. RL = LL + RR rotacija.
4a) Najprej izvedemo LL rotacijo na vozlišču E
Nastalo drevo po rotaciji LL je:
4b) Nato izvedemo RR rotacijo na vozlišču B
Nastalo uravnoteženo drevo po rotaciji RR je:
5. Vstavite G
Ko vstavimo G, BST postane neuravnotežen, saj je faktor ravnotežja H 2, ker če potujemo od G do H, ugotovimo, da je vstavljen v levo poddrevo desnega poddrevesa H, bomo izvedli LR rotacijo na vozlišču I. LR = RR + LL vrtenje.
5 a) Najprej izvedemo RR rotacijo na vozlišču C
Nastalo drevo po rotaciji RR je:
5 b) Nato izvedemo LL rotacijo na vozlišču H
Nastalo uravnoteženo drevo po rotaciji LL je:
6. Vstavite K
Ko vstavite K, BST postane neuravnotežen, saj je faktor ravnovesja I -2. Ker je BST nagnjen v desno od I do K, bomo izvedli RR rotacijo na vozlišču I.
Nastalo uravnoteženo drevo po rotaciji RR je:
7. Vstavite L
Po vstavitvi je drevo L še vedno uravnoteženo, saj je faktor ravnovesja vsakega vozlišča zdaj bodisi -1, 0, +1. Zato je drevo uravnoteženo drevo AVL
