import java.util.Random;

public class Main {
    public static void main(final String[] args) {
        Tree t = Tree.leaf;

        for (final int i : sfl(seq(32), new java.util.Random()))
            t = t.add(i);
        
        t.dump();
    }

    public static int[] seq(final int c) {
        final int[] a = new int[c];
        for (int i = 0; i < c; i++)
            a[i] = i;
        return a;
    }

    public static int[] sfl(final int[] a, final Random r) {
        for (int i = a.length; i > 0; i--)
            swap(a, i - 1, r.nextInt(i));
        return a;
    }

    public static void swap(final int[] a, final int i, final int j) {
        final int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

abstract class Tree {
    public static final Leaf leaf = Leaf.instance;
    
    public abstract Tree add(int v);
    public abstract Tree del(int v);
    public abstract void dump();
    protected abstract Result add_(int v);
    protected abstract Result del_(int v);
    protected abstract Tree getLeft();
    protected abstract Tree getRight();
    protected abstract int getValue();
    protected abstract int getHeight();
    protected abstract void dump_(String s);
}

class Leaf extends Tree {
    public static final Leaf instance = new Leaf();

    private Leaf() {

    }

    @Override
    public Tree add(final int v) {
        return add_(v).node;
    }

    @Override
    protected Result add_(final int v) {
        return new Result(false, new Node(v, 1, this, this));
    }

    @Override
    public Tree del(final int v) {
        return del_(v).node;
    }

    @Override
    protected Result del_(final int v) {
        throw new RuntimeException("not found");
    }

    @Override
    protected Tree getLeft() {
        throw new RuntimeException("not implement");
    }

    @Override
    protected Tree getRight() {
        throw new RuntimeException("not implement");
    }

    @Override
    protected int getValue() {
        throw new RuntimeException("not implement");
    }

    @Override
    protected int getHeight() {
        return 0;
    }

    @Override
    public void dump() {
        dump_("");
    }

    @Override
    protected void dump_(final String s) {
    }
}

class Result {
    final boolean balanced;
    final Tree node;

    public Result(final boolean b, final Tree n) {
        balanced = b;
        node = n;
    }
}

class Node extends Tree {
    final int value;
    final int height;
    final Tree left;
    final Tree right;

    public Node(final int v, final int h, final Tree l, final Tree r) {
        value = v;
        height = h;
        left = l;
        right = r;
    }

    @Override
    protected Tree getLeft() {
        return left;
    }

    @Override
    protected Tree getRight() {
        return right;
    }

    @Override
    protected int getValue() {
        return value;
    }

    @Override
    protected int getHeight() {
        return height;
    }

    @Override
    public Tree add(final int v) {
        return add_(v).node;
    }

    @Override
    protected Result add_(final int v) {
        if (v < value)
            return addFixL(left.add_(v));
        else if (v > value)
            return addFixR(right.add_(v));
        else
            throw new RuntimeException("not implement");
    }

    @Override
    public Tree del(final int v) {
        return del_(v).node;
    }

    @Override
    protected Result del_(final int v) {
        if (value == v) {
            if (left == Leaf.instance)
                return new Result(false, right);
            else if (right == Leaf.instance)
                return new Result(false, left);
            else
                return (new Node(((Node) right).minValue(), height, left, right)).delFixR(((Node) right).delMin());
        } else if (v < value)
            return delFixL(left.del_(v));
        else
            return delFixR(right.del_(v));
    }

    private int minValue() {
        if (left == Leaf.instance)
            return value;
        else
            return ((Node) left).minValue();
    }

    private Result delMin() {
        if (left == Leaf.instance)
            return new Result(false, right);
        else
            return delFixL(((Node) left).delMin());
    }

    private Result addFixL(final Result r) {
        final Node n = new Node(value, height, r.node, right);
        if (r.balanced)
            return new Result(true, n);
        else {
            final Node nn = n.fixL_(0, 1);
            return new Result(nn.left.getHeight() == nn.right.getHeight(), nn);
        }
    }

    private Result addFixR(final Result r) {
        final Node n = new Node(value, height, left, r.node);
        if (r.balanced)
            return new Result(true, n);
        else {
            final Node nn = n.fixR_(0, 1);
            return new Result(nn.left.getHeight() == nn.right.getHeight(), nn);
        }
    }

    private Result delFixR(final Result r) {
        final Node n = new Node(value, height, left, r.node);
        if (r.balanced)
            return new Result(true, n);
        else {
            final Node nn = n.fixL_(-1, 0);
            return new Result(nn.left.getHeight() != nn.right.getHeight(), nn);
        }
    }

    private Result delFixL(final Result r) {
        final Node n = new Node(value, height, r.node, right);
        if (r.balanced)
            return new Result(true, n);
        else {
            final Node nn = n.fixR_(-1, 0);
            return new Result(nn.left.getHeight() != nn.right.getHeight(), nn);
        }
    }

    private Node fixR_(final int b, final int u) {
        switch (right.getHeight() - left.getHeight()) {
        case 0:
            return new Node(value, height + b, left, right);
        case 1:
            return new Node(value, height + u, left, right);
        case 2:
            return rotateLeft();
        default:
            throw new RuntimeException("invalid balance");
        }
    }

    private Node fixL_(final int b, final int u) {
        switch (left.getHeight() - right.getHeight()) {
        case 0:
            return new Node(value, height + b, left, right);
        case 1:
            return new Node(value, height + u, left, right);
        case 2:
            return rotateRight();
        default:
            throw new RuntimeException("invalid balance");
        }
    }

    private Node rotateRight() {
        final int h = right.getHeight();
        switch (left.getLeft().getHeight() - left.getRight().getHeight()) {
        case 1:
            return rotateRight1(h + 2, h + 1);
        case -1:
            return rotateRight2(h + 2, h + 1, h + 1);
        case 0:
            return rotateRight1(h + 3, h + 2);
        default:
            throw new RuntimeException("invalid balance");
        }
    }

    private Node rotateLeft() {
        final int h = left.getHeight();
        switch (right.getRight().getHeight() - right.getLeft().getHeight()) {
        case 1:
            return rotateLeft1(h + 2, h + 1);
        case -1:
            return rotateLeft2(h + 2, h + 1, h + 1);
        case 0:
            return rotateLeft1(h + 3, h + 2);
        default:
            throw new RuntimeException("invalid balance");
        }
    }

    private Node rotateLeft1(final int nh, final int lh) {
        return new Node(right.getValue(), nh, new Node(value, lh, left, right.getLeft()), right.getRight());
    }

    private Node rotateLeft2(final int nh, final int lh, final int rh) {
        final Node l = new Node(value, lh, left, right.getLeft().getLeft());
        final Node r = new Node(right.getValue(), rh, right.getLeft().getRight(), right.getRight());
        return new Node(right.getLeft().getValue(), nh, l, r);
    }

    private Node rotateRight1(final int nh, final int rh) {
        return new Node(left.getValue(), nh, left.getLeft(), new Node(value, rh, left.getRight(), right));
    }

    private Node rotateRight2(final int nh, final int lh, final int rh) {
        final Node l = new Node(left.getValue(), lh, left.getLeft(), left.getRight().getLeft());
        final Node r = new Node(value, rh, left.getRight().getRight(), right);
        return new Node(left.getRight().getValue(), nh, l, r);
    }

    @Override
    public void dump() {
        dump_("");
    }

    @Override
    protected void dump_(final String s) {
        right.dump_(s + "  ");
        System.out.println(s + value);
        left.dump_(s + "  ");
    }
}