The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

AVL Trees

Next ►
►

The previous lesson ended with an uncomfortable measurement: TaskFlow's index, built with auto-incrementing ids — the most common case in the real world — degenerated into a list and its O(log n) evaporated. The AVL tree (after its inventors, Adelson-Velskii and Landis, 1962) is a BST that refuses to degenerate: after every insertion it checks one number per node (the balance factor) and, if it detects imbalance, corrects it with a rotation — a local repositioning of two or three nodes that restores balance without breaking the search property. The result: height O(log n) guaranteed, whatever data arrives and in whatever order. In this lesson you'll understand the balance factor, the four rotations (LL, RR, LR, RL) with step-by-step diagrams, implement full AVL insertion, and measure the difference with the exact experiment that sank the BST.

Contents

  1. The problem, quantified: why the BST isn't enough
  2. Balance factor: each node's telltale
  3. The single rotations: LL and RR
  4. The double rotations: LR and RL
  5. Implementation: AVL insertion with recursive rebalancing
  6. The rematch: measuring BST vs AVL with sorted ids
  7. When an AVL pays off (and what the libraries use)

The problem, quantified: why the BST isn't enough

Let's recap 06-04's wound with numbers: inserting range(1023) into a BST produces height 1022; shuffled, ~20; the ideal was 9. The problem isn't the BST as an idea — it's that its shape is at the mercy of arrival order, and real data arrives with order (increasing ids, dates, counters). An index whose performance depends on luck isn't an index: it's a lottery.

The AVL idea: maintain a balance invariant on top of the search one. Specifically:

At every node, the heights of its two subtrees differ by at most 1.

It doesn't demand perfection (that would force massive rebuilds); it demands near-balance, which is cheap to maintain and sufficient: it can be proven that an AVL with n nodes has height less than 1.45·log₂(n+2) — for the million tasks in 06-02's table, height ≤ 28 instead of up to 999,999. O(log n) with a mathematical guarantee, not a statistical one.

Balance factor: each node's telltale

To watch the invariant without recomputing heights at every step (that would be O(n) per check), each node stores its height as an attribute, and we define:

balance factor (BF) = height(left subtree) − height(right subtree)

BF Meaning
0 Perfectly balanced at this node
+1 The left is one level taller: acceptable
−1 The right is one level taller: acceptable
+2 Too heavy on the left: rotate
−2 Too heavy on the right: rotate

Inserting one at a time, the BF can only reach ±2 (we started from at most ±1, and one insertion changes heights by 1); we'll never see a ±3. That's why corrections are always local and small.

graph TD
    A["10 (BF=+2) ⚠"] --> B["6 (BF=+1)"]
    A --> Z["(empty)"]
    B --> C["3 (BF=0)"]
    B --> Y["(empty)"]

This tree (insert 10, 6, 3) already violates the invariant at the root: left of height 1, right of height −1 (empty), BF = +2. In a plain BST nothing happens here and degeneration gets rolling; the AVL, on the other hand, acts.

The single rotations: LL and RR

A rotation rearranges a node and one of its children so that the child goes up, the parent goes down, and — this is the crucial part — the inorder sequence doesn't change, so the search property survives intact. There are four imbalance cases, named after where the new node landed relative to the unbalanced node: LL, RR, LR, and RL.

LL case (left-left): BF = +2 and the excess sits in the left-left subtree. It's fixed with a right rotation: the left child rises to root of the subtree, the old parent becomes its right child, and subtree B (the values between the two) switches sides:

graph TD
    subgraph "Before: BF(z)=+2, LL case"
        Z((z)) --> Y((y))
        Z --> T4[T4]
        Y --> X((x))
        Y --> T3[T3]
        X --> T1[T1]
        X --> T2[T2]
    end
    subgraph "After: right rotation at z"
        Y2((y)) --> X2((x))
        Y2 --> Z2((z))
        X2 --> T1b[T1]
        X2 --> T2b[T2]
        Z2 --> T3b[T3]
        Z2 --> T4b[T4]
    end

Check the inorder in both: T1, x, T2, y, T3, z, T4. Identical — search notices nothing, but the overall height drops by 1. With the 10-6-3 example: z=10, y=6, x=3; after rotating, 6 is the root with 3 and 10 as children. Balance restored with three reference reassignments: O(1).

The RR case is the exact mirror (BF = −2, excess in right-right; inserting 3, 6, 10 causes it): left rotation, the right child rises. In code, both:

def rotate_right(z):
    """LL case. Returns the new root of the subtree (y)."""
    y = z.left
    t3 = y.right
    y.right = z            # the parent drops down to right child
    z.left = t3            # and y's old right subtree (T3) changes owner
    update_height(z)       # z first: it's now the one below
    update_height(y)
    return y

def rotate_left(z):
    """RR case. Mirror of the previous one. Returns the new root (y)."""
    y = z.right
    t2 = y.left
    y.left = z
    z.right = t2
    update_height(z)
    update_height(y)
    return y

Transferring t3 is the step people forget: T3's values sit between y and z (greater than y, less than z), and after the rotation their rightful place is z's left slot. And heights are updated bottom-up: first z (now the child), then y (now the subtree's root).

The double rotations: LR and RL

What if the excess is in a "zigzag"? Insert 10, 3, 6: node 10 has BF = +2, but the new node landed in the left-right subtree. A single right rotation doesn't fix it (try it on paper: 3 would rise with BF = −2 — the imbalance just changes sides). The LR case needs two moves: first a left rotation on the child (turning the zigzag into the LL case) and then the usual right rotation on the unbalanced node:

graph TD
    subgraph "1. Before: LR case"
        Z((10)) --> Y((3))
        Y --> X((6))
    end
    subgraph "2. Rotate left at 3"
        Z2((10)) --> X2((6))
        X2 --> Y2((3))
    end
    subgraph "3. Rotate right at 10"
        X3((6)) --> Y3((3))
        X3 --> Z3((10))
    end

The grandchild (6) ends up as the subtree's root, with its former grandparent and former parent as children. The RL case is the mirror (BF = −2 with the excess in right-left; inserting 3, 10, 6): right rotation on the child, then left on the node. Summary of the four cases:

Case Detection Fix
LL BF = +2 and BF(left child) ≥ 0 Right rotation
LR BF = +2 and BF(left child) < 0 Left rot. on the child + right rot.
RR BF = −2 and BF(right child) ≤ 0 Left rotation
RL BF = −2 and BF(right child) > 0 Right rot. on the child + left rot.

Note that detection is purely arithmetic: the node's BF tells you which side the problem is on, and the child's BF tells you whether it's in line (single) or zigzag (double).

Implementation: AVL insertion with recursive rebalancing

Let's assemble. The strategy is the BST's recursive insertion with an extra step on the way back from each call: update the node's height and, if its BF has stepped outside [−1, +1], apply the rotation for the corresponding case. Since each call returns the (possibly new) root of its subtree, the "reassign on the way back" pattern we used in 06-04's _delete fits perfectly:

class AVLNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.height = 0                  # newborn leaf (06-02's convention)

def height_of(node):
    return node.height if node else -1   # the empty subtree measures -1

def update_height(node):
    node.height = 1 + max(height_of(node.left), height_of(node.right))

def balance_factor(node):
    return height_of(node.left) - height_of(node.right)

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, key, value):
        self.root = self._insert(self.root, key, value)

    def _insert(self, node, key, value):
        # 1) Normal (recursive) BST insertion
        if node is None:
            return AVLNode(key, value)
        if key == node.key:
            node.value = value
            return node
        elif key < node.key:
            node.left = self._insert(node.left, key, value)
        else:
            node.right = self._insert(node.right, key, value)

        # 2) On the way BACK: update height and check balance
        update_height(node)
        bf = balance_factor(node)

        # 3) The four cases
        if bf > 1 and balance_factor(node.left) >= 0:   # LL
            return rotate_right(node)
        if bf > 1:                                      # LR
            node.left = rotate_left(node.left)
            return rotate_right(node)
        if bf < -1 and balance_factor(node.right) <= 0: # RR
            return rotate_left(node)
        if bf < -1:                                     # RL
            node.right = rotate_right(node.right)
            return rotate_left(node)

        return node                       # balanced: no changes

    def find(self, key):                  # identical to the BST!
        node = self.root
        while node is not None:
            if key == node.key:
                return node.value
            node = node.left if key < node.key else node.right
        return None

Fine points, top to bottom:

  • Everything happens as the recursion unwinds: insertion descends to the leaf, and the height updates and rotations happen on the way back, from the leaf toward the root — exactly the direction imbalance propagates.
  • Storing the height in the node makes balance_factor O(1); without it, each check would cost a subtree traversal.
  • A reassuring theorem: on an insertion, a single rotation (single or double) restores balance for the entire tree — once the first unbalanced node is corrected, the ancestors recover their previous height and there's no need to continue. (AVL deletion is less friendly: it may need cascading rotations up to the root, still O(log n); its implementation combines 06-04's _delete with this same rebalancing and is beyond the lesson's scope.)
  • find (and inorder, and range_query...) are the same as the BST's, without touching a comma: the AVL is a BST. Only who controls the shape changes.

Let's verify with the killer sequence:

avl = AVLTree()
for i in range(1, 8):
    avl.insert(i, f"task {i}")

print(avl.root.key)            # 4: the root is the median, not 1!
print(height_of(avl.root))     # 2: the minimum possible with 7 nodes

Inserting 1…7 in order, the BST gave height 6; the AVL gives 2, the perfect tree. The rotations kept repositioning: on inserting 3, the 1-2-3 chain rotates and 2 rises; on inserting 5, 3's subtree rotates... The tree rebuilds itself, insertion by insertion, without the client code knowing anything.

The rematch: measuring BST vs AVL with sorted ids

Let's repeat the exact experiment that condemned the BST in 06-04 — 2,000 auto-incrementing ids — plus a search on the result:

import timeit

def build_avl(keys):
    t = AVLTree()
    for k in keys:
        t.insert(k, None)
    return t

ids = list(range(2000))

print(timeit.timeit(lambda: build(ids), number=5))       # BST:  ~4 s
print(timeit.timeit(lambda: build_avl(ids), number=5))   # AVL:  ~0.06 s

bst, avl = build(ids), build_avl(ids)
print(timeit.timeit(lambda: bst.find(1999), number=10000)) # ~1.9 s  (walks 2000 nodes)
print(timeit.timeit(lambda: avl.find(1999), number=10000)) # ~0.02 s (goes down ~11 levels)
print(bst_height(bst), height_of(avl.root))                # 1999  vs  10

The concrete times will vary on your machine, but the structure of the result won't: construction ~70 times faster, search ~100 times faster, height 1999 versus 10. And note the fair fine print: the AVL pays a constant overhead per insertion (updating heights, checking BFs, sometimes rotating) — with random keys the plain BST can even beat it by a hair. What the AVL buys is not speed in the good case: it's the elimination of the bad case.

When an AVL pays off (and what the libraries use)

Always AVL, then? Almost, but with judgment:

  • It pays off when searches and range queries dominate over writes, or when you don't control the arrival order of the keys (or you do control it: and it's sorted!). The AVL is the most rigidly balanced of the self-balancing trees: minimal height, maximally fast searches.
  • It falls short when there are very many writes: its rigidity forces frequent rotations. For those workloads there's the red-black tree, a cousin that tolerates a bit more imbalance (height ≤ 2·log₂ n) in exchange for rotating less; it's the choice of the standard libraries — C++'s std::map, Java's TreeMap — precisely for that read/write balance. We won't develop it: the ideas (invariant + local rotations) are the same ones you just learned; only the bookkeeping changes.
  • Python, by the way, doesn't ship a balanced tree in the standard library (its culture solves almost everything with dict + sorted); in the ecosystem, packages like sortedcontainers fill the gap with a different technique. Now you understand exactly which hole they plug.

For TaskFlow, the decision is clear: 06-04's (priority, id) index receives auto-incrementing ids daily — the workload that degenerates the BST. Swapping SearchTree() for AVLTree() (same interface: insert, find...) gives TaskFlow an ordered index that never degrades, whatever it receives.

Common Mistakes and Tips

  • Forgetting to update heights, or doing it in the wrong order. After a rotation, first the node that went down, then the one that went up (the upper one depends on the lower one). Stale heights → lying BFs → rotations where they don't belong. It's the number-one bug in homemade implementations.
  • Losing the middle subtree (T2/T3) when rotating. A rotation isn't "swap parent and child": the intermediate subtree must change parents. If your tree loses nodes after rotating, this is it.
  • Handling a zigzag case with a single rotation. LR and RL need the double one; the single one leaves BF = ∓2 on the other side and, with bad luck, a loop of fruitless rotations. Correct detection looks at the child's BF.
  • Forgetting to reassign the result: self.root = self._insert(...) and node.left = rotate_left(...). Rotations return the subtree's new root; ignoring the return value leaves references pointing at the node that's no longer the root.
  • Verification tip: after each batch of insertions in your tests, check two invariants: the inorder comes out sorted (BST property intact) and all BFs are in {−1, 0, +1} (balance). A ten-line test that catches 95% of AVL bugs.

Exercises

Exercise 1: the rotation trace

Without running any code, draw the AVL after inserting, in this order, the keys 30, 20, 10, 25, 27. Indicate which case (LL, RR, LR, RL) fires at each rotation and on which node. Then verify it with code by printing the inorder and the root.

Exercise 2: balance auditor

Write is_valid_avl(node) that returns True if all the tree's BFs are in {−1, 0, +1}, computing the heights on its own (without trusting the height attribute, which is precisely what could be wrong). Test it on the AVL of 1…7 and on a degenerate BST.

Exercise 3: TaskFlow's indestructible index

Rebuild 06-04's (priority, id) index on AVLTree, inserting 30 tasks with ids 1…30 and priorities (i % 3) + 1. Check: (a) that the height is ≤ 1.45·log₂(32) ≈ 7; (b) that a filtered inorder returns the priority-1 tasks ordered by id. (If you added range_query to the AVL by copying it from the BST, even better: use it.)

Solutions

Solution 1

Step by step:

  1. 30, 20: no problems (BF(30) = +1).
  2. 10: chain 30-20-10, BF(30) = +2 with left-left excess → LL, right rotation at 30. 20 becomes the root, children 10 and 30.
  3. 25: descends to left child of 30. BF(20) = −1, BF(30) = +1: all within range, no rotation.
  4. 27: descends below 25, to its right. Now BF(30) = +2 and the excess is in left-right → LR at 30: left rotation at 25 (27 rises) and right rotation at 30. The subtree becomes 27 with children 25 and 30.

Final tree: root 20, left 10, right 27, and under 27 the nodes 25 and 30. Verification:

avl = AVLTree()
for k in [30, 20, 10, 25, 27]:
    avl.insert(k, None)
print(avl.root.key)                        # 20
print(avl.root.right.key)                  # 27
# inorder: [10, 20, 25, 27, 30] — sorted, property intact

Comment: step 4 is the one that separates those who understand the AVL from those who memorize it — the first instinct ("rotate right at 30 and done") leaves the tree just as unbalanced. Always draw the child's BF before deciding.

Solution 2

def _height_and_validity(node):
    """Returns (real height, is_valid) for the subtree, in a single pass."""
    if node is None:
        return -1, True
    left_h, left_ok = _height_and_validity(node.left)
    right_h, right_ok = _height_and_validity(node.right)
    bf = left_h - right_h
    return 1 + max(left_h, right_h), left_ok and right_ok and abs(bf) <= 1

def is_valid_avl(node):
    return _height_and_validity(node)[1]

print(is_valid_avl(avl.root))          # True
print(is_valid_avl(build(list(range(10))).root))   # False (degenerate BST)

Comment: the function returns two things at once (height and verdict) so the pass is O(n) — the naive version calling height() at every node is O(n²), exactly the performance trap the AVL's height attribute avoids in production. It's a pure postorder: information (heights) flows from children to parents, like the accumulated hours of 06-03. This auditor is the ten-line test from the final tip; its twin auditor for the search property comes in 06-08.

Solution 3

import math

index = AVLTree()
for i in range(1, 31):
    task = {"id": i, "title": f"Task {i}", "priority": (i % 3) + 1,
            "status": "pending"}
    index.insert((task["priority"], i), task)

# (a) guaranteed height
print(height_of(index.root))                       # 5 or 6 depending on the sequence
print(1.45 * math.log2(32))                        # 7.25: within the guarantee

# (b) priority 1, ordered by id (inorder + filter)
result = []
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    result.append(node)
    inorder(node.right)
inorder(index.root)
prio1 = [n.value["id"] for n in result if n.key[0] == 1]
print(prio1)     # [3, 6, 9, 12, 15, 18, 21, 24, 27, 30] — ascending, guaranteed

Comment: the (priority, id) keys arrive with strictly increasing ids — within each priority, the sequence that degenerated the BST. The AVL doesn't flinch: height 5-6 with 30 nodes, within the 1.45·log₂(n+2) bound. And the inorder comes out grouped by priority and by id within each group, because that's how tuples compare. This is, now in its definitive version, TaskFlow's ordered index: 06-04's interface, 06-05's guarantee.

Conclusion

The AVL closes the vulnerability the BST shipped with: storing one height per node, watching the balance factor, and correcting with the four rotations (LL and RR single, LR and RL double — all O(1), all preserving the inorder), it guarantees O(log n) height no matter what — and you've verified it with the same sorted-id sequence that sank the BST: height 10 where there was 1999. TaskFlow finally has an indestructible ordered index, and as a bonus you know the map of the territory: red-black when writes get heavy (the libraries' choice), and the reason for the gap in Python's standard library. But this whole lesson took something for granted: that the entire tree lives in RAM, where jumping from one node to another is free. What if TaskFlow's tasks number in the millions and live on disk, where every access is paid for dearly and in blocks? There, binary trees — even perfect ones — make too many jumps, and you need a shorter, much wider tree: the B-tree, the one that holds up databases, and the next lesson.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved