Ero sivun ”AVL-puu” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
p Lisätty linkki artikkeliin: Solmu (tietojenkäsittelytiede) |
p Botti lisäsi: da, de, es, fr, he, it, ja, lt, pl, pt, sk, sl, zh |
||
Rivi 81: | Rivi 81: | ||
[[Luokka:Tietorakenteet]] |
[[Luokka:Tietorakenteet]] |
||
[[da:AVL-træ]] |
|||
[[de:AVL-Baum]] |
|||
[[en:AVL tree]] |
[[en:AVL tree]] |
||
[[es:Árbol AVL]] |
|||
[[fr:Arbre AVL]] |
|||
[[it:Albero AVL]] |
|||
[[he:עץ AVL]] |
|||
[[lt:AVL medis]] |
|||
[[ja:AVL木]] |
|||
[[pl:Drzewo AVL]] |
|||
[[pt:Árvore AVL]] |
|||
[[sk:AVL strom]] |
|||
[[sl:AVL drevo]] |
|||
[[zh:AVL树]] |
Versio 16. maaliskuuta 2006 kello 17.54
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ä arvo puuhun samalla tavalla kuin tasapainottamattomaan binääripuuhun. Sen jälkeen uuden solmun isäsolmulle lasketaan tasapainokerroin. Jos puu ei ole tasapainossa suoritetaan puun kierto, jolla 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).
Kierto
Puu tasapainotetaan kiertämällä. Esimerkiksi seuraava puu:
D / \ / \ B E / \ A C
voidaan kiertää muotoon:
B / \ / \ A D / \ C E
Edelläoleva esimerkki on kierto oikealle. Vastaava operaatio päinvastoin on kierto vasemmalle.
Lisäksi puun tasapainottamiseksi voidaan tarvita kaksoiskiertoa oikealle tai kaksoiskiertoa vasemmmalle. Kaksoiskierto oikealle suoritetaan suorittamalla ensin kierto vasemalle vasemmanpuoleiselle lapsisolmulle ja sitten suorittamalla kierto oikealle solmulle itselleen. Seuraavassa esimerkissa tehdään solmulle (F) kaksoiskierto oikealle:
F / \ / \ B G / \ A D / \ C E
Kierretään vasemmalle vasen lapsisolmu (B).
F / \ / \ D G / \ B E / \ A C
Kierretään oikealle solmu itse (D).
D / \ / \ B E / \ / \ A C F G