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

1 061 merkkiä poistettu ,  16 vuotta sitten
[arvioimaton versio][arvioimaton versio]
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:
<pre>
D
/ \
/ \
B E
/ \
A C
</pre>
voidaan kiertää muotoon:
<pre>
B
/ \
/ \
A D
/ \
C E
</pre>
 
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:
 
<pre>
F
/ \
/ \
B G
/ \
A D
/ \
C E
</pre>
Kierretään vasemmalle vasen lapsisolmu (B).
<pre>
F
/ \
/ \
D G
/ \
B E
/ \
A C
</pre>
Kierretään oikealle solmu itse (D).
<pre>
D
/ \
/ \
B E
/ \ / \
A C F G
</pre>
 
== Katso myös ==
Rekisteröitymätön käyttäjä