Ero sivun ”AVL-puu” versioiden välillä
[katsottu versio] | [katsottu versio] |
p Removing Link GA template (handled by wikidata) |
Pieniä korjauksia ulkoasuun |
||
Rivi 1: | Rivi 1: | ||
[[Tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''AVL-puu''' on [[binäärinen hakupuu]]. Se on ensimmäinen tietojenkäsittelytieteessä esitetty itsestään tasapainottuva |
[[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 |
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”''. |
||
⚫ | |||
⚫ | |||
[[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. |
[[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 === |
||
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. |
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 === |
||
Poisto AVL-puusta voidaan tehdä kiertämällä poistettava solmu lehtisolmuksi ja sitten poistaa se. |
Poisto AVL-puusta voidaan tehdä kiertämällä poistettava solmu lehtisolmuksi ja sitten poistaa se. |
||
===Haku=== |
=== Haku === |
||
⚫ | |||
⚫ | |||
== Katso myös == |
== Katso myös == |
||
⚫ | |||
== Aiheesta muualla == |
|||
⚫ | |||
{{Commonscat-rivi}} |
|||
[[Luokka:Tietorakenteet]] |
[[Luokka:Tietorakenteet]] |
Versio 23. helmikuuta 2022 kello 12.42
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 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-Velskin ja Jevgeni 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 .
Katso myös
Aiheesta muualla
- Kuvia tai muita tiedostoja aiheesta AVL-puu Wikimedia Commonsissa