What you'll learn
A binary search tree is only fast when it's balanced. An AVL tree is a BST that keeps itself balanced after every insert and delete, using rotations — guaranteeing O(log n) forever.
By the end you'll be able to:
- Compute a node's balance factor
- Apply the four rotations (LL, RR, LR, RL) to restore balance
- Explain why AVL trees guarantee
O(log n)height
The balance factor
For every node, the balance factor is height(left) − height(right). An AVL tree keeps it in {−1, 0, +1} at every node. The moment an insertion pushes some node to ±2, the tree performs a rotation to fix it. Recall from Module 17 that a bad insertion order can make a plain BST degrade to a list — this is the cure.
The right-right case
Insert values that all go right, and a node becomes right-heavy by 2. A single left rotation rebalances it:
The left-right case
A "zig-zag" imbalance needs two rotations: first straighten it, then rotate as usual.
All four rotations
| Case | Shape | Fix |
|---|---|---|
Left-Left | Heavy on the left child's left | Single right rotation |
Right-Right | Heavy on the right child's right | Single left rotation |
Left-Right | Left child, but heavy on its right | Left rotation, then right |
Right-Left | Right child, but heavy on its left | Right rotation, then left |
Key idea
O(1) pointer rewrite that preserves the BST ordering. After an insert, you rebalance along the path back to the root — at most O(log n) work.In code
def rotate_left(x): # fixes a right-heavy node
y = x.right
x.right = y.left
y.left = x
update_height(x); update_height(y)
return y # y is the new subtree root
def rotate_right(y): # fixes a left-heavy node
x = y.left
y.left = x.right
x.right = y
update_height(y); update_height(x)
return x
def rebalance(node):
bf = balance(node) # height(left) - height(right)
if bf > 1 and balance(node.left) >= 0: # Left-Left
return rotate_right(node)
if bf > 1: # Left-Right
node.left = rotate_left(node.left)
return rotate_right(node)
if bf < -1 and balance(node.right) <= 0: # Right-Right
return rotate_left(node)
if bf < -1: # Right-Left
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeRecap & quick check
Key takeaways
- An AVL tree is a self-balancing BST: every node's balance factor stays in {−1, 0, +1}.
- Balance factor = height(left) − height(right).
- Four cases (LL, RR, LR, RL) are fixed by one or two rotations.
- A rotation is an O(1) pointer rewrite that preserves BST order.
- AVL trees guarantee O(log n) search, insert, and delete regardless of input order.
Quick check
1. What is a node's balance factor?
2. A right-right imbalance is fixed by:
3. Which case needs two rotations?
4. What does an AVL tree guarantee?
AVL trees are strictly balanced. The next self-balancing tree trades a little balance for faster updates — and it's the one inside your language's library. Next up: Module 19 — Red-Black Trees.