datastructures9AVLTree

1package pkg3datastructures;2 3/*4 * datastructures9AVLTree.java5 * ------------6 * A self-balancing BST. After each insert it rebalances using rotations so the7 * height stays O(log n), guaranteeing O(log n) operations even in the worst case.8 *9 * BALANCE FACTOR = height(left) - height(right), kept in {-1, 0, 1}.10 * ROTATIONS: LL (right rotate), RR (left rotate), LR, RL.11 */12import java.util.*;13 14public class datastructures9AVLTree {15 16    static class Node {17        int val, height = 1; Node left, right;18        Node(int val) { this.val = val; }19    }20 21    private Node root;22 23    private int h(Node n) { return n == null ? 0 : n.height; }24    private int balance(Node n) { return n == null ? 0 : h(n.left) - h(n.right); }25    private void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }26 27    private Node rotateRight(Node y) {28        Node x = y.left, t = x.right;29        x.right = y; y.left = t;30        update(y); update(x);31        return x;32    }33 34    private Node rotateLeft(Node x) {35        Node y = x.right, t = y.left;36        y.left = x; x.right = t;37        update(x); update(y);38        return y;39    }40 41    void insert(int v) { root = insert(root, v); }42    private Node insert(Node n, int v) {43        if (n == null) return new Node(v);44        if (v < n.val) n.left = insert(n.left, v);45        else if (v > n.val) n.right = insert(n.right, v);46        else return n;47 48        update(n);49        int bf = balance(n);50        // Four imbalance cases51        if (bf > 1 && v < n.left.val) return rotateRight(n);                 // LL52        if (bf < -1 && v > n.right.val) return rotateLeft(n);                // RR53        if (bf > 1 && v > n.left.val) { n.left = rotateLeft(n.left); return rotateRight(n); }   // LR54        if (bf < -1 && v < n.right.val) { n.right = rotateRight(n.right); return rotateLeft(n); } // RL55        return n;56    }57 58    void inorder(Node n, List<Integer> out) { if (n == null) return; inorder(n.left, out); out.add(n.val); inorder(n.right, out); }59 60    public static void main(String[] args) {61        datastructures9AVLTree avl = new datastructures9AVLTree();62        // Inserting sorted values would skew a normal BST; AVL stays balanced.63        for (int i = 1; i <= 7; i++) avl.insert(i);64 65        List<Integer> in = new ArrayList<>();66        avl.inorder(avl.root, in);67        System.out.println("in-order: " + in);68        System.out.println("root value: " + avl.root.val + " (balanced, not 1)");69        System.out.println("tree height: " + avl.root.height + " (log2(7)~3, vs 7 if skewed)");70    }71}