AVL-puu

Mureakuha

AVL-Puu on nimetty keksijoidensä Adelson, Velskii ja Landis mukaan. AVL-puu on binäärinen hakupuu, jossa on tasapainoehto. Puurakenteena se oli ensimmäinen tasapainoitettu puu (1962). Tasapainoehto takaa hakujen, lisäysten ja poistojen tapahtuvan O(log n) ajassa.

Tasapainoehto

Tasapainoehdon mukaan vasemman ja oikean alipuun korkeudet saavat poiketa toisistaan enintään yhdellä. Alkiolisäyksen jälkeen puun tasapainoasemaan saattamiseen tarvitaan enintään yksi kierto. Tasapaino-ominaisuutta pidetään yllä kierroilla (rotation). Kiertoja on neljä erilaista. Yksinkertainen kierto sekä kaksoiskierrot vasemmalle sekä oikealle. Alkiota poistaessa tasapainoa korjaavia kiertoja tarvitaan korkeintaan O(log n) kappaletta.

Linkit

• GNU libavl