AVL Tree: The Self-Balancing Binary Search Tree
- AVL trees guarantee O(log n) height by maintaining the balance factor invariant after every operation.
- Balance factor = height(left) - height(right) — must be -1, 0, or 1.
- Four rotation cases handle all imbalance scenarios: LL, RR, LR, RL.
An AVL tree is a self-balancing BST where the height difference between left and right subtrees of any node is at most 1 (the balance factor). After every insertion or deletion, the tree rebalances using rotations. This guarantees O(log n) search, insert, and delete — a BST can degrade to O(n) without balancing.
How AVL Trees Work — Plain English and Rotations
An AVL tree is a self-balancing BST that maintains the invariant: for every node, |height(left) - height(right)| <= 1 (balance factor in {-1, 0, 1}). This guarantees O(log n) height, giving O(log n) search, insert, and delete.
After every insert/delete, the tree checks balance factors bottom-up. If any node becomes unbalanced (factor becomes -2 or 2), a rotation is applied.
Four rotation cases: 1. Left-Left (LL): right rotation on the unbalanced node. 2. Right-Right (RR): left rotation on the unbalanced node. 3. Left-Right (LR): left rotation on left child, then right rotation on node. 4. Right-Left (RL): right rotation on right child, then left rotation on node.
Worked example — insert 3, 2, 1 into AVL tree: Insert 3: [3]. BF(3)=0. Insert 2: [3, left=2]. BF(3)=-1. OK. Insert 1: [3, left=2, 2.left=1]. BF(3)=-2! Left-Left case. Right rotate at 3: 2 becomes root. 2.right=3. 2.left=1. 2 / \ 1 3 BF(2)=0, BF(1)=0, BF(3)=0. Balanced.
Balance Factor and Height
The fundamental invariant of an AVL tree is the Balance Factor (BF). BF = height(left subtree) - height(right subtree). For a tree to remain an AVL tree, every single node must have a BF of -1, 0, or +1. If a node hits +2 or -2, it is 'unbalanced' and requires immediate rotation.
In production code, we store the height in each node rather than recalculating it recursively to keep our operations at O(1) per node visited.
package io.thecodeforge.java.dsa; /** * Production-grade AVL Node structure. * Storing height explicitly avoids O(N) recalculations. */ public class AVLNode { public int key, height; public AVLNode left, right; public AVLNode(int key) { this.key = key; this.height = 1; // New nodes are leaves with height 1 } public static int getHeight(AVLNode node) { return (node == null) ? 0 : node.height; } public static int getBalanceFactor(AVLNode node) { return (node == null) ? 0 : getHeight(node.left) - getHeight(node.right); } public void updateHeight() { this.height = 1 + Math.max(getHeight(this.left), getHeight(this.right)); } }
The Four Rotation Cases
When a node becomes unbalanced, there are four possible configurations of the imbalance. Each has a specific rotation 'fix':
- Left-Left (LL): The left child's left subtree is too heavy. Fix: Single Right Rotation.
- Right-Right (RR): The right child's right subtree is too heavy. Fix: Single Left Rotation.
- Left-Right (LR): The left child's right subtree is too heavy. Fix: Left Rotate child, then Right Rotate parent.
- Right-Left (RL): The right child's left subtree is too heavy. Fix: Right Rotate child, then Left Rotate parent.
package io.thecodeforge.java.dsa; public class AVLUtility { public static AVLNode rotateRight(AVLNode y) { AVLNode x = y.left; AVLNode t2 = x.right; // Perform rotation x.right = y; y.left = t2; // Update heights in correct order (bottom-up) y.updateHeight(); x.updateHeight(); return x; // New root of subtree } public static AVLNode rotateLeft(AVLNode x) { AVLNode y = x.right; AVLNode t2 = y.left; // Perform rotation y.left = x; x.right = t2; // Update heights x.updateHeight(); y.updateHeight(); return y; // New root of subtree } public static AVLNode rebalance(AVLNode node) { node.updateHeight(); int balance = AVLNode.getBalanceFactor(node); // LL Case if (balance > 1 && AVLNode.getBalanceFactor(node.left) >= 0) return rotateRight(node); // LR Case if (balance > 1 && AVLNode.getBalanceFactor(node.left) < 0) { node.left = rotateLeft(node.left); return rotateRight(node); } // RR Case if (balance < -1 && AVLNode.getBalanceFactor(node.right) <= 0) return rotateLeft(node); // RL Case if (balance < -1 && AVLNode.getBalanceFactor(node.right) > 0) { node.right = rotateRight(node.right); return rotateLeft(node); } return node; } }
Insertion and Recursive Rebalancing
Insertion in an AVL tree follows standard BST logic, but as the recursion 'unwinds' (goes back up the tree), we call our rebalance function on every parent node. This ensures the entire path from the new leaf to the root is checked and fixed if needed.
package io.thecodeforge.java.dsa; public class AVLTree { private AVLNode root; public void insert(int key) { root = insertRecursive(root, key); } private AVLNode insertRecursive(AVLNode node, int key) { if (node == null) return new AVLNode(key); if (key < node.key) { node.left = insertRecursive(node.left, key); } else if (key > node.key) { node.right = insertRecursive(node.right, key); } else { return node; // Duplicate keys not allowed } // Rebalance during call stack unwinding return AVLUtility.rebalance(node); } public static void main(String[] args) { AVLTree tree = new AVLTree(); // Inserting sorted data that would break a normal BST int[] data = {10, 20, 30, 40, 50, 25}; for (int val : data) tree.insert(val); System.out.println("Tree Balanced. Root is: " + tree.root.key); } }
🎯 Key Takeaways
- AVL trees guarantee O(log n) height by maintaining the balance factor invariant after every operation.
- Balance factor = height(left) - height(right) — must be -1, 0, or 1.
- Four rotation cases handle all imbalance scenarios: LL, RR, LR, RL.
- Rotations are O(1) — they just update a few pointers.
- Use AVL trees when you need faster lookups (fewer levels than Red-Black); use Red-Black trees when you need faster insertions/deletions.
Interview Questions on This Topic
- QExplain the 'Balance Factor' of a node in an AVL tree. What are the permitted values for a tree to be considered balanced?
- QWalk through the 'Left-Right' (LR) rotation case. Why does it require two steps instead of one?
- QLeetCode Standard: Given a sorted array, convert it into a height-balanced BST. Why is the resulting tree effectively an AVL tree?
- QCompare the space complexity of an AVL tree vs. a standard BST. Does storing the 'height' variable change the Big O complexity?
- QIn what specific scenario would you choose a Red-Black tree over an AVL tree for a production system?
Frequently Asked Questions
What is the difference between an AVL tree and a Red-Black tree?
Both are self-balancing BSTs with O(log n) operations. AVL trees are more strictly balanced—the height is at most 1.44 log n. Red-Black trees allow slightly more imbalance (height up to 2 log n) but require fewer rotations during insertion and significantly fewer during deletion. Consequently, AVL trees are superior for search-heavy workloads (like a static dictionary), while Red-Black trees are better for general-purpose collections with frequent writes (like Java's TreeMap or C++'s std::map).
How many rotations does AVL insertion require compared to deletion?
Insertion requires at most one single or double rotation to restore balance for the entire tree. Deletion is more complex; a single deletion can trigger a 'cascade' of rotations all the way up to the root. This makes AVL deletion O(log n) in terms of rotations, whereas Red-Black deletion is O(1) (at most 3 rotations).
Can an AVL tree have a balance factor of 2?
Temporarily, yes. During the execution of an insertion or deletion, a node might reach a balance factor of +2 or -2. However, the AVL algorithm identifies this immediately and applies rotations to bring the balance factor back to the permissible range of [-1, 0, 1] before the operation completes.
Is an AVL tree always better than a Binary Search Tree?
In terms of search performance, yes. However, an AVL tree has higher overhead for each insertion and deletion due to rotation logic and height maintenance. For very small datasets or data that is already known to be inserted in a random distribution, a simple BST might be marginally faster due to less code complexity.
What is the difference between AVL trees and Red-Black trees?
AVL trees are more strictly balanced (height difference at most 1), giving faster lookups. Red-Black trees allow slightly less balance (height up to 2*log n) but require fewer rotations during insertions and deletions — faster writes. Practical rule: use AVL for read-heavy workloads, Red-Black (or just a library's balanced BST) for general use.
What is a rotation in an AVL tree?
A rotation changes the structure of the tree while preserving BST order. A right rotation on node A: A's left child B becomes the new root. A becomes B's right child. B's former right subtree becomes A's new left subtree. All BST properties are maintained because B < A and B's right subtree has values between B and A.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.