Balanced Trees: AVL & Red-Black Trees Explained by Intuition (Rotations, Not Rote)

In plain words

Imagine a library where books are sorted by ISBN on a long shelf. Every time you add a book, you need to keep the shelf sorted — but if books always arrive in ISBN order, you end up pushing every previous book one slot to the right, which is slow. A self-balancing bookshelf notices when one side is getting too heavy and automatically rearranges a few books so both halves stay roughly equal. That's an AVL or red-black tree: it performs the same BST operations, but after each insert or delete it does a tiny local rearrangement to keep the shelf balanced — so no matter what order books arrive, searching always takes O(log n).

Lesson 11 ended on a cliffhanger: the BST's O(log n) promise dies whenever input arrives in sorted order — and sorted input is everywhere. The fix is a tree that notices when it's becoming lopsided and repairs itself on the spot. This lesson builds the intuition for how that's even possible, then tours the two canonical designs. Fair warning about scope: full deletion-rebalancing case analysis is genuinely intricate and almost never asked; what interviews and engineering judgment actually require is the why — rotations, the two invariant styles, and the trade-off between them. That's what this lesson delivers.

The rotation: one move, all of balancing

Picture nodes x < y where y is x's parent and x is the left child. A right rotation at y lifts x into y's position and demotes y to x's right child; x's former right subtree — which contains exactly the keys between x and y — slides over to become y's left subtree. Count what happened: three pointer updates, O(1). And check the ordering: keys less than x stay left of x; keys between x and y are now left of y (correct — they're less than y and greater than x); keys greater than y stay right. The inorder sequence is completely unchanged. A left rotation is the mirror image.

Before right-rotate(y):        After right-rotate(y):

        y                               x
       / \                            / \
      x   C                          A   y
     / \                                / \
    A   B                              B   C

Keys in each region:
  A: all < x
  B: x < keys < y   (slides from x's right to y's left)
  C: all > y

Inorder before: A, x, B, y, C
Inorder after:  A, x, B, y, C  ← identical!

3 pointer updates: x.right=y, y.left=B, parent.child=x

The effect on shape: rotating shifts one unit of height from one side to the other. A tree leaning too far left gets a right rotation at the lean point and levels out. All that differs between balancing schemes is the bookkeeping that decides *when* and *where* to rotate.

AVL trees: the strict approach

The AVL tree (Adelson-Velsky & Landis, 1962 — the first self-balancing BST) enforces: at every node, the left and right subtree heights differ by at most 1. Each node stores its height (or just the −1/0/+1 balance factor). After a standard BST insertion, walk back up the insertion path updating heights; the first node whose balance factor hits ±2 is the trouble spot, and there are exactly four shapes it can take:

1. Left-Left (inserted into the left child's left subtree): one right rotation at the unbalanced node.
2. Right-Right: the mirror — one left rotation.
3. Left-Right (left child's *right* subtree grew): a single rotation would just flip the zigzag to the other side — first left-rotate the left child to straighten the zigzag into Left-Left, then right-rotate the unbalanced node.
4. Right-Left: the mirror double rotation.

Step 0: Unbalanced tree after inserting 5

        z=7     ← balance factor = +2 (left heavy)
       /
      x=3
       \
        y=5     ← zigzag! left child's RIGHT subtree grew

Step 1: Left-rotate x (straighten the zigzag → Left-Left)

        z=7
       /
      y=5
     /
    x=3

Step 2: Right-rotate z (fix the Left-Left case)

        y=5
       / \
      x=3  z=7

Height reduced by 1; AVL property restored at z.
The subtrees of x and z (omitted above) slide correctly.

The zigzag cases are the only subtlety: a bent path can't be fixed by one rotation, so you straighten it first. After the (at most one single or double) rotation, insertion rebalancing is provably complete — the subtree's height returns to its pre-insertion value, so no ancestor above needs repair. The payoff for all this vigilance: an AVL tree's height is at most ~1.44·log₂(n), the tightest of any classic scheme, making AVL the fastest to search. The cost: insertions and deletions do more rebalancing work (deletions may rotate at O(log n) separate levels on the way up).

Worked intuition: sorted input, healed

Insert 1:    Insert 2:    Insert 3 → Right-Right imbalance at 1:

  1            1               1   ← balance = -2
                \               \
                 2               2   ← right child
                                  \
                                   3  ← right-right

Left-rotate at 1:

        2
       / \
      1   3        ← perfectly balanced, height = 1

Insert 4 → Right-Right at 2 (right subtree now height 2, left height 0):
Wait — after insert 4: balance at 2 is -1 (right: h=1, left: h=0) → OK!

Insert 5 → Right-Right at 2:
        2
       / \
      1   4
         / \
        3   5

Balance at 2: left=0, right=2 → imbalance=2 → Left-rotate at 2:

        4
       / \
      2   5
     / \
    1   3

Insert 1, 2, 3 into an AVL tree. After 1, 2: fine (heights 1, 0 down the right spine). Insert 3: node 1's balance factor hits −2 with the growth in its right child's right subtree — Right-Right case. One left rotation at 1: now 2 is the root with children 1 and 3. A plain BST would be a three-node chain; the AVL tree is already perfect, and it repeats that repair every time the chain tries to form — inserting 1…n costs O(n log n) total and yields a logarithmic tree, versus the plain BST's O(n²) build into a list.

Red-black trees: the pragmatic approach

The red-black tree relaxes strictness for cheaper maintenance. Each node is colored red or black, subject to: (1) the root is black; (2) a red node never has a red child; (3) every root-to-null path contains the same number of black nodes. Squint at what those rules force: rule 3 makes the tree perfectly balanced *in black nodes*, and rule 2 caps how many reds can pad any path — at most one red between consecutive blacks. So the longest possible path (alternating black-red) is at most twice the shortest (all black): height ≤ 2·log₂(n + 1). Looser than AVL's bound, but still firmly O(log n).

Legend: [B]=black  [R]=red  null=black leaf (sentinel)

              [B]8
             /    \
          [R]3    [B]10
          /  \       \
        [B]1 [B]6    [R]14
             /  \
           [R]4 [R]7

Rules check:
  (1) Root 8 is black ✓
  (2) No red node has a red child ✓
      (R)3 → (B)1, (B)6  ✓
      (R)14 → null (black sentinel) ✓
  (3) Black-height = 2 on every root→null path ✓
      8→3→1→null:   B,R,B,null  = 2 blacks
      8→3→6→4→null: B,R,B,R,null= 2 blacks
      8→10→14→null: B,B,R,null  = 2 blacks

Insertions enter red (never disturbing rule 3), and violations of rule 2 are repaired by recoloring — often just flipping colors, no structural change at all — plus at most two rotations per insertion (at most three per deletion). That's the design philosophy in one line: *tolerate mild imbalance to make modifications cheap.* It's why red-black trees are the standard behind most languages' sorted map/set containers, where inserts and deletes are as common as lookups.

AVL vs red-black: the actual trade-off

Both are O(log n) at everything, so Big-O won't pick a winner — constants and workload do. AVL's flatter tree wins when searches vastly outnumber updates; red-black's lazier maintenance wins under churn. And per Lesson 9: if you don't need order at all, a hash table beats both at O(1) average. The balanced BST's niche is *ordered* dynamic data — sorted maps and sets, range queries, floor/ceiling lookups, priority-with-arbitrary-delete (schedulers, order books, interval indexes).

Common pitfalls

• Memorizing the four AVL cases without the zigzag insight. The only idea is: straight lean → one rotation; bent lean → straighten first, then rotate. Everything else is mirror images.
• Believing rotations could reorder data. They can't — the inorder sequence is invariant under rotation. If your mental model allows a rotation to 'lose' a subtree, re-draw the between-keys subtree sliding across.
• Assuming red-black's looser balance is worse. Its tree is ~2× deeper in the worst case, but its updates are O(1) rotations; for mixed workloads that trade is a win, which is why general-purpose libraries chose it.
• Hand-rolling one in production. Correct deletion rebalancing is famously fiddly. Use your language's sorted map/set — the point of this lesson is judgment, not artisanal red-black trees.
• Using a balanced tree when a hash table or heap fits. Need only lookup? Hash table. Need only min/max? A heap — next lesson — is simpler and faster than a full ordered tree.

Practice problems

1. Trace AVL insertions. Insert the sequence 10, 20, 30, 15, 25 into an AVL tree one by one. After each insertion, compute balance factors and apply rotations as needed. Draw the tree after each step.
2. Red-black recoloring. Start with a valid red-black tree of 7 nodes. Insert a new key that causes a double-red violation. Trace whether the fix is a recolor, a single rotation, or a double rotation.
3. Library selection. You're building a leaderboard: keys are scores, values are player IDs. You insert/update millions of scores per minute and also need 'top 100 scores' every second. Which structure — hash table, AVL tree, red-black tree, or min-heap — and why?

Key takeaways

• Rotations reshape a BST in O(1) without disturbing the sorted (inorder) sequence — the atomic move of all balancing.
• AVL: heights differ ≤ 1 everywhere; flattest tree, fastest search, more repair work on updates.
• Red-black: color rules bound the longest path at 2× the shortest; slightly deeper tree, much cheaper updates — the general-purpose default.
• Both guarantee O(log n) search/insert/delete regardless of input order — sorted input can no longer hurt you.
• Reach for a balanced BST when you need *ordered* dynamic data; otherwise hash tables (unordered lookup) or heaps (min/max only) are simpler wins.

Next: drop the total-order requirement and keep just 'smallest first', and the tree flattens into an array — the heap and priority queue. Reinforce rotations and balance rules with quizzes in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play