An [http://en.wikipedia.org/wiki/AVL_tree AVL tree] is a binary search tree which maintains balance by clever use of rotation after updates.

For each node x:

- * Height(left subtree) and Height(right subtree) must differ by less than 1.
- * If the difference is greater than 1, a rotation is done

For an AVL tree, there are always at most 2 rotations after an insertion

- Insert the new value at a new leaf node
- Through a path from the new leaf back to the root:
- update heights
- if an imbalance has been created, perform a rotation

The case analysis for this is very messy…

- Delete the target node, replacing it with one of its children
- Through a path from the child back to the root:
- update heights
- if an imbalance has been created, perform a rotation