Ero sivun ”AVL-puu” versioiden välillä
[katsottu versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
p Removing Link GA template (handled by wikidata) |
Pieniä korjauksia ulkoasuun |
||
Rivi 1:
[[Tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''AVL-puu''' on [[binäärinen hakupuu]]. Se on ensimmäinen tietojenkäsittelytieteessä esitetty itsestään tasapainottuva
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
==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
▲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]]
|