AVL Treen keksivät GM Adelson - Velsky ja EM Landis vuonna 1962. Puu on nimetty AVL:ksi sen keksijöiden kunniaksi.
AVL-puu voidaan määritellä korkeudeltaan tasapainotetuksi binäärihakupuuksi, jossa jokainen solmu liittyy tasapainokertoimeen, joka lasketaan vähentämällä sen oikean alipuun korkeus vasemman alipuun korkeudesta.
Puun sanotaan olevan tasapainossa, jos kunkin solmun tasapainokerroin on välillä -1:stä 1:een, muuten puu on epätasapainossa ja se on tasapainotettava.
Tasapainokerroin (k) = korkeus (vasen(k)) - korkeus (oikea(k))
Jos minkä tahansa solmun tasapainokerroin on 1, se tarkoittaa, että vasen alipuu on yhden tason korkeampi kuin oikea alipuu.
Jos minkä tahansa solmun tasapainokerroin on 0, se tarkoittaa, että vasemman ja oikean alipuun korkeus on yhtä suuri.
Jos minkä tahansa solmun tasapainokerroin on -1, se tarkoittaa, että vasen alipuu on yhden tason alempana kuin oikea alipuu.
AVL-puu on esitetty seuraavassa kuvassa. Näemme, että kuhunkin solmuun liittyvä tasapainokerroin on välillä -1 ja +1. siksi se on esimerkki AVL-puusta.
Monimutkaisuus
| Algoritmi | Keskimääräinen tapaus | Pahimmassa tapauksessa |
|---|---|---|
| Avaruus | päällä) | päällä) |
| Hae | o(log n) | o(log n) |
| Lisää | o(log n) | o(log n) |
| Poistaa | o(log n) | o(log n) |
Toiminnot AVL-puussa
Koska AVL-puu on myös binäärihakupuu, kaikki toiminnot suoritetaan samalla tavalla kuin ne suoritetaan binäärihakupuussa. Etsiminen ja poikki ei johda AVL-puun ominaisuuden rikkomiseen. Lisäys ja poistaminen ovat kuitenkin toimintoja, jotka voivat rikkoa tätä ominaisuutta, ja siksi niitä on tarkasteltava uudelleen.
| SN | Operaatio | Kuvaus |
|---|---|---|
| 1 | Lisäys | Lisäys AVL-puuhun suoritetaan samalla tavalla kuin se suoritetaan binäärihakupuussa. Se voi kuitenkin johtaa AVL-puuomaisuuden rikkomiseen ja siksi puu saattaa tarvita tasapainotusta. Puu voidaan tasapainottaa pyörittämällä. |
| 2 | Poistaminen | Poistaminen voidaan myös suorittaa samalla tavalla kuin se tehdään binäärihakupuussa. Poistaminen voi myös häiritä puun tasapainoa, joten puun tasapainottamiseen käytetään erilaisia pyörityksiä. |
Miksi AVL Tree?
AVL-puu ohjaa binäärihakupuun korkeutta siten, ettei se anna sen olla vinossa. Aika, joka kuluu kaikkiin operaatioihin binäärihakupuussa, jonka korkeus on h Vai niin) . Sitä voidaan kuitenkin laajentaa Päällä) jos BST tulee vinoon (eli pahimmassa tapauksessa). Rajoittamalla tämän korkeuden log n:ään, AVL-puu asettaa ylärajan kullekin olla-operaatiolle O(log n) missä n on solmujen lukumäärä.
AVL Rotations
Suoritamme kiertoa AVL-puussa vain siinä tapauksessa, että Balance Factor on muu kuin -1, 0 ja 1 . Periaatteessa on neljä kiertotyyppiä, jotka ovat seuraavat:
- L L -kierto: Lisätty solmu on A:n vasemman alipuun vasemmassa alipuussa
- R R -kierto : Lisätty solmu on A:n oikean alipuun oikeassa alipuussa
- L R -kierto : Lisätty solmu on A:n vasemman alipuun oikeassa alipuussa
- R L -kierto: Lisätty solmu on A:n oikean alipuun vasemmassa alipuussa
Missä solmu A on solmu, jonka saldotekijä on muu kuin -1, 0, 1.
Ensimmäiset kaksi kiertoa LL ja RR ovat yksittäiskiertoja ja seuraavat kaksi kiertoa LR ja RL ovat kaksoiskierroksia. Jotta puu olisi epätasapainossa, minimikorkeuden on oltava vähintään 2. Ymmärrämme jokaisen kierroksen
1. RR-kierto
Kun BST tulee epätasapainoiseksi, koska A:n oikean alipuun oikeaan alipuuhun lisätään solmu, suoritetaan RR-kierto, RR-kierto on vastapäivään kierto, jota sovelletaan solmun alapuolelle, jonka tasapainokerroin on -2.
Yllä olevassa esimerkissä solmulla A on tasapainokerroin -2, koska solmu C on lisätty oikean alipuun A oikeaan alipuuhun. Suoritamme RR-kierron A:n alapuolella olevalle reunalle.
2. LL-kierto
Kun BST tulee epätasapainoiseksi, koska C:n vasemman alipuun vasempaan alipuuhun lisätään solmu, suoritetaan LL-kierto, LL-kierto on myötäpäivään kiertoa, jota sovelletaan solmun alapuolelle, jolla on tasapainokerroin 2.
Yllä olevassa esimerkissä solmulla C on tasapainotekijä 2, koska solmu A on lisätty C:n vasemman alipuun vasempaan alipuuhun. Suoritamme LL-kierron A:n alapuolella olevalle reunalle.
3. LR-kierto
Kaksoiskierrokset ovat hieman kovempaa kuin yksikierto, joka on jo selitetty edellä. LR-kierto = RR-kierto + LL-kierto, eli ensin RR-kierto suoritetaan alipuulle ja sitten LL-kierto koko puulle, täydellä puulla tarkoitamme ensimmäistä solmua lisätyn solmun polulta, jonka tasapainokerroin on muu kuin -1 , 0 tai 1.
Ymmärtäkäämme jokainen askel hyvin selvästi:
| Osavaltio | Toiminta |
|---|---|
 | A:n oikeaan alipuuhun C:n vasempaan alipuuhun on lisätty solmu B, minkä vuoksi C:stä on tullut epätasapainoinen solmu, jolla on tasapainokerroin 2. Tämä tapaus on L R -kierto, jossa: Lisätty solmu on vasemman alipuun oikeassa alipuussa. C |
 | Koska LR-kierto = RR + LL-kierto, RR (vastapäivään) suoritetaan ensin A:sta juurtuneessa alipuussa. Tekemällä RR-kiertoa, solmu A , on tullut kohteen vasen alipuu B . |
 | RR-kierron suorittamisen jälkeen solmu C on edelleen epätasapainossa, eli sillä on tasapainotekijä 2, koska lisätty solmu A on vasemmalla tai vasemmalla. C |
 | Nyt suoritetaan LL myötäpäivään kierto täydessä puussa, eli solmun C. solmussa C on nyt tullut solmun B oikea alipuu, A on B:n vasen alipuu |
 | Jokaisen solmun tasapainokerroin on nyt joko -1, 0 tai 1, eli BST on nyt tasapainotettu. |
4. RL-kierto
Kuten jo mainittiin, kaksoiskierrokset ovat hieman kovempaa kuin yksikierto, joka on jo selitetty edellä. RL-kierto = LL-kierto + RR-kierto, eli ensin LL-kierto suoritetaan alipuulle ja sitten RR-kierto koko puulle, täydellä puulla tarkoitamme ensimmäistä solmua lisätyn solmun polulta, jonka tasapainokerroin on muu kuin -1 , 0 tai 1.
| Osavaltio | Toiminta |
|---|---|
 | Solmu B on lisätty kohteen vasempaan alipuuhun C oikea alipuu A , jonka vuoksi A:sta on tullut epätasapainoinen solmu, jonka tasapainokerroin - 2. Tämä tapaus on RL-kierto, jossa: Lisätty solmu on A:n oikean alipuun vasemmassa alipuussa |
 | Koska RL-kierto = LL-kierto + RR-kierto, siis LL (myötäpäivään) alipuussa, jonka juuret ovat C suoritetaan ensin. Tekemällä RR-kiertoa, solmu C on tullut oikea alipuu B . |
 | Kun LL-kierto on suoritettu, solmu A on edelleen epätasapainossa, eli sillä on tasapainokerroin -2, mikä johtuu oikeanpuoleisen alipuusolmun A oikeasta alipuusta. |
 | Nyt suoritetaan RR-kierto (vastapäivään) täydelle puulle, eli solmulle A. solmu C on nyt tullut solmun B oikea alipuu ja solmusta A on tullut B:n vasen alipuu. |
 | Jokaisen solmun tasapainokerroin on nyt joko -1, 0 tai 1, eli BST on nyt tasapainotettu. |
K: Muodosta AVL-puu, jossa on seuraavat elementit
H, I, J, B, A, E, C, F, D, G, K, L
1. Lisää H, I, J
Kun yllä olevat elementit lisätään, erityisesti H:n tapauksessa, BST tulee epätasapainoiseksi, koska H:n tasapainokerroin on -2. Koska BST on oikealle vino, suoritamme RR-kierron solmussa H.
Tuloksena oleva tasapainopuu on:
2. Lisää B, A
Yllä olevia elementtejä lisättäessä, erityisesti A:n tapauksessa, BST tulee epätasapainoiseksi, koska H:n ja I:n tasapainotekijä on 2, otetaan huomioon viimeksi lisätyn solmun ensimmäinen solmu eli H. Koska H:n BST on vasemmalle vino, Suoritamme LL Rotationin solmussa H.
Tuloksena oleva tasapainopuu on:
3. Aseta E
Lisättäessä E, BST tulee epätasapainoiseksi, koska I:n tasapainokerroin on 2, koska jos kuljemme paikasta E paikkaan I, huomaamme, että se on lisätty I:n oikean alipuun vasempaan alipuuhun, suoritamme LR-kierron solmulle I. LR = RR + LL kierto
3 a) Suoritamme ensin RR-rottamisen solmulle B
Tuloksena oleva puu RR-kierron jälkeen on:
3b) Suoritamme ensin LL-rotaatio solmulle I
Tuloksena oleva tasapainoinen puu LL-kierron jälkeen on:
4. Lisää C, F, D
Lisättäessä C, F, D, BST tulee epätasapainoiseksi, koska B:n ja H:n tasapainokerroin on -2, koska jos kuljemme D:stä B:hen, huomaamme, että se on lisätty B:n vasemman alipuun oikeaan alipuuhun, suoritamme RL Rotaatio solmussa I. RL = LL + RR kierto.
4a) Suoritamme ensin LL-kierron solmulle E
Tuloksena oleva puu LL-kierron jälkeen on:
4b) Suoritamme sitten RR-rottamisen solmulle B
asetettu javassa
Tuloksena oleva tasapainoinen puu RR-kierron jälkeen on:
5. Aseta G
Lisättäessä G, BST tulee epätasapainoiseksi, koska H:n tasapainokerroin on 2, koska jos kuljemme G:stä H:hen, huomaamme, että se lisätään H:n oikean alipuun vasempaan alipuuhun, suoritamme LR-kierron solmussa I. LR = RR + LL kierto.
5 a) Suoritamme ensin RR-rotaatio solmussa C
Tuloksena oleva puu RR-kierron jälkeen on:
5 b) Suoritamme sitten LL-rotaatio solmulle H
Tuloksena oleva tasapainoinen puu LL-kierron jälkeen on:
6. Lisää K
Lisättäessä K, BST tulee epätasapainoiseksi, koska I:n saldotekijä on -2. Koska BST on vinossa I:stä K:hen, suoritamme RR-kierron solmulle I.
Tuloksena oleva tasapainoinen puu RR-kierron jälkeen on:
7. Aseta L
Lisättäessä L-puu on edelleen tasapainossa, koska kunkin solmun tasapainokerroin on nyt joko -1, 0, +1. Tästä syystä puu on tasapainoinen AVL-puu
