AVL and Red-Black Trees
In short: an AVL tree rebalances after every insert so that for
every node, the heights of its two subtrees never differ by more than 1 —
its balance factor (bf = height(left) - height(right)) always stays
in {-1, 0, 1}. An insert can push several ancestors' bf to ±2 at once,
but fixing the lowest unbalanced one with one of four rotation
recipes — LL, LR, RR or RL — restores that subtree to its pre-insert
height, which makes every ancestor above it balanced again too. A
red-black tree relaxes the rule (a looser "never more than twice as
deep on one side") and fixes violations with cheaper recolouring most
of the time, trading a slightly taller tree for fewer rotations per insert.
Keeping a leaderboard fast after a losing streak
A game's leaderboard indexes players by score. Scores update constantly, and a bad run of matches can insert a long streak of similar, nearly-sorted scores — exactly the pattern that degrades a plain BST. An AVL-backed index keeps lookups at O(log n) no matter how the scores arrive, by checking the balance factor after every single insert and fixing it immediately if it's broken.
bf(70) comes out -1 — its right child 90 makes that side one level
taller — and that extra level echoes up to the root: bf(50) is -1 too,
while bf(30), a leaf, is still 0. None of these cross ±2 yet, so no
rotation fires. That's the check an AVL insert runs after every single
node on its way back up, not just at the root.
An order book sorted by price
A trading system keeps active buy orders in a structure sorted by price, so it can answer "what's the best bid right now?" in O(1) and insert a new order in O(log n). Order arrivals cluster — a price move brings a burst of orders near the same level — which is exactly the nearly-sorted pattern that needs rebalancing, not just balancing once at startup.
The mistake people actually make implementing this: forgetting to call
update(node) on the way back up, so every node's own height silently
stays frozen at its initial value of 1 — which means bf() never sees a
real imbalance, and rotations simply never fire.
This prints 1 (the root's height never updated past its initial value) instead of 3, the real AVL height for 5 descending inserts. Add the missing `update(node)` call.
The four shapes, and why there are exactly four
An insert can leave several ancestors on its path with bf at ±2 at
once — not just the nearest one. But fixing the lowest unbalanced
ancestor first restores that whole subtree to the height it had before
the insert, so every ancestor above it sees no height change at all, and
needs no fix of its own. One rotation (or two, for a zigzag) is always
enough for the entire path, applied once, at the lowest violation.
Which of the four shapes applies depends only on that lowest node's two children's relative heights. Heavy on the left, and the left child is itself left-heavy (or balanced) → LL. Heavy on the left, but the left child is right-heavy → LR, a zigzag needing two rotations. RR and RL mirror these on the right.
LL case. Node 3 has bf=1 before the insert lands under its left child, 2.
Before: 3's left subtree (through 2) is one level taller than its empty right side. Binary tree, 4 nodes, height 3.
RR case, mirroring LL on the right. Node 8 has bf=-1 before the insert lands under its right child, 9.
Before: 8's right subtree (through 9) is one level taller than its empty left side. Binary tree, 4 nodes, height 3.
LR and RL are the trickier pair — the imbalance is real, but a single rotation at the top would just rotate the zigzag sideways, not straighten it:
LR case. Node 3 has bf=1 before the insert lands as 1's RIGHT child — a zigzag, not a line.
Before: 3's left subtree (through 1) is one level taller. Binary tree, 4 nodes, height 3.
RL case, mirroring LR on the right. Node 8 has bf=-1 before the insert lands as 12's LEFT child — a zigzag.
Before: 8's right subtree (through 12) is one level taller. Binary tree, 4 nodes, height 3.
A real sequence, run for real
Here's every case, caught live, inserting 10, 20, 30, 25, 28, 5, 4 one at
a time:
Three of the four cases fire in this one short sequence: 30 triggers RR
at 10 (two ascending inserts in a row), 28 triggers LR at 30 (a
zigzag landing under 25), and 4 triggers LL at 10 (two descending
inserts). RL doesn't happen to come up here — see the viz above for it in
isolation — but the mechanism is identical: find the lowest unbalanced
node, read which shape its children make, apply the matching recipe.
Red-black recolouring: the cheaper alternative
AVL keeps the tightest possible balance (height ≤ ~1.44 log₂n), which
makes lookups a hair faster but can mean more rotations while inserting or
deleting. A red-black tree colours every node red or black and enforces
a looser rule instead: no red node has a red child, and every path from a
node to its descendant leaves passes through the same number of black
nodes. Fixing a violation after an insert is usually just recolouring a
parent and uncle red-to-black (O(1), no pointers move) and only escalates
to a rotation when recolouring alone can't fix it. The tree that comes out
can be up to twice as deep as an AVL tree in the worst case, but the
average insert is cheaper — which is why most language standard libraries
(C++'s map, Java's TreeMap) use red-black trees, not AVL.
| AVL | red-black | |
|---|---|---|
| balance rule | ` | bf |
| worst-case height | ~1.44 log2(n) |
~2 log2(n) |
| typical fix cost | 1–2 rotations | O(1) recolouring, rotation only sometimes |
| best for | read-heavy (lookups dominate) | write-heavy (inserts/deletes dominate) |
Quick practice
def rotation_case(bf_node, bf_child):
if bf_node > 1:
return "LL" if bf_child >= 0 else "LR"
if bf_node < -1:
return "RR" if bf_child <= 0 else "RL"
return "balanced"
print(rotation_case(2, -1), rotation_case(-2, 1))This prints 4 1 instead of 2 1 — x's height comes out far too tall because it was recalculated using y's old, pre-rotation height. Swap the order of the two update() calls.
What it costs
| operation | AVL | red-black |
|---|---|---|
| search | O(log n) | O(log n) |
| insert | O(log n), ≤ 2 rotations | O(log n), O(1) amortised recolouring |
| delete | O(log n), up to O(log n) rotations | O(log n), O(1) amortised recolouring |
| height bound for n nodes | ~1.44 log2(n+2) |
~2 log2(n+1) |
🎯 Your turn
Build avl_insert_sequence(values): insert values one at a time into an
AVL tree, rebalancing with rotations after every insert, and return
{"inorder": [...], "height": ...}.
avl_insert_sequence([1, 2, 3, 4, 5, 6, 7, 8])→{"inorder": [1, 2, 3, 4, 5, 6, 7, 8], "height": 4}avl_insert_sequence([3, 2, 1])→{"inorder": [1, 2, 3], "height": 2}
Hint: reuse insert, rotate_left, rotate_right, bf and update
from this lesson; after every insert, check the current node's balance
factor and fix LL/LR/RR/RL as it unwinds back up to the root.
Press ▶ Run, then ✓ Check.