1. import java.util.Scanner;
2.  
3. class Node {
4.     int value;
5.     Node left, right;
6.  
7.     public Node(int item) {
8.         value = item;
9.         left = right = null;
10.     }
11. }
12.  
13. class DrzewoBin {
14.     Node root;
15.  
16.     DrzewoBin() {
17.         root = null;
18.     }
19.  
20.     void insert(int wartosc) {
21.         root = insertRekurencyjnie(root, wartosc);
22.     }
23.  
24.     Node insertRekurencyjnie(Node node, int wartosc) {
25.         if (node == null) {
26.             node = new Node(wartosc);
27.             return node;
28.         }
29.  
30.         if (wartosc < node.value)
31.             node.left = insertRekurencyjnie(node.left, wartosc);
32.         else if (wartosc > node.value)
33.             node.right = insertRekurencyjnie(node.right, wartosc);
34.  
35.         return node;
36.     }
37.  
38.     void printPostorder() {
39.         printPostorderRekurencyjnie(root);
40.     }
41.  
42.     void printPostorderRekurencyjnie(Node node) {
43.         if (node == null)
44.             return;
45.  
46.         printPostorderRekurencyjnie(node.left);
47.         printPostorderRekurencyjnie(node.right);
48.         System.out.print(node.value + " ");
49.     }
50.  
51.     int height(Node node) {
52.         if (node == null)
53.             return 0;
54.         return 1 + Math.max(height(node.left), height(node.right));
55.     }
56.  
57.     Node rotateRight(Node y) {
58.         Node x = y.left;
59.         Node T2 = x.right;
60.         x.right = y;
61.         y.left = T2;
62.         return x;
63.     }
64.  
65.     Node rotateLeft(Node x) {
66.         Node y = x.right;
67.         Node T2 = y.left;
68.         y.left = x;
69.         x.right = T2;
70.         return y;
71.     }
72.  
73.     Node balance(Node node) {
74.         int balanceFactor = height(node.left) - height(node.right);
75.  
76.         if (balanceFactor > 1) {
77.             if (height(node.left.left) >= height(node.left.right)) {
78.                 return rotateRight(node);
79.             } else {
80.                 node.left = rotateLeft(node.left);
81.                 return rotateRight(node);
82.             }
83.         } else if (balanceFactor < -1) {
84.             if (height(node.right.right) >= height(node.right.left)) {
85.                 return rotateLeft(node);
86.             } else {
87.                 node.right = rotateRight(node.right);
88.                 return rotateLeft(node);
89.             }
90.         }
91.  
92.         return node;
93.     }
94.  
95.     Node balanceTree(Node node) {
96.         if (node == null)
97.             return null;
98.  
99.         node.left = balanceTree(node.left);
100.         node.right = balanceTree(node.right);
101.  
102.         return balance(node);
103.     }
104.  
105.     public static void main(String[] args) {
106.         DrzewoBin drzewo = new DrzewoBin();
107.         Scanner scanner = new Scanner(System.in);
108.         System.out.println("Wprowadź elementy drzewa oddzielone spacjami:");
109.  
110.         // Wczytywanie elementów drzewa z konsoli
111.         String input = scanner.nextLine();
112.         String[] elements = input.split("s+");
113.  
114.         // Dodawanie elementów do drzewa
115.         for (String element : elements) {
116.             drzewo.insert(Integer.parseInt(element));
117.         }
118.  
119.         System.out.println("Zawartość drzewa przed dodaniem niezrównoważonych elementów:");
120.         drzewo.printPostorder();
121.  
122.         // Dodawanie niezrównoważonych elementów
123.         drzewo.insert(9);
124.         drzewo.insert(10);
125.  
126.         System.out.println("nZawartość drzewa po dodaniu niezrównoważonych elementów:");
127.         drzewo.printPostorder();
128.  
129.         // Balansowanie drzewa
130.         drzewo.root = drzewo.balanceTree(drzewo.root);
131.  
132.         System.out.println("nDrzewo zostało zbalansowane:");
133.         System.out.println("nZawartość drzewa po zbalansowaniu:");
134.         drzewo.printPostorder();
135.     }
136. }
137.