An AVL puu määritellään itsetasapainotukseksi Minkä tahansa solmun vasemman alipuun ja oikean alipuun korkeuksien välinen ero tunnetaan nimellä tasapainotekijä solmusta.

AVL-puu on nimetty sen keksijöiden, Georgi Adelson-Velskyn ja Evgenii Landisin mukaan, jotka julkaisivat sen vuoden 1962 artikkelissaan An Algorithm for organisation of information.

Esimerkki AVL-puista:

AVL puu

0,0625 murtolukuna

Yllä oleva puu on AVL, koska jokaisen solmun vasemman ja oikean alipuun korkeuksien erot ovat pienempiä tai yhtä suuria kuin 1.

Toiminnot AVL-puussa:

• Lisäys
• Poistaminen
• Etsitään [Se on samanlainen kuin haun tekeminen BST:ssä]

Alipuiden kiertäminen AVL-puussa:

AVL-puu voi pyöriä jollakin seuraavista neljästä tavasta pitääkseen itsensä tasapainossa:

Kierto vasemmalle :

Kun solmu lisätään oikean alipuun oikeaan alipuuhun, jos puu menee epätasapainosta, teemme yhden kierroksen vasemmalle.

taskulampun asennus

Kierto vasemmalle AVL-puussa

Oikea kierto :

Jos vasemman alipuun vasempaan alipuuhun lisätään solmu, AVL-puu saattaa mennä epätasapainosta, teemme yhden kierroksen oikealle.

Kierto oikealle AVL-puussa

Kierto vasemmalle-oikealle :

kuinka luodaan taulukko javassa

Kierto vasemmalle oikealle on yhdistelmä, jossa ensimmäinen kierto vasemmalle tapahtuu sen jälkeen, kun oikea kierto on suoritettu.

Kierto vasemmalle-oikealle AVL-puussa

Oikea-vasen kierto :

javascript uni

Kierto oikealle-vasemmalle on yhdistelmä, jossa ensimmäinen oikea kierto tapahtuu sen jälkeen, kun kierto vasemmalle suoritetaan.

Oikea-vasen kierto AVL-puussa

AVL Treen sovellukset:

1. Sitä käytetään valtavien tietueiden indeksoimiseen tietokannassa ja myös tehokkaaseen hakuun.
2. Kaikentyyppisille muistikokoelmille, mukaan lukien joukot ja sanakirjat, käytetään AVL-puita.
3. Tietokantasovellukset, joissa lisäykset ja poistot ovat harvinaisempia, mutta toistuvia tietojen hakuja tarvitaan
4. Ohjelmisto, joka vaatii optimoitua hakua.
5. Sitä käytetään yritysalueilla ja juonipeleissä.

AVL Treen edut:

1. AVL-puut voivat tasapainottaa itsensä.
2. Se ei varmasti ole vinossa.
3. Se tarjoaa nopeampia hakuja kuin Red-Black Trees
4. Parempi hakuajan monimutkaisuus verrattuna muihin puihin, kuten binääripuuhun.
5. Korkeus ei saa ylittää log(N), missä N on puun solmujen kokonaismäärä.

AVL-puun haitat:

1. Se on vaikea toteuttaa.
2. Sillä on korkeat vakiokertoimet joidenkin toimintojen osalta.
3. Vähemmän käytetty verrattuna Red-Black-puihin.
4. Melko tiukan tasapainonsa ansiosta AVL-puut tarjoavat monimutkaisia ​​lisäys- ja poistotoimenpiteitä, kun kiertoja tehdään enemmän.
5. Käytä enemmän käsittelyä tasapainottamiseksi.

Aiheeseen liittyvät artikkelit:

• Johdatus binäärihakupuihin – Tietorakenteen ja algoritmin opetusohjelmat
• Lisäys AVL-puuhun
• Poisto AVL-puussa