You insert yesterday’s order IDs into a binary search tree because “search is O(log n).” The IDs come out of the CSV already sorted. After a million rows every lookup walks a million nodes. The ordering law was honest. Height was never a promise.
An AVL tree is a BST that rebalances after every insert and delete so no node’s two subtrees differ in height by more than one. Search stays a single path. The path stays short even when the keys arrive in order. Height, Big-O, and worst-case vs amortized live on the Data Structures Roadmap. This post is the extra law: balance factor, the four rotation cases, and why that strictness is a tax you do not always want to pay.
The invariant is height, not just order
A BST already says every left descendant is smaller and every right descendant is larger. AVL adds a second law on shape:
for every node:
|height(left) - height(right)| <= 1Empty is height -1, a leaf is height 0. A node whose children are a leaf and null has heights 0 and -1; the gap is 1, which is legal. A gap of 2 is a violation — fix it before the caller sees the tree. Every node must satisfy the law, not only the root, or a later search pays for a local stick.
The node is the BST node plus a cached height. Recomputing height from the leaves on every mutate is O(n). Storing it is O(1) to refresh after a child changes:
final class Node {
int key;
Node left;
Node right;
int height; // leaf starts at 0
Node(int key) {
this.key = key;
}
}
int height(Node n) {
return n == null ? -1 : n.height;
}
void updateHeight(Node n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}Note: Height is derived state. After every pointer rewrite — insert, delete, or rotation — call updateHeight on the nodes whose children changed, bottom up. A stale height is a silent invariant break: the next rotation will fire on the wrong node, or not fire at all.
Balance factor is the signed gap
Balance factor is height(left) - height(right). Legal nodes sit in {-1, 0, +1}: +2 is left-heavy, -2 is right-heavy. Zero is perfect local balance, not a requirement everywhere.
int balanceFactor(Node n) {
return n == null ? 0 : height(n.left) - height(n.right);
}After a BST insert or delete you walk back toward the root, refresh height, and read this number. The first ancestor whose factor is ±2 is where the layout broke. Only nodes on that path can change height, so you do not scan the tree; rebalance stays O(height), and the invariant keeps height itself O(log n).
Rotations are four names for two primitives
A rotation is not a sort. It lifts one child into the parent’s seat and hangs the parent on the other side, preserving inorder. Two primitives cover the four textbook names: a right rotation and a left rotation.
Right rotation — the left child x rises; y becomes x’s right child. Subtree T2 moves from x.right to y.left so BST order stays true:
y x
/ \ / \
x T3 => T1 y
/ \ / \
T1 T2 T2 T3Three pointer assignments, then height from the lowered node up:
Node rotateRight(Node y) {
Node x = y.left;
Node t2 = x.right;
x.right = y;
y.left = t2;
updateHeight(y);
updateHeight(x);
return x;
}Left rotation is the mirror. The right child y rises; x becomes y’s left child:
x y
/ \ / \
T1 y => x T3
/ \ / \
T2 T3 T1 T2Same three-assignment shape, mirrored:
Node rotateLeft(Node x) {
Node y = x.right;
Node t2 = y.left;
y.left = x;
x.right = t2;
updateHeight(x);
updateHeight(y);
return y;
}Update the lowered node first so the new root’s height is honest, then return that root so the parent can reattach. The four cases are where the extra height sits:
| Case | Extra height | Fix |
|---|---|---|
| LL (left-left) | Left child, left side | One rotateRight |
| RR (right-right) | Right child, right side | One rotateLeft |
| LR (left-right) | Left child, right side | rotateLeft on the left child, then rotateRight |
| RL (right-left) | Right child, left side | rotateRight on the right child, then rotateLeft |
LL and RR are “same-side” (a single rotation). LR and RL are “zigzag” (a double rotation): first make the heavy grandchild line up, then apply the matching single rotation.
Sorted inserts are the RR case in slow motion. Insert 10, then 20, then 30:
10 10 20
\ => \ => / \
20 20 10 30
\
30Node 10 has balance factor -2. Its right child 20 is also right-heavy. One left rotation restores the invariant. The BST order 10, 20, 30 did not change. Height did.
LR is the zigzag: insert 30, then 10, then 20. The extra node hangs off the inside of the left child, so left-rotate 10 first, then right-rotate 30:
30 30 20
/ / / \
10 => 20 => 10 30
\ /
20 10One single or double rotation at the first unbalanced ancestor is enough after an insert. Heights above that node return to what they were, so you can stop walking. Delete is harsher: shrinking a subtree can leave the next ancestor still off by two, so you may rotate at several nodes on the way up.
Insert is BST insert, then a walk back
Insert still searches until it falls off a null child and hangs a new leaf. Recursion makes the rebalance obvious: as each call returns, refresh height and, if the factor is ±2, apply the matching case.
Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
return node; // already present
}
updateHeight(node);
return rebalance(node);
}
Node rebalance(Node node) {
int bf = balanceFactor(node);
if (bf > 1 && balanceFactor(node.left) >= 0) {
return rotateRight(node); // LL
}
if (bf > 1 && balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left); // LR
return rotateRight(node);
}
if (bf < -1 && balanceFactor(node.right) <= 0) {
return rotateLeft(node); // RR
}
if (bf < -1 && balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right); // RL
return rotateLeft(node);
}
return node;
}The >= 0 / <= 0 tests on the child are what make the same helper safe after delete, when a child’s factor can be 0 and a single rotation is the correct choice.
Delete is the BST delete (leaf / one child / two children via inorder successor), then the same updateHeight + rebalance on the way up. A rotation after a shrink may not restore the old height, so you keep going to the root. The path is still short. The four cases above are insert and delete — there is no fifth rotation hiding in a problem number.
Stricter than red-black, on purpose
Red-black trees also keep a BST ordered and height O(log n). They do it with a looser shape: a red-black tree’s height can be up to about twice log n. An AVL tree’s height stays closer to log n — roughly a factor of 1.44 instead of 2. Lookups walk fewer edges. That is the whole point of the extra strictness.
The bill is mutations. AVL’s tighter invariant means you rotate more often than a red-black tree does on the same insert sequence. Insert still stops after one single or double rotation, but that rotation fires more frequently. Delete can rotate on every step of the path. Red-black spends more of its fixup on color flips, which are cheaper than pointer rewrites, and it tolerates a skinnier tree between mutations.
Reach for AVL when the hot path is search, and you are implementing the tree yourself — a read-heavy ordered index, a teaching implementation, a layout where you want the tightest height you can still restore in O(log n). Reach for red-black when the hot path is mixed inserts and deletes and you want fewer structural changes per write.
Java has no java.util.AVL
There is no AVL type in the JDK. TreeMap and TreeSet are red-black. If you needed an ordered map in production Java, you already had one, and it is not the Node class above.
NavigableMap<Integer, String> orders = new TreeMap<>();
orders.put(42, "paid");
orders.put(7, "pending");
orders.put(19, "packed");
// 7, 19, 42 — sorted keys, log n per mutate, red-black under the hoodRolling your own AVL is for learning the invariant, for an interview whiteboard, or for a read-heavy ordered structure the JDK does not ship. It is not the default sorted map.
Note: TreeMap is still a tree of objects, not a contiguous array. It wins on order-plus-log-n, not on cache scans. If the job is “sort once and binary-search a list,” a sorted ArrayList can be cheaper. Match the hot operation, as the roadmap asks.
When not to use an AVL tree
Skip AVL when:
- You are writing production Java and need sorted keys —
TreeMap/TreeSetare red-black. There is nojava.util.AVL. Hand-rolling rotations to “be more balanced than the JDK” is almost never the win you think it is. - The workload is write-heavy. AVL rotates more often than red-black on insert, and delete can rebalance all the way to the root. If mutations dominate lookups, the looser balancer is the cheaper layout.
- You do not need order. Lookup-only uniqueness is a hash table’s job. AVL’s comparisons, heights, and rotations are a tax you are not spending.
nis tiny. A list and a linear scan will beat a balanced tree of twenty objects. Log n is not a reason to celebrate twenty pointers.- The data lives on disk. Databases use wide, page-sized nodes (B-trees), not binary AVL nodes. A disk round-trip is the expensive operation; packing more keys per page beats a tighter binary height.
Use AVL when you implement an ordered tree and lookups dominate: you want the strictest height guarantee a binary node can give, and you are willing to pay extra rotations on write. If the sentence does not mention order, you wanted a hash table. If it mentions order and you are in the JDK, you wanted TreeMap.
How to read the bill
Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path.
Structure: AVL tree
search O(log n) — height is strictly bounded
insert O(log n) — BST walk + at most one single/double rotation
delete O(log n) — may rotate at several ancestors
inorder O(n) — still a BST; the walk is sorted
min / max O(log n) — leftmost / rightmost
space O(n) — two child pointers + a height per keyAVL puts a ceiling on height. The extra field and the rotations are the cost of that ceiling.
Cheat sheet
Invariant: BST order + |h(left) - h(right)| <= 1 at every node
BF: h(left) - h(right); legal in {-1, 0, +1}
Height: cached on the node; empty = -1; leaf = 0
LL / RR: same-side; one rotation
LR / RL: zigzag; rotate the child, then the node
Insert: BST insert, then rebalance; at most one double rotation
Delete: BST delete, then rebalance up the path
Vs RB: tighter height, more rotations on write
JDK: no java.util.AVL; TreeMap / TreeSet are red-black
Skip: production sorted map (TreeMap); write-heavy; no order (hash)Do:
- Cache height and refresh it after every pointer rewrite.
- Treat the four rotation cases as one local fix, not a problem catalog.
- Use
TreeMapwhen production Java needs ordered keys.
Don’t:
- Quote O(log n) on a BST you never rebalance and call it AVL.
- Hand-roll AVL to beat
TreeMapon a mixed read/write map. - Use a tree when a hash table would do and you never iterate in key order.
Wrap-up
An AVL tree is a BST with a height law: no node is allowed to lean by more than one. Balance factor is that lean as a signed integer. LL, RR, LR, and RL are four pictures of two rotations that restore the law without breaking order. Insert pays at most one double rotation. Delete may keep rotating on the way up. Lookups stay O(log n) even on sorted input — that is the guarantee a plain BST does not make.
The guarantee is stricter than red-black, so writes rotate more often. Java does not ship an AVL type; TreeMap is red-black on purpose. Implement AVL when you need the tight height and you own the node. Reach for the JDK map when you need the job.
For the glossary behind height, worst-case, and “what operation is hot,” stay on the Data Structures Roadmap.