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