public void insert(K key, V value) {
        //Make a new node so we don't need to later
        RBTreeNode<K, V> insertedNode = new RBTreeNode<K, V>(key, value, Color.RED, null, null);
        //If root is null, set the new node to root (inserting it as the only pair in the tree)
        if (root == null) {
            root = insertedNode;
        } else {
            //Start with current node being root
            RBTreeNode<K, V> node = root;
            //Loop down the tree until we've found the proper place
            while (true) {
                int cmp = key.compareTo(node.key);
                if (cmp == 0) {
                    //If the key was already in the tree, then replace it
                    //(We won't even need to rebalance!)
                    node.value = value;
                    return;
                } else if (cmp < 0) {
                    //If we're inserting to the left of a node with no left child...
                    if (node.left == null) {
                        //Then we'll insert it there, and re-balance in a bit.
                        node.left = insertedNode;
                        break;
                    } else {
                        //Otherwise, "recurse" on left child.
                        node = node.left;
                    }
                } else { //if (cmp > 0)
                    assert cmp > 0;
                    //If we're inserting to the right of a node with no right child...
                    if (node.right == null) {
                        //Insert it there, and rebalance later.
                        node.right = insertedNode;
                        break;
                    } else {
                        //Otherwise, recurse on right
                        node = node.right;
                    }
                }
            }
            //If we've exited the while loop here, then insertedNode has just been made the child of node
            //So we'll fix the parent.
            insertedNode.parent = node;
        }
        //Re-balance.
        insertCase1(insertedNode);
        //Complain if we've messed up.
        verifyProperties();
    }