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

Wikipediasta
Siirry navigaatioon Siirry hakuun
[arvioimaton versio][arvioimaton versio]
Poistettu sisältö Lisätty sisältö
PipepBot (keskustelu | muokkaukset)
p Botti lisäsi: id:Pohon AVL
JAnDbot (keskustelu | muokkaukset)
p Botti muokkasi: sl:AVL-drevo
Rivi 42: Rivi 42:
[[ru:АВЛ-дерево]]
[[ru:АВЛ-дерево]]
[[sk:AVL strom]]
[[sk:AVL strom]]
[[sl:AVL drevo]]
[[sl:AVL-drevo]]
[[sv:AVL-träd]]
[[sv:AVL-träd]]
[[vi:Cây AVL]]
[[vi:Cây AVL]]

Versio 5. lokakuuta 2007 kello 10.58

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ä G.M. Adelson-Velskyn ja E.M. Landisin mukaan. He esittelivät puun vuonna 1962 artikkelissaan "An algorithm for the organization of information."

Tasapainokerroin

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ää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 O(log n).


Katso myös