AVL Trees
AVL Trees automatically rebalance themselves during insertions and deletions to guarantee logarithmic search times under all conditions.
The Balance Factor
An AVL tree — named for Adelson-Velsky and Landis, who described it in 1962 as the first self-balancing binary search tree — is a binary search tree that additionally enforces a height constraint at every node.
Each node's balance factor is height(left subtree) − height(right subtree). The AVL invariant is that this value must be −1, 0, or +1 for every node in the tree. A factor of +2 or −2 anywhere means the tree is out of balance and must be repaired immediately.
Using the convention that an empty subtree has height −1 and a leaf has height 0 makes the arithmetic work without special cases. Whichever convention you choose, apply it consistently — mixing them shifts every balance factor and produces spurious violations.
Each node stores its height (or, in some implementations, just the balance factor) so the value can be computed in O(1) rather than by traversing the subtree. Keeping this field correct after every structural change is where implementation bugs concentrate: a stale height silently disables rebalancing, and the tree degrades without any visible error.
The payoff is a hard guarantee. The invariant bounds the height at 1.44·log₂(n + 2) — at most about 44% taller than a perfectly balanced tree — so search, insert and delete are O(log n) in the worst case, not merely on average. An ordinary BST offers no such promise, and degenerates to O(n) on sorted input.
- Balance factor = left height − right height, allowed only in {−1, 0, +1}
- Store the height in each node so the check is O(1)
- A stale height field disables rebalancing silently
- Height bounded by 1.44·log₂(n+2), giving worst-case O(log n)
The Four Rotation Cases
A rotation is a local rearrangement of two or three nodes that changes the tree's shape while preserving the in-order sequence — and therefore the BST invariant. It is the only tool AVL trees use, and it runs in O(1).
After an insertion or deletion, walk back up toward the root. At the first node whose balance factor reaches ±2, apply the appropriate rotation. Which one depends on the shape of the path from that node down into the heavier side, giving exactly four cases.
Left-Left (LL): the node is left-heavy and its left child is also left-heavy. One right rotation at the unbalanced node fixes it.
Right-Right (RR): the mirror image — right-heavy with a right-heavy right child. One left rotation.
Left-Right (LR): left-heavy, but the left child is right-heavy. A single rotation does not help, because the offending subtree is on the inside. First rotate the left child left, converting the shape into LL, then rotate the node right. Two rotations.
Right-Left (RL): the mirror — right-heavy with a left-heavy right child. Rotate the right child right, then the node left.
The pattern is worth stating as a rule rather than four memorised diagrams: when the imbalance zigzags, straighten it first. The single rotations handle straight-line imbalances; the double rotations convert a zigzag into a straight line and then apply the single case.
Every rotation must update the heights of the nodes it moved, from the bottom up, or subsequent balance checks read stale values.
| Case | Shape | Fix |
|---|---|---|
| LL | Left-heavy, left child left-heavy | One right rotation |
| RR | Right-heavy, right child right-heavy | One left rotation |
| LR | Left-heavy, left child right-heavy | Left on the child, then right on the node |
| RL | Right-heavy, right child left-heavy | Right on the child, then left on the node |
- Rotations preserve in-order sequence, so the BST invariant survives
- Straight-line imbalance: one rotation. Zigzag: two
- Fix the lowest node whose balance factor reaches ±2
- Update heights after every rotation, bottom up
Insertion and Deletion Differ
Insertion proceeds as an ordinary BST insert, placing the new node as a leaf. Then the path back to the root is retraced, updating heights and checking balance factors.
The important property is that one rotation is always enough. A single rotation restores the subtree to the height it had before the insertion, so nothing above it can still be unbalanced — the retracing can stop immediately. Insertion therefore costs O(log n) to descend plus at most O(1) of rebalancing.
Deletion does not share this property, and the difference is the most commonly missed point about AVL trees. A rotation after deletion may leave the subtree shorter than it was, which can unbalance the node above, which may need its own rotation, and so on.
So deletion may require up to O(log n) rotations — potentially one at every level from the deleted node to the root. The retracing cannot stop at the first fix; it must continue upward until a node's height is unchanged by the repair.
The deletion itself follows the standard BST cases first: a leaf is removed directly, a node with one child is replaced by that child, and a node with two children is replaced by its inorder successor — the leftmost node of the right subtree — which is then deleted from that subtree. Rebalancing begins from the position where a node was physically removed, not from the node whose key was logically deleted.
That distinction causes real bugs: retracing from the wrong starting point skips the nodes whose heights actually changed.
- Insertion needs at most one rotation, then retracing can stop
- Deletion may need a rotation at every level up to the root
- A rotation after deletion can shorten the subtree, propagating upward
- Retrace from where a node was physically removed, not logically deleted
Terms, operations, and practical uses
Balance Mechanics
- Balance FactorCalculated as the height of the left subtree minus the height of the right subtree. Must be -1, 0, or 1.
- Height TrackingEach node actively stores its height, which is updated whenever its children are modified.
- Imbalance DetectionChecked on the path back to the root after an insertion/deletion. Triggered if a balance factor reaches +2 or -2.
Rotations
- Right Rotation (LL)Performed when a node is unbalanced due to an insertion in the left child's left subtree. The left child becomes the new root.
- Left Rotation (RR)Performed when a node is unbalanced due to an insertion in the right child's right subtree.
- Left-Right Rotation (LR)A double rotation (Left on child, Right on parent) used when the insertion is in the left child's right subtree.
Complexity
- SearchStrictly O(log N) because the height is mathematically guaranteed to be proportional to log(N).
- InsertionO(log N) to find the spot and update heights, requiring at most two rotations to rebalance.
- DeletionO(log N), but unlike insertion, a deletion might trigger O(log N) cascading rotations all the way to the root.
Repair an AVL tree with a right rotation
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(node):
return node.height if node else 0
def balance(node):
return height(node.left) - height(node.right) if node else 0
def rotate_right(y):
x = y.left
y.left = x.right
x.right = y
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x
class AVLTree:
def insert(self, root, key):
if not root:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(height(root.left), height(root.right))
# Left-left case: one right rotation restores the balance factor
if balance(root) > 1 and key < root.left.key:
return rotate_right(root)
return root
tree = AVLTree()
root = None
for key in (3, 2, 1):
root = tree.insert(root, key)
print('Root after rotation:', root.key)#include <iostream>
#include <algorithm>
using namespace std;
struct AVLNode {
int key, height;
AVLNode *left, *right;
explicit AVLNode(int key) : key(key), height(1), left(nullptr), right(nullptr) {
}
};
int height(AVLNode* node) {
return node ? node->height : 0;
}
int balance(AVLNode* node) {
return node ? height(node->left) - height(node->right) : 0;
}
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
y->left = x->right;
x->right = y;
y->height = 1 + max(height(y->left), height(y->right));
x->height = 1 + max(height(x->left), height(x->right));
return x;
}
class AVLTree {
public:
AVLNode* insert(AVLNode* node, int key) {
if (!node) return new AVLNode(key);
if (key < node->key) node->left = insert(node->left, key);
else node->right = insert(node->right, key);
node->height = 1 + max(height(node->left), height(node->right));
// Left-left case: one right rotation restores the balance factor
if (balance(node) > 1 && key < node->left->key) return rotateRight(node);
return node;
}
};
int main() {
AVLTree tree;
AVLNode* root = nullptr;
for (int key : {3, 2, 1}) root = tree.insert(root, key);
cout << "Root after rotation: " << root->key << '\n';
}public class Main {
static class Node {
int key, height = 1;
Node left, right;
Node(int key) {
this.key = key;
}
}
static int height(Node node) {
return node == null ? 0 : node.height;
}
static int balance(Node node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
static Node rotateRight(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y;
y.height = 1 + Math.max(height(y.left), height(y.right));
x.height = 1 + Math.max(height(x.left), height(x.right));
return x;
}
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);
node.height = 1 + Math.max(height(node.left), height(node.right));
// Left-left case: one right rotation restores the balance factor
if (balance(node) > 1 && key < node.left.key) return rotateRight(node);
return node;
}
public static void main(String[] args) {
Node root = null;
for (int key : new int[]{3, 2, 1}) root = insert(root, key);
System.out.println("Root after rotation: " + root.key);
}
}Step through it
Running on insert 3, 2, 1
Read all 12 Steps
- Insert 10 An empty AVL tree. Insert 10 as the root. Balance factor 0.
- Insert 20 20 > 10 so it becomes the right child. The root now leans right by one — still legal.
- Insert 30 30 goes right again. The root's right subtree is height 1 and its left is empty: balance factor -2. Illegal.
- Right-right case The imbalance is right-right: heavy on the right child's right side. A single left rotation fixes it.
- Rotate left 20 becomes the root; 10 becomes its left child. Height drops from 2 to 1 and every balance factor is 0 again.
- Insert 25 25 > 20 so go right, then 25 < 30 so go left. It lands as 30's left child.
- Still balanced The root leans right by one, which AVL permits. No rotation needed yet.
- Insert 27 27 goes right of 20, left of 30, right of 25. Now 30 has balance factor +2 — illegal.
- Left-right case 30 is left-heavy but the new node went right of 25. A single rotation would not fix this shape.
- First rotation Rotate 25 left so 27 takes its place. The shape becomes left-left, which a single rotation can handle.
- Second rotation Now rotate 30 right. 27 rises, taking 25 and 30 as its children.
- Balanced again Every node's two subtrees differ in height by at most 1. Both rotations were O(1) pointer swaps, so insertion stays O(log n).
AVL Against Red-Black
Both are self-balancing binary search trees offering O(log n) worst-case operations, and the choice between them is a genuine engineering trade rather than one being better.
AVL is more strictly balanced. Its height bound is 1.44·log₂ n against red-black's 2·log₂ n, so an AVL tree is meaningfully shorter — which means fewer comparisons and fewer cache misses per lookup. For read-heavy workloads, AVL wins.
Red-black rebalances less. Its looser invariant tolerates more imbalance before intervening, and much of its repair work is recolouring — changing a bit — rather than rotating. Insertion needs at most 2 rotations and deletion at most 3, both constant, against AVL's potential O(log n) rotations on deletion. For write-heavy workloads, red-black wins.
This is why standard libraries almost universally choose red-black: std::map and std::set in C++, TreeMap and TreeSet in Java, and the Linux kernel's scheduler and memory management. A general-purpose container cannot assume a read-heavy workload, so the cheaper worst-case modification cost is the safer default.
AVL trees appear where lookups dominate and updates are rare — in-memory database indexes built once and queried repeatedly are the usual example.
There is also a maintenance dimension worth noting: AVL logic is generally considered easier to reason about and to implement correctly, since the four rotation cases are symmetric and the invariant is a simple numeric check. Red-black insertion and deletion involve more cases and are correspondingly more error-prone to write from scratch.
| AVL | Red-black | |
|---|---|---|
| Height bound | 1.44·log₂ n | 2·log₂ n |
| Lookup speed | Faster — shorter tree | Slower |
| Rotations on insert | ≤ 1 | ≤ 2 |
| Rotations on delete | O(log n) | ≤ 3 |
| Best for | Read-heavy workloads | General purpose |
| Used by | In-memory indexes | std::map, TreeMap, Linux kernel |
- AVL is shorter, so lookups are faster
- Red-black rebalances less, so modifications are cheaper
- Deletion is the asymmetry: O(log n) rotations against at most 3
- Libraries default to red-black; AVL suits read-heavy use