Johdanto AVL-puun tietorakenteeseen

Tietorakenteessa oleva AVL-puu viittaa Adelson-, Velski- ja Landis-puuhun. Tämä on parannettu versio binaarisesta hakupuusta. Sillä on kaikki ominaisuudet kuin binaarisessa hakupuussa, mutta se eroaa vain, koska ne yllä pitävät eroa vasemman ja oikean alapuun korkeudessa ja varmistaa myös, että sen arvo on <= 1 puussa, tätä kutsutaan tasapainoksi Tekijä.

Balance Factor = height(left-subtree) − height(right-subtree)

Esimerkiksi: Harkitse seuraavia puita

Yllä olevassa esimerkissä oikean alapuun korkeuden = 2 ja vasemman = 3, siis BF = 2, joka on <= 1, siis puun sanotaan olevan tasapainossa.

Miksi tarvitsemme AVL-puuta DS: ssä?

Kun työskentelemme binaarisen hakupuun kanssa, törmäämme tilanteeseen, jossa elementit ovat lajiteltuina. Tällaisissa tapauksissa kaikki taulukon elementit on sijoitettu juuren yhdelle puolelle, tämä johtaa elementtien etsimisen aikataulun monimutkaisuuteen ryhmästä ja monimutkaisuudesta tulee -O (n) eli puun pahimmassa tapauksessa monimutkaisuus . Tällaisten ongelmien ratkaisemiseksi ja hakuajan vähentämiseksi Adelson, Velski & Landis keksivät AVL-puut.

Esimerkki:

Yllä olevassa kuvassa vasemman alaryhmän korkeus = 3 oli kuin

Oikean alaosan korkeus = 0

Siten tasapainotuskerroin = 3-0 = 3. Täten elementin etsinnällä sellaisessa puussa on O (n) monimutkaisuus, joka on samanlainen kuin lineaarinen haku. Tämän monimutkaisen haun välttämiseksi AVL-puu otettiin käyttöön missä puun jokaisen solmun on ylläpidettävä

tasapainotuskerroin <= 1, muuten suoritetaan erilaisia ​​kiertotekniikoita tällaisen puun tasapainottamiseksi.

Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);

Kiertojen tyypit

Kun puun tasapainotuskerroin ei täytä <= 1 ehtoa, silloin on suoritettava kierto, jotta puu muuttuu tasapainoiseksi puuksi.

Kiertoa on 4 tyyppiä:

1. Vasen kierto: Jos solmun lisääminen puun oikealle puolelle tekee siitä epätasapainon, silloin on kierto vasemmalle suoritettava.

2. Oikea kierto: Jos solmun lisääminen puun vasemmalle puolelle tekee solmun epätasapainosta, oikea kierto on suoritettava. Toisin sanoen, kun solmujen lukumäärä kasvaa vasemmalla puolella, syntyy tarve siirtää elementtejä oikealle puolelle tasapainottaa sitä, joten sen sanotaan olevan oikea kierto.

3. Vasen-oikea-kierto: Tämän tyyppinen rotaatio on yhdistelmä kahdesta edellä selitetystä rotaatiosta. Tämän tyyppinen kierto tapahtuu, kun yksi elementti lisätään vasemman puun oikeaan alaosaan.

Suorita tällöin ensin alapuun vasen kierto, jota seuraa vasemman puun oikea kierto.

4. Oikealta vasemmalle-kierto: Tämän tyyppinen kierto koostuu myös sekvenssistä, joka on yli 2 kiertoa. Tämän tyyppinen kierto tarvitaan, kun elementti lisätään oikean alaosan vasemmalle puolelle ja puu tasapainottuu. Tällöin suoritamme ensin oikeanpuoleisen kääntymisen oikealle ja sitten vasemmanpuoleisen kääntymisen oikealle puulle.

Toiminnot AVL-puussa DS: ssä

Alle 3 toimenpidettä, jotka voidaan suorittaa AVL-puulle: -

1. Etsi

Tämä toimenpide on samanlainen kuin haun suorittaminen binaarisessa hakupuussa. Seuraavat vaiheet ovat seuraavat:

  • Lue elementti, jonka käyttäjä antaa sanomalla x.
  • Vertaa elementtiä juuri, jos se on sama, poistu, muuten siirry seuraavaan vaiheeseen.
  • Jos x

Muuta mennä oikean lapsen luo ja vertaa uudelleen.

Seuraa prosesseja B ja C, kunnes löydät elementin ja poistu.

Tällä prosessilla on O (log n) monimutkaisuus.

Esimerkki:

Harkitse tätä puuta, jossa meidän on suoritettava haku solmuarvolle 9.
Ensin annetaan x = 9, juuriarvo (12)> x, sitten arvon on oltava juurielementin vasemmassa alakentässä.
Nyt x: tä verrataan solmun arvoon 3
x> 3, joten meidän on edettävä kohti oikeaa alaosaa.
Nyt x: tä verrataan solmuun (9), missä 9 == 9 palaa true. Siten elementtihaku suoritetaan puussa loppuun.

2. Lisäys

Lisättäessä elementtiä AVL-puuhun, meidän on löydettävä paikkakohtainen elementti, joka on lisättävä ja sitten elementti kiinnitetään samalla tavalla kuin lisäys BST: ssä, mutta sen jälkeen tarkistetaan, onko puu edelleen tasapainossa vai ei. ts. solmun tasapainotekijä on <= 1. Ja tietyt kierrokset suoritetaan tarpeen mukaan.

Monimutkaisuus on O (log n).
Esimerkki: Mieti alla olevaa puuta,

Jokaisella solmulla on tasapainotuskerroin 0, -1 tai 1, joten puu on tasapainossa. Nyt antaa mitä tapahtuu, kun solmu, jonka arvo on 1, lisätään.
Ensimmäinen puu kuljetetaan löytääkseen sijainti, johon se on asetettava …
1 <2 on siten kirjoitettu solmun (2) vasemmanpuoleisena lapsena.
Asetuksen jälkeen solmu (9) muuttuu epätasapainoksi, kun tasapainotuskerroin = 2. Nyt sille tehdään oikea kierto.
Puusta tulee tasapaino oikean kiertämisen jälkeen ja siten lisäysoperaatio on suoritettu onnistuneesti loppuun.

3. Poisto

Elementin poistaminen AVL-puusta käsittää myös elementin etsimisen puusta ja sen poistamisen. Hakutoiminto on sama kuin BST, ja poistettavan elementin löytämisen jälkeen elementti poistetaan puusta ja elementit säädetään tekemään siitä BST. Sen jälkeen kun näiden elementtien tasapainotuskerroin on tarkistettu, on 0, -1 tai 1, ja siten suoritetaan sopivat kiertootteet tasapainottamiseksi.

Monimutkaisuus, jos O (log n).

Tarkastellaan annettua puuta, jonka kaikkien tasapainotuskerroin on 0, -1 tai 1.
Poistakaamme nyt solmu, jonka arvo on 16.
Ensimmäinen puu kuljetetaan löytääkseen solmu, jonka arvo on 16, sama kuin hakualgoritmi.
Solmu 16 korvataan tämän solmun sisääntulon edeltäjällä, joka on suurin elementti vasemmasta alapuusta eli 12
Puusta on tullut epätasapainoista, joten LL - kierto on suoritettava.
Nyt jokainen solmu on tasapainotettu.

Johtopäätös - AVL-puu tietorakenteessa

AVL-puu on binaarisen hakupuun jälkeläinen, mutta se välttää sen haitan, joka johtuu kasvavasta monimutkaisuudesta, jos elementit lajitellaan. Se tarkkailee puun tasapainotuskerrointa 0 tai 1 tai -1. Jos puusta tulee epätasapainoinen, vastaavat kiertotekniikat suoritetaan puun tasapainottamiseksi.

Suositellut artikkelit

Tämä on opas AVL-puun tietorakenteeseen. Tässä keskustellaan johdannosta, AVL-puun toiminnoista DS: ssä ja rotaatiotyypeistä. Voit myös käydä läpi muiden aiheeseen liittyvien artikkeleidemme saadaksesi lisätietoja -

  1. jQuery Elements
  2. Mikä on tietotiede
  3. Puutyypit tietorakenteessa
  4. C # tietotyypit

Luokka: