AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 16
Self-Balancing Trees: AVL and Red-Black
If a BST can degenerate, make it repair itself. Rotations look like sleight of hand until you see one animated — then they are obvious and you never forget them.
By the end of this chapter you can
- Define the balance factor and use it to detect an imbalance
- Perform left and right rotations, and prove they preserve the in-order sequence
- Identify which of the four cases applies and apply the right one or two rotations
- Compare AVL and red-black trees, and say which to prefer for which workload
- Explain why real libraries ship red-black trees rather than AVL
1The problem, restated
Chapter 15 ended with a BST that had become a linked list. This chapter is the fix, and it is one operation.
Every BST operation is O(h). A balanced tree has
h = O(log n); a degenerate one has h = n - 1. Sorted input produces the
second, and sorted input is common.
A self-balancing tree notices when it is getting lopsided and restructures itself
— a little, cheaply, on every insertion and deletion — so that the height can never
exceed O(log n).
Whatever restructuring we do, it must preserve the BST property. The in-order sequence of the tree must come out identical, or search stops working.
So we need an operation that changes the shape without changing the order. That operation is the rotation, and there is essentially only one of them (plus its mirror).
2Rotation
Three pointers move. The height drops. The in-order sequence is untouched. That is the whole mechanism.
A hanging mobile with one arm loaded too heavily on the left. You do not remove anything or rearrange the objects — you take one join and pivot it, so the heavy arm's own pivot becomes the new top and the old top hangs off its side.
Same objects, same left-to-right order, lower and more even. That is a rotation.
Consider a right rotation at node Q, where P is its left child:
Q P
/ \ right rotate at Q / \
P C ───────────────▶ A Q
/ \ / \
A B B C
# In-order BEFORE: A P B Q C
# In-order AFTER: A P B Q C ← IDENTICAL
#
# That is not a coincidence. B was Q's-left-child's-right-subtree, meaning
# "greater than P, less than Q". After the rotation it is Q's left subtree,
# meaning "less than Q" — and it is still greater than P because it hangs
# below Q which hangs off P's right. Every constraint still holds.def rotate_right(q):
p = q.left
q.left = p.right # 1. B moves across to be Q's left child
p.right = q # 2. Q becomes P's right child
update_height(q) # 3. Q is now lower, so fix it FIRST
update_height(p) # then P, which depends on Q
return p # P is the new subtree root
def rotate_left(p):
q = p.right
p.right = q.left
q.left = p
update_height(p)
update_height(q)
return q
# Three pointer writes. O(1). No matter how large the subtrees are.After a rotation, q is below p. Its height must be
recomputed before p's, because p's height depends on it.
Getting that order wrong is the classic AVL bug: the tree stays correct as a BST but the balance factors go stale, so it silently stops rebalancing and quietly degenerates — which is exactly the failure you were trying to prevent.
3AVL trees and the four cases
The strictest common rule: no node's two subtrees may differ in height by more than one. Four imbalance shapes, four fixes.
An AVL tree stores a height at each node and maintains its balance factor:
balance_factor(node) = height(node.left) - height(node.right)
# +1, 0, -1 → fine
# +2 → left-heavy, must fix
# -2 → right-heavy, must fixAfter an insertion, walk back up the path you came down. The first node with a balance factor of ±2 is where the fix goes. Which fix depends on the shape of the imbalance, and there are exactly four shapes.
Left-Left — a straight line leaning left
Right-Right — the mirror image
Left-Right — a zig-zag
Here a single rotation does not help: it just produces the mirror-image zig-zag. Straighten it first, then apply the LL fix.
Right-Left — the other zig-zag
| Case | Detect with | Fix |
|---|---|---|
| Left-Left | bf > 1 and value < node.left.value | One right rotation at the node |
| Right-Right | bf < −1 and value > node.right.value | One left rotation at the node |
| Left-Right | bf > 1 and value > node.left.value | Left at the child, then right at the node |
| Right-Left | bf < −1 and value < node.right.value | Right at the child, then left at the node |
def insert(node, value):
# 1. ordinary BST insert
if node is None:
return AVLNode(value)
if value < node.value:
node.left = insert(node.left, value)
elif value > node.value:
node.right = insert(node.right, value)
else:
return node # duplicates ignored
# 2. update this node's height on the way back up
node.height = 1 + max(h(node.left), h(node.right))
# 3. rebalance if needed
bf = h(node.left) - h(node.right)
if bf > 1 and value < node.left.value: # Left-Left
return rotate_right(node)
if bf < -1 and value > node.right.value: # Right-Right
return rotate_left(node)
if bf > 1 and value > node.left.value: # Left-Right
node.left = rotate_left(node.left)
return rotate_right(node)
if bf < -1 and value < node.right.value: # Right-Left
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeAn AVL insertion needs at most one rebalance (one or two rotations), because the rotation restores the subtree to its height before the insertion — so nothing above it is affected.
Deletion is different: it can require a rebalance at every level, so up to
O(log n) rotations. That asymmetry is the main practical argument against AVL, and it
is why the next section exists.
4Red-black trees
A looser guarantee that costs less to maintain. This is what your standard library actually ships.
AVL keeps the tree very balanced, which makes lookups fast and updates expensive. A red-black tree accepts a weaker guarantee in exchange for cheaper updates.
Every node is coloured red or black, and five rules hold:
- Every node is red or black.
- The root is black.
- Every leaf (the conceptual null child) is black.
- A red node's children are both black — no two reds in a row.
- Every path from a node down to a leaf contains the same number of black nodes.
Rule 5 says all root-to-leaf paths have the same number of blacks. Rule 4 says reds cannot be adjacent, so no path can be more than half red.
Therefore the longest path is at most twice the shortest, which gives
h ≤ 2 log₂(n+1). Looser than AVL's
1.44 log₂ n, and still O(log n).
| AVL | Red-black | |
|---|---|---|
| Balance rule | Subtree heights differ by ≤ 1 | Longest path ≤ 2 × shortest |
| Maximum height | ~1.44 log₂ n | ~2 log₂ n |
| Lookup | Faster (shorter tree) | Slightly slower |
| Insert | ≤ 2 rotations | ≤ 2 rotations |
| Delete | Up to O(log n) rotations | ≤ 3 rotations |
| Extra storage | An integer height per node | One bit per colour |
| Best for | Read-heavy workloads | Write-heavy or mixed |
| Real users | Databases' in-memory indexes | Java TreeMap, C++ std::map, the Linux kernel |
The deletion row is the deciding one. AVL's strictness means a single deletion can cascade rebalances all the way to the root. Red-black's looseness caps it at three rotations, and general workloads delete as well as insert.
Red-black insertion has three cases and deletion has six, several with mirror images. A correct implementation is a few hundred lines and is genuinely hard to get right.
That is fine. What you need is to recognise one when you meet it in a library, and
to understand what it guarantees: O(log n) for everything, in the worst case, with keys
kept in order. That is why std::map and TreeMap behave the way they do.
5The alternatives, and what to actually use
Two other structures reach the same guarantee by different routes, and in Python you will probably use none of them.
Treaps — balance by randomness
Each node gets a random priority. The tree is a BST by key and a heap by
priority. Since the priorities are random, the tree's shape is that of a randomly-built BST
— expected height O(log n), with no balance factors and no case analysis.
def insert(node, key):
if node is None:
return TreapNode(key, priority=random.random())
if key < node.key:
node.left = insert(node.left, key)
if node.left.priority > node.priority: # heap violated
node = rotate_right(node) # one rotation fixes it
else:
node.right = insert(node.right, key)
if node.right.priority > node.priority:
node = rotate_left(node)
return node
# Twenty lines instead of three hundred. The guarantee is probabilistic
# rather than absolute, but the probability of a bad tree is astronomically
# small — and, crucially, an ADVERSARY cannot cause one, because the
# randomness is yours and not theirs.Skip lists — balance by layers
Not a tree at all: a stack of linked lists, where each level randomly contains about half the
elements of the one below. Searching drops down levels like an express train service. Same
O(log n) expected cost, much easier to make concurrent — which is why Redis uses
one for sorted sets.
B-trees — balance for disks
When your data lives on disk, the cost that matters is not comparisons but block reads. A B-tree gives each node hundreds of keys so it fills one disk page, making the tree extremely shallow — three or four levels for millions of records. Every relational database index is a B-tree.
What to reach for in Python
| You need | Use | Why |
|---|---|---|
| Lookup by key, no ordering | dict | O(1) and built in |
| A sorted collection, built once then queried | sorted() + bisect | O(log n) search, no dependency |
| A sorted collection with frequent inserts | sortedcontainers | Not a tree — a list of lists, and faster in practice |
| Repeatedly take the smallest | heapq | Chapter 17; a full tree is overkill |
| A genuine ordered map | sortedcontainers.SortedDict | Python has no built-in TreeMap |
You will almost certainly never write a red-black tree. What this chapter buys you is the ability to read a library's documentation and know what it is promising.
“std::map has O(log n) lookup and iterates in sorted order”
now means something concrete: it is a balanced tree, it pays a little on every write to keep the
height down, and that is why it beats unordered_map whenever you need order and loses
whenever you do not.
What to carry forward
- A rotation moves three pointers, lowers the height, and leaves the in-order sequence identical. It is the only mechanism any balanced tree needs.
- Balance factor = height(left) − height(right). ±2 means fix it. Update heights bottom-up after a rotation, or the factors go stale.
- Four cases: LL and RR need one rotation; LR and RL need two, because a single rotation just mirrors a zig-zag.
- An AVL insert needs at most one rebalance; an AVL delete can cascade to the root. That asymmetry is the argument against AVL.
- Red-black allows the longest path to be twice the shortest, which is looser but caps deletion at three rotations. That is why libraries ship it.
- You will not implement one. You will recognise one:
TreeMap,std::mapand every database index are balanced trees.
>_Playground
A working AVL tree. Insert sorted values and watch the height refuse to grow — then compare against a plain BST.
✓Exercises
Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.
Chapter 17 — Heaps and Priority Queues
A hospital triage desk, not a queue: whoever is most urgent goes next. A tree that hides inside an array.