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
Insertion
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
Deletion
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