[prev] [index] [next]

AVL Trees

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(depth(left)-depth(right)) > 1

This can be repaired by a single rotation:

  • if left subtree too deep, rotate right
  • if right subtree too deep, rotate left
Problem: determining height of subtrees may be expensive.