| 1 | // AVL Tree · Java 17 · Tanmay Bohra |
| 2 | // Self-balancing Binary Search Tree |
| 3 | |
| 4 | public class AVLTree { |
| 5 | |
| 6 | // ── Node ───────────────────────────────── |
| 7 | static class Node { |
| 8 | int key, height; |
| 9 | Node left, right; |
| 10 | Node(int k) { |
| 11 | this.key = k; |
| 12 | this.height = 1; |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | // ── Helpers ────────────────────────────── |
| 17 | int height(Node n) { |
| 18 | return n == null ? 0 : n.height; |
| 19 | } |
| 20 | |
| 21 | int bf(Node n) { |
| 22 | return n == null ? 0 |
| 23 | : height(n.left) - height(n.right); |
| 24 | } |
| 25 | |
| 26 | void updateHeight(Node n) { |
| 27 | n.height = 1 + Math.max( |
| 28 | height(n.left), height(n.right)); |
| 29 | } |
| 30 | |
| 31 | // ── BST insert ──────────────────────────── |
| 32 | Node bstInsert(Node nd, int k) { |
| 33 | if (nd == null) |
| 34 | return new Node(k); |
| 35 | if (k < nd.key) |
| 36 | nd.left = bstInsert(nd.left, k); |
| 37 | else if (k > nd.key) |
| 38 | nd.right = bstInsert(nd.right, k); |
| 39 | return nd; |
| 40 | } |
| 41 | |
| 42 | // ── rotateRight (fixes LL) ─────────────── |
| 43 | Node rotateRight(Node y) { |
| 44 | Node x = y.left; |
| 45 | Node T2 = x.right; |
| 46 | x.right = y; |
| 47 | y.left = T2; |
| 48 | updateHeight(y); |
| 49 | updateHeight(x); |
| 50 | return x; |
| 51 | } |
| 52 | |
| 53 | // ── rotateLeft (fixes RR) ─────────────── |
| 54 | Node rotateLeft(Node x) { |
| 55 | Node y = x.right; |
| 56 | Node T2 = y.left; |
| 57 | y.left = x; |
| 58 | x.right = T2; |
| 59 | updateHeight(x); |
| 60 | updateHeight(y); |
| 61 | return y; |
| 62 | } |
| 63 | |
| 64 | // ── avlInsert (BST + rebalance) ────────── |
| 65 | Node avlInsert(Node nd, int k) { |
| 66 | if (nd == null) |
| 67 | return new Node(k); |
| 68 | if (k < nd.key) |
| 69 | nd.left = avlInsert(nd.left, k); |
| 70 | else if (k > nd.key) |
| 71 | nd.right = avlInsert(nd.right, k); |
| 72 | else return nd; |
| 73 | |
| 74 | updateHeight(nd); |
| 75 | int b = bf(nd); |
| 76 | |
| 77 | // LL — single right rotation |
| 78 | if (b > 1 && k < nd.left.key) |
| 79 | return rotateRight(nd); |
| 80 | // RR — single left rotation |
| 81 | if (b < -1 && k > nd.right.key) |
| 82 | return rotateLeft(nd); |
| 83 | // LR — left then right |
| 84 | if (b > 1 && k > nd.left.key) { |
| 85 | nd.left = rotateLeft(nd.left); |
| 86 | return rotateRight(nd); |
| 87 | } |
| 88 | // RL — right then left |
| 89 | if (b < -1 && k < nd.right.key) { |
| 90 | nd.right = rotateRight(nd.right); |
| 91 | return rotateLeft(nd); |
| 92 | } |
| 93 | return nd; |
| 94 | } |
| 95 | } |