private SplayTreeNode zig(SplayTreeNode node) {
        SplayTreeNode k1 = new SplayTreeNode(node);
        SplayTreeNode a = new SplayTreeNode(node.left);
        SplayTreeNode b = new SplayTreeNode(node.right);
        if (a.isNull())
            a.parent = k1;
        if (b.isNull())
            b.parent = k1;

        SplayTreeNode k2 = new SplayTreeNode(node.parent);
        SplayTreeNode k2Parent = k2.parent;
        SplayTreeNode c = new SplayTreeNode(node.parent.right);
        if (c.isNull())
            c.parent = k2;

        k2.left = b;

        k1.right = k2;

        b.parent = k2;
        k2.parent = k1;

        node = k1;
        node.parent = k2Parent;

        if (node.parent != null) {
            node.parent.left = node;
        }

        return node;
    }