Rememember this rule: When you insert x into a tree T that does not already contain x, key x is always put in a new leaf.
