Ero sivun ”AVL-puu” versioiden välillä

53 merkkiä lisätty ,  9 kuukautta sitten
Pieniä korjauksia ulkoasuun
[katsottu versio][katsottu versio]
p (Removing Link GA template (handled by wikidata))
(Pieniä korjauksia ulkoasuun)
[[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.”information”''.
 
==Tasapainokerroin==
 
== 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>.
 
Haku tehdään kuten tavallisessa binääripuussa. Koska AVL-puu on aina tasapainossa on haun aikavaatimus aina ''O''(log ''n'').
 
 
 
== Katso myös ==
* [[Punamusta puu]]
 
== Aiheesta muualla ==
* [[Punamusta puu]]
{{Commonscat-rivi}}
 
[[Luokka:Tietorakenteet]]