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

4 merkkiä lisätty ,  14 vuotta sitten
ei muokkausyhteenvetoa
[arvioimaton versio][arvioimaton versio]
Ei muokkausyhteenvetoa
Ei muokkausyhteenvetoa
[[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 aikavaatimus on O(log n) 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]] [[artikkelissa]]anartikkelissaan "An''”An algorithm for the organization of information."”''
 
===Tasapainokerroin===
20 551

muokkausta