AVL Trees -- Balancing Algorithms
An insertion can cause an AVL tree to become unbalanced in four cases:
1. An insertion into the left subtree of the left child of node alpha.
2. An insertion into the right subtree of the left child of node alpha.
3. An insertion into the left subtree of the right child of alpha.
4. An insertion into the right subtree of the right child of alpha.
Cases 1&4 are symmetrical, so the same algorithm (with minor variations) can be used to rebalance the tree. Likewise with cases 2&3.