AVL Trees in Python — Rotations, Animations & Code

Section 01

The Analogy That Makes AVL Trees Click

🎬 Real World Analogy

Cinema Seat Allocation — Why Balance Matters

Imagine a cinema that assigns seats in strict alphabetical order by surname. Every new guest walks down the aisle checking each row until they find their spot. The first night goes fine — ten guests, ten quick walks. But by the hundredth night every guest whose surname starts with A sits up front and every Z has to walk the full length of the theatre. Searching for "Mr Zhou" now means checking all 100 rows — that's O(n) time.

A smart cinema manager would rebalance the seating every time someone new arrived — always keeping the middle seat occupied first, so no walk ever exceeds log₂(100) ≈ 7 rows. That manager's rebalancing rule is exactly what an AVL tree does.

Every time a node is inserted or deleted, the AVL tree checks whether any ancestor has become "lopsided" (height difference > 1) and fixes it immediately with a rotation. The result: every search, insert, and delete is guaranteed O(log n) — always.

An AVL tree (named after Adelson-Velsky and Landis, 1962) is a self-balancing binary search tree. It maintains the AVL property: for every node, the heights of its left and right subtrees differ by at most 1. The moment a violation is detected, the tree rotates nodes to restore balance before returning control.

🌳

The Core Insight

A plain Binary Search Tree degrades to a linked list when data arrives in sorted order — giving O(n) operations. AVL trees pay a tiny overhead on inserts/deletes (at most two rotations) to guarantee O(log n) in the worst case, forever. No adversarial insertion sequence can break them.

Section 02

Watch an AVL Tree Build Itself

The animation below inserts 10 → 20 → 30 → 15 → 25 → 5 → 1 one by one. Watch balance factors update after each insert and rotations fire automatically when the tree goes out of balance. Use STEP to advance manually or PLAY for auto-play.

🌲 AVL Tree — Live Build Animation

    Press PLAY or STEP to begin inserting nodes…
  

💡

Reading the Balance Factor (BF)

BF = height(left subtree) − height(right subtree). BF 0 = perfectly symmetric. ±1 = allowed, no action. ±2 = triggers an immediate rotation. The BF is recalculated bottom-up after every insert/delete.

Section 03

The Four Rotation Types — Animated Phase-by-Phase

When balance breaks, exactly one of four rotation patterns applies. Each animation loops through Before → Rotating → After, showing which nodes move and where.

↩️

Case 1 — LL → Right Rotate

BF(z)=+2, BF(y)=+1

Left subtree of Left child is too tall. Single right rotation at z fixes it.

rotate_right(z)

↪️

Case 2 — RR → Left Rotate

BF(z)=−2, BF(y)=−1

Right subtree of Right child is too tall. Single left rotation at z fixes it.

rotate_left(z)

↔️

Case 3 — LR → Left then Right

BF(z)=+2, BF(y)=−1

Right subtree of Left child is too tall. Left-rotate y first, then right-rotate z.

rotL(z.left) → rotR(z)

🔄

Case 4 — RL → Right then Left

BF(z)=−2, BF(y)=+1

Left subtree of Right child is too tall. Right-rotate y first, then left-rotate z.

rotR(z.right) → rotL(z)

⚠️

Identifying Which Rotation to Apply

Always check two BF values: the unbalanced node z and its taller child y. Same-direction lean (++ or −−) → single rotation. Opposite-direction lean (+− or −+) → double rotation. The signs determine the answer deterministically — no guessing.

Section 04

Python Implementation — Full AVL Tree

A complete, self-contained AVL tree in Python. Each block maps to a phase in the animations above.

🔷 Phase A — Node Definition & Height Helpers

Purpose

Every AVL node stores its value, left/right child references, and its own cached height. Height is stored to avoid O(n) recomputation.

Animation

The number inside each circle is its value; BF±n shown below is computed live from these heights.

class Node:
    def __init__(self, val):
        self.val    = val
        self.left   = None
        self.right  = None
        self.height = 1   # leaf node starts at height 1

def get_height(node):
    return node.height if node else 0   # None → 0

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

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

CONCEPT CHECK

get_height(None) → 0 get_height(Node(10)) → 1 (leaf) get_balance balanced → 0 get_balance left-heavy → +2 → rotate right get_balance right-heavy→ -2 → rotate left

✅

Why Cache Height in the Node?

Computing height by traversing to every leaf costs O(n). By storing it in the node and updating O(1) after each rotation, get_balance() runs in O(1) and every insert/delete stays O(log n).

🔄 Phase B — The Four Rotation Functions

rotate_right(z) — z's left child becomes new root; z becomes its right child.

rotate_left(z) — mirror of above; z's right child becomes new root.

Left-rotate the left child, then right-rotate z.

Right-rotate the right child, then left-rotate z.

def rotate_right(z):
    # z has BF=+2 (left-heavy). y = z's left child.
    y  = z.left
    T2 = y.right          # T2 moves to become z's new left subtree

    y.right = z           # y rises to take z's place
    z.left  = T2

    update_height(z)      # update LOWER node FIRST (z is now below y)
    update_height(y)
    return y              # y is the new subtree root

def rotate_left(z):
    # z has BF=-2 (right-heavy). y = z's right child.
    y  = z.right
    T2 = y.left

    y.left  = z
    z.right = T2

    update_height(z)
    update_height(y)
    return y

ROTATION COST

rotate_right / rotate_left → O(1) (2 pointer moves + 2 height updates) LR / RL double rotation → O(1) (two single rotations back-to-back) Per insert: max 1 rotation → O(1) rotation overhead total

➕ Phase C — AVL Insert (the heart of the algorithm)

Step 1

Recurse down like a normal BST insert — O(log n) levels deep.

Step 2

On the way back up, update height and compute BF at every ancestor.

Step 3

At the first unbalanced ancestor, apply the correct rotation. Only one rotation ever needed per insert.

def insert(node, val):
    # ── 1. Standard BST insert ──────────────────────────────
    if not node:
        return Node(val)
    if   val < node.val:  node.left  = insert(node.left,  val)
    elif val > node.val:  node.right = insert(node.right, val)
    else: return node      # duplicate — ignore

    # ── 2. Update height on the way back up ─────────────────
    update_height(node)
    b = get_balance(node)

    # ── 3. Four rotation cases ──────────────────────────────
    # LL: left-left heavy → single right rotation
    if b > 1  and val < node.left.val:
        return rotate_right(node)

    # RR: right-right heavy → single left rotation
    if b < -1 and val > node.right.val:
        return rotate_left(node)

    # LR: left child is right-heavy → left then right
    if b > 1  and val > node.left.val:
        node.left = rotate_left(node.left)
        return rotate_right(node)

    # RL: right child is left-heavy → right then left
    if b < -1 and val < node.right.val:
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node  # already balanced — no rotation needed

TRACE — inserting 10→20→30→15→25→5→1

insert(None, 10) → Node(10), h=1 insert(root, 20) → right of 10, BF(10)=−1 OK insert(root, 30) → right of 20, BF(10)=−2! RR → rotate_left(10) → root=20 insert(root, 15) → left of 20, BF(20)=0 OK insert(root, 25) → right of 20, BF(20)=−1 OK insert(root, 5) → left of 10, BF(20)=+1 OK insert(root, 1) → left of 5, BF(10)=+2! LL → rotate_right(10) Final root: 20 | height: 3 | all BF ∈ {−1, 0, +1} ✓

🔍

How the Call Stack "Repairs" the Tree

Python unwinds the recursion from the newly inserted leaf back to the root, running update_height and the four balance checks at every ancestor. The first unbalanced node rotates, and the stack continues upward — now with a balanced subtree in place of the broken one.

➖ Phase D — AVL Delete (inorder successor trick)

Step 1

Find and remove as in a normal BST (leaf, one child, or two children).

Step 2

If the node had two children, replace its value with the inorder successor (smallest in right subtree).

Step 3

Re-balance all the way back up — up to O(log n) rotations (unlike insert which needs at most one).

def min_node(node):
    while node.left: node = node.left
    return node

def delete(node, val):
    if not node: return node

    # ── 1. BST delete ───────────────────────────────────────
    if   val < node.val: node.left  = delete(node.left,  val)
    elif val > node.val: node.right = delete(node.right, val)
    else:
        if not node.left or not node.right:
            node = node.left or node.right   # leaf / single child
        else:
            s          = min_node(node.right)  # inorder successor
            node.val   = s.val
            node.right = delete(node.right, s.val)

    if not node: return node

    # ── 2. Rebalance (same logic as insert) ─────────────────
    update_height(node)
    b = get_balance(node)

    if b >  1:
        if get_balance(node.left)  >=  0: return rotate_right(node)
        node.left  = rotate_left(node.left);  return rotate_right(node)
    if b < -1:
        if get_balance(node.right) <=  0: return rotate_left(node)
        node.right = rotate_right(node.right); return rotate_left(node)
    return node

TRACE — delete root (20) from {1,5,10,15,20,25,30}

delete(root=20, 20) node has two children successor = min_node(right subtree) = 25 node.val = 25 delete(right subtree, 25) update_height, rebalance… Result: {1,5,10,15,25,30}, still balanced ✓

🚀 Phase E — Full Demo

Demo

Build the 7-node tree, verify in-order output and height, delete root, confirm still balanced.

root = None
for v in [10, 20, 30, 15, 25, 5, 1]:
    root = insert(root, v)

def inorder(node, out=None):
    if out is None: out=[]
    if node:
        inorder(node.left, out); out.append(node.val); inorder(node.right, out)
    return out

print("In-order :", inorder(root))
print("Root     :", root.val)
print("Height   :", root.height)
print("Root BF  :", get_balance(root))

root = delete(root, root.val)   # delete the root node
print("After del:", inorder(root))
print("New root :", root.val)
print("Balanced :", abs(get_balance(root)) <= 1)

OUTPUT

In-order : [1, 5, 10, 15, 20, 25, 30] Root : 20 Height : 3 Root BF : 0 After del: [1, 5, 10, 15, 25, 30] New root : 25 Balanced : True

🎯

In-Order Output Proves Correctness

In-order traversal of any valid BST always yields a sorted sequence. If the output is sorted after every insert and delete, the BST property is intact. Combined with all |BF| ≤ 1, the full AVL property is proven.

Section 05

Time & Space Complexity

Operation	AVL Tree	Plain BST (worst)	Sorted Array	Guaranteed?
Search	O(log n)	O(n)	O(log n)	Always
Insert	O(log n)	O(n)	O(n)	Always
Delete	O(log n)	O(n)	O(n)	Always
Rotation cost	O(1) each	N/A	N/A	≤ 2 per insert
Rotations per delete	O(log n) max	N/A	N/A	Unlike insert
Space	O(n) + 1 int/node	O(n)	O(n) contiguous	+1 int overhead
Sorted iteration	O(n) in-order	O(n)	O(n)	Always sorted
Tree height bound	≤ 1.44 log₂(n+2)	n in worst case	N/A	Proven bound

⚠️

When AVL Loses to Red-Black Trees

AVL trees are more strictly balanced — lookups are ~30% faster than Red-Black on average. But deletion can trigger O(log n) rotations, while Red-Black caps at 3. For write-heavy workloads (databases, OS schedulers) Red-Black is preferred. For read-heavy workloads (in-memory dictionaries, routers) AVL wins.

Section 06

Where AVL Trees Are Used in Practice

🗄️

Database Indexes

B-Tree cousin

MySQL and SQLite use AVL / B-tree variants for primary key indexes. A 10-million-row table is found in ≤ 24 comparisons — O(log n) guaranteed.

🔠

Spell Checkers & Autocomplete

Ordered dictionary

A 200,000-word dictionary in an AVL tree allows predecessor/successor search in O(log n) — essential for real-time suggestions as you type.

🌐

IP Routing Tables

Longest-prefix match

Network routers store prefixes in AVL-like structures to find the next hop in O(log n) — critical when routing millions of packets per second.

Data arrives in adversarial (e.g. sorted) order

A plain BST degrades to a linked list with sorted input — O(n) per operation. AVL detects imbalance at insertion time before returning.

Insert / Delete triggers height + BF check up the stack

Recursion unwinds from the new leaf back to root, recomputing height and BF at every ancestor. Most ancestors stay balanced — no rotation needed.

First ancestor with |BF| = 2 gets rotated in O(1)

One of four rotation patterns fires. Heights are updated bottom-up. After the rotation, all ancestors above are guaranteed balanced.

Search runs on the balanced tree in ≤ 1.44 log₂(n) steps

This is the mathematical upper bound for AVL height. In practice height is usually very close to log₂(n) — far tighter than any unbalanced BST.

Section 07

AVL Tree vs Plain BST — Side-by-Side

❌ Plain BST — Sorted input [1,2,3,4,5]

Height = 5 · Search = O(n) ← DEGENERATE

✅ AVL Tree — Same input [1,2,3,4,5]

Height = 3 · Search = O(log n) ← ALWAYS BALANCED

Section 08

Golden Rules — AVL Trees

🌳 AVL Tree — 6 Non-Negotiable Rules

Always cache height in the node, never compute it on the fly. Computing height by traversal costs O(n); cached height costs O(1). Every rotation and balance check depends on this — getting it wrong silently destroys your time-complexity guarantee.

Update the lower node's height BEFORE the upper one after a rotation. In rotate_right(z), call update_height(z) before update_height(y). Reversing this produces wrong heights — a subtle silent bug that corrupts every BF check upward.

Insert needs at most 1 rotation; delete may need O(log n). An insert unbalances exactly one ancestor. A delete can unbalance every ancestor up to the root. Your delete path must re-check balance at every level — not stop at the first fix.

Use BF signs to choose the rotation — not visual tree shape. BF(z) > 1 && BF(y) ≥ 0 → right rotate. BF(z) > 1 && BF(y) < 0 → left-right. BF(z) < −1 && BF(y) ≤ 0 → left rotate. BF(z) < −1 && BF(y) > 0 → right-left.

Always return the new subtree root from every recursive call. Python cannot mutate a parent pointer from inside a child call. Every insert() and delete() must return the (possibly rotated) subtree root, and the caller must assign it: node.left = insert(node.left, val).

Choose AVL for read-heavy; Red-Black for write-heavy workloads. AVL's stricter balance (height ≤ 1.44 log n vs Red-Black's 2 log n) gives faster lookups. But deletion can trigger O(log n) rotations vs Red-Black's maximum 3. Profile your workload before picking.