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.
|