Project 2
Deadline: March 26 @ 12 Noon

AVL Trees
- Required balance: Balance factor
  * The height of the subtrees of any node can't differ by more than 1.
- Underlying operations, cf. insertion, search, and deletion work exactly as with BST initially.
  * Difference is that following the BST operation, the tree may need to be rebalanced.
    + Accomplished via rotation
- A tree can be out of balance in multiple nodes. We work bottom to top and correct the first node found that's out of balance.
- Which rotation?
  * Outside-in is single
  * Inside out requires double
  * How to tell:
    + On the left subtree if the unbalanced node is  to the left of its parent, single; to the right, double
      Symmetric to the right subtree
- Deletion may ripple, i.e. one necessary rotation may cause an imbalance higher up.