import java.util.Scanner;

class Node {
    int value;
    Node left, right;

    public Node(int item) {
        value = item;
        left = right = null;
    }
}

class DrzewoBin {
    Node root;

    DrzewoBin() {
        root = null;
    }

    void insert(int wartosc) {
        root = insertRekurencyjnie(root, wartosc);
    }

    Node insertRekurencyjnie(Node node, int wartosc) {
        if (node == null) {
            node = new Node(wartosc);
            return node;
        }

        if (wartosc < node.value)
            node.left = insertRekurencyjnie(node.left, wartosc);
        else if (wartosc > node.value)
            node.right = insertRekurencyjnie(node.right, wartosc);

        return node;
    }

    void printPostorder() {
        printPostorderRekurencyjnie(root);
    }

    void printPostorderRekurencyjnie(Node node) {
        if (node == null)
            return;

        printPostorderRekurencyjnie(node.left);
        printPostorderRekurencyjnie(node.right);
        System.out.print(node.value + " ");
    }

    int height(Node node) {
        if (node == null)
            return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;
        x.right = y;
        y.left = T2;
        return x;
    }

    Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;
        y.left = x;
        x.right = T2;
        return y;
    }

    Node balance(Node node) {
        int balanceFactor = height(node.left) - height(node.right);

        if (balanceFactor > 1) {
            if (height(node.left.left) >= height(node.left.right)) {
                return rotateRight(node);
            } else {
                node.left = rotateLeft(node.left);
                return rotateRight(node);
            }
        } else if (balanceFactor < -1) {
            if (height(node.right.right) >= height(node.right.left)) {
                return rotateLeft(node);
            } else {
                node.right = rotateRight(node.right);
                return rotateLeft(node);
            }
        }

        return node;
    }

    Node balanceTree(Node node) {
        if (node == null)
            return null;

        node.left = balanceTree(node.left);
        node.right = balanceTree(node.right);

        return balance(node);
    }

    public static void main(String[] args) {
        DrzewoBin drzewo = new DrzewoBin();
        Scanner scanner = new Scanner(System.in);
        System.out.println("Wprowadź elementy drzewa oddzielone spacjami:");

        // Wczytywanie elementów drzewa z konsoli
        String input = scanner.nextLine();
        String[] elements = input.split("s+");

        // Dodawanie elementów do drzewa
        for (String element : elements) {
            drzewo.insert(Integer.parseInt(element));
        }

        System.out.println("Zawartość drzewa przed dodaniem niezrównoważonych elementów:");
        drzewo.printPostorder();

        // Dodawanie niezrównoważonych elementów
        drzewo.insert(9);
        drzewo.insert(10);

        System.out.println("nZawartość drzewa po dodaniu niezrównoważonych elementów:");
        drzewo.printPostorder();

        // Balansowanie drzewa
        drzewo.root = drzewo.balanceTree(drzewo.root);

        System.out.println("nDrzewo zostało zbalansowane:");
        System.out.println("nZawartość drzewa po zbalansowaniu:");
        drzewo.printPostorder();
    }
}