What is an AVL Tree?
An AVL tree (named after Adelson-Velsky and Landis) is a self-balancing binary search tree. It maintains the BST property (left < root < right) and adds a balance constraint: for every node, the heights of its left and right subtrees differ by at most 1.
When an insertion or deletion violates this constraint, the tree automatically rebalances itself using rotations. This guarantees O(log n) height, which means O(log n) time for search, insert, and delete in all cases. No degenerate linked-list behavior like an unbalanced BST.
AVL Rotations Explained
There are four cases that trigger rotations, determined by where the imbalance occurs:
Left-Left (LL) Case
The unbalanced node's left child is left-heavy. Fix with a single right rotation. The left child becomes the new root, the old root becomes its right child, and the left child's right subtree moves to become the old root's left subtree.
Right-Right (RR) Case
Mirror of LL. The unbalanced node's right child is right-heavy. Fix with a single left rotation.
Left-Right (LR) Case
The unbalanced node's left child is right-heavy. Requires two rotations: first a left rotation on the left child (converting it to an LL case), then a right rotation on the unbalanced node.
Right-Left (RL) Case
Mirror of LR. The unbalanced node's right child is left-heavy. First a right rotation on the right child, then a left rotation on the unbalanced node.
AVL Tree Operations & Complexity
| Operation | Time | Description |
|---|---|---|
| Search | O(log n) | Same as BST. Guaranteed by balanced height. |
| Insert | O(log n) | BST insert + walk back up rebalancing (at most 1 rotation). |
| Delete | O(log n) | BST delete + walk back up rebalancing (may need multiple rotations). |
| Rotation | O(1) | Each rotation is a constant-time pointer swap. |
| Height | O(log n) | Strictly bounded: height ≤ 1.44 log₂(n+2). |
AVL Tree vs Red-Black Tree vs BST
| Property | AVL Tree | Red-Black Tree | Plain BST |
|---|---|---|---|
| Balance guarantee | Height diff ≤ 1 | Height ≤ 2x optimal | None |
| Search (worst) | O(log n) | O(log n) | O(n) |
| Insert rotations | ≤ 2 | ≤ 2 | 0 |
| Delete rotations | ≤ O(log n) | ≤ 3 | 0 |
| Best for | Read-heavy workloads | General purpose | Random data only |
Frequently Asked Questions
What is an AVL tree?add
An AVL tree is a self-balancing binary search tree where the height difference (balance factor) between the left and right subtrees of every node is at most 1. When an insertion or deletion violates this property, the tree is rebalanced using rotations. This guarantees O(log n) time for search, insert, and delete in all cases.
What are the four types of AVL rotations?add
The four rotation cases are: Left-Left (LL) fixed by a single right rotation, Right-Right (RR) fixed by a single left rotation, Left-Right (LR) fixed by a left rotation on the left child then a right rotation, and Right-Left (RL) fixed by a right rotation on the right child then a left rotation. The case is determined by where the imbalance and the triggering node are located.
What is the balance factor in an AVL tree?add
The balance factor of a node is the height of its left subtree minus the height of its right subtree. In a valid AVL tree, every node has a balance factor of -1, 0, or 1. A balance factor of +2 or -2 means the node is unbalanced and needs rotation to restore the AVL property.
What is the difference between AVL trees and red-black trees?add
Both are self-balancing BSTs, but AVL trees are more strictly balanced (height difference of at most 1 vs up to 2x for red-black trees). This makes AVL trees faster for lookups but slightly slower for insertions and deletions due to more frequent rotations. Red-black trees are used in most standard library implementations (Java TreeMap, C++ std::map) because they need fewer rotations on average.
When should I use an AVL tree?add
Use an AVL tree when you need guaranteed O(log n) lookups and your workload is read-heavy. The stricter balancing means shorter tree height and faster searches compared to red-black trees. For write-heavy workloads, red-black trees may perform better due to fewer rotations. In interviews, AVL trees are asked about to test understanding of tree rotations and balance maintenance.