Kierto
Wikipedia
Kierto on matemaattisessa verkkojen teoriassa mahdollinen operaatio. Kierron lajeja ovat esimerkiksi kierto vasemmalle, kierto oikealle sekä kaksoiskierto vasemmalle ja kaksoiskierto oikealle.
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 vasemmalle 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
