[prev] 40 [next]

AVL Trees

Invented by Georgy Adelson-Velsky and Evgenii Landis

Approach:

  • insertion (at leaves) may cause imbalance
  • repair balance as soon as we notice imbalance
  • repairs done locally, not by overall tree restructure
A tree is unbalanced when: abs(height(left)-height(right)) > 1

This can be repaired by at most two rotations:

  • if left subtree too deep …
    • if data inserted in left-right grandchild   ⇒ left-rotate left subtree
    • rotate right
  • if right subtree too deep …
    • if data inserted in right-left grandchild   ⇒ right-rotate right subtree
    • rotate left
Problem: determining height/depth of subtrees may be expensive.