public Node put(Node x, Key k, Value v) {
        if (x == null) {
            return new Node(k, v, COLOR.RED);
        }

        int cmp = k.compareTo(root.key);
        if (cmp < 0) {
            x.left = put(x.left, k, v);
        }
        else if (cmp > 0) {
            x.right = put(x.right, k, v);
        }
        else {
            x.value = v;
        }

        // 3 cases
        // left black, right red : rotateleft
        // left red, left-left red: rotateright
        // left red, right red: flip color
        if(isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if(isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if(isRed(x.left) && isRed(x.right)) flipColors(x);
        
        return x;

    }