Java Online

Main.java

ResetEraseRun

StdinOptional input fed to the program on stdin - one line per line.2 linesAlice 30

Output

Click Run to see the output here.

public class Main {
    static class Node {
        int key, height = 1;
        Node left, right;
        Node(int key) { this.key = key; }
    }

    static int height(Node n) { return n == null ? 0 : n.height; }
    static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }
    static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }

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

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

    static Node insert(Node node, int key) {
        if (node == null) return new Node(key);
        if (key < node.key) node.left = insert(node.left, key);
        else node.right = insert(node.right, key);
        update(node);
        int b = balance(node);
        // Four imbalance cases: LL, RR, LR, RL
        if (b > 1 && key < node.left.key) return rotateRight(node);
        if (b < -1 && key > node.right.key) return rotateLeft(node);
        if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }
        if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }
        return node;
    }

    static void inorder(Node n, StringBuilder sb) {
        if (n == null) return;
        inorder(n.left, sb);
        sb.append(n.key).append(" ");
        inorder(n.right, sb);
    }

    public static void main(String[] args) {
        Node root = null;
        int[] keys = {10, 20, 30, 40, 50, 25};
        for (int k : keys) root = insert(root, k);
        StringBuilder sb = new StringBuilder();
        inorder(root, sb);
        System.out.println("Inorder: " + sb.toString().trim());
        System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");
    }
}