private Node put(Node node, Key k, Value v) {
        if (node == null) {
            return new Node(k, v, 1, RED);
        }
        if (node.key.compareTo(k) > 0) {
            node.left = put(node.left, k, v);
        } else {
            node.right = put(node.right, k, v);
        }
        if (isRed(node.right) && !isRed(node.left)) {
            node =  rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }
        if (isRed(node.right) && isRed(node.left)) {
            flipColors(node);
        }
        return node;
    }