Kierto

Kierto on operaatio puulle graafiteoriassa. Kierron lajeja ovat esimerkiksi kierto vasemmalle, kierto oikealle sekä kaksoiskierto vasemmalle ja kaksoiskierto oikealle.

Puu tasapainotetaan kiertämällä:

       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 vasemmalle. Kaksoiskierto oikealle suoritetaan suorittamalla ensin kierto vasemmalle vasemmanpuoleiselle lapsisolmulle ja sitten suorittamalla kierto oikealle solmulle itselleen. Seuraavassa esimerkissä 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     F
   / \   / \
  A   C E   G