Lähdekoodi sivulle AVL-puu

{{lähteetön}}[[Tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''AVL-puu''' on [[binäärinen hakupuu]]. Se on ensimmäinen tietojenkäsittelytieteessä esitetty itsestään tasapainottuva binäärinen hakupuu. AVL-puussa kaikkien solmujen alipuiden korkeusero on korkeintaan yksi. Haun, lisäyksen ja poiston [[asymptoottinen suoritusaika]] on <math>O(\log n)</math> sekä keskimääräisessä että pahimmassa tapauksessa. Lisäykset ja poistot saattavat vaatia puun tasapainottamisen uudelleen yhdellä tai useammalla ''kierrolla''.

AVL-puu on nimetty keksijöidensä [[Georgi Adelson-Velski]]n ja [[Jevgeni Landis]]in mukaan. He esittelivät puun vuonna [[1962]] artikkelissaan ''”An algorithm for the organization of information”''.

== Tasapainokerroin ==
[[Solmu (tietojenkäsittelytiede)|Solmun]] '''tasapainokerroin''' on sen oikeanpuoleisen alipuun korkeus vähennettynä vasemmanpuoleisen alipuun korkeudella. Solmu jonka tasapainokerroin on -1, 0 tai 1 on tasapainoinen. Solmu jonka tasapainokerroin on jokin muu arvo on epätasapainossa ja vaati tasapainotuksen. Tasapainokerroin voidaan tallettaa jokaiseen solmuun tai se voidaan laskea suoraan alipuista.

=== Lisäys ===
Lisäys AVL-puuhun tehdään lisäämällä alkio puuhun samalla tavalla kuin [[binäärinen hakupuu|binääriseen hakupuuhun]]. Samalla puun solmujen tasapainokertoimia päivitetään. Jos jokin puun solmu menee epätasapainoon suoritetaan [[kierto]] alimmassa epätasapainoisessa solmussa, jolloin puu saadaan taas tasapainoon.

=== Poisto ===
Poisto AVL-puusta voidaan tehdä kiertämällä poistettava solmu lehtisolmuksi ja sitten poistaa se.

=== Haku ===
Haku tehdään kuten tavallisessa binääripuussa. Koska AVL-puu on aina tasapainossa on haun aikavaatimus aina <math>O(\log n)</math>.

== Katso myös ==
* [[Punamusta puu]]

== Aiheesta muualla ==
{{Commonscat-rivi}}

[[Luokka:Tietorakenteet]]
[[Luokka:Hakualgoritmit]]