AVL Tree

The problem with plain BSTs

A binary search tree is fast only if it stays bushy. Insert sorted data (10, 20, 30, …) and every node goes right — the tree turns into a straight line and search becomes O(n).

An AVL tree (named after inventors Adelson-Velsky and Landis, 1962) fixes this. After every insert or delete it checks whether the tree has become lopsided and, if so, repairs it with rotations.

The balance factor

For every node:

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

An AVL tree requires bf ∈ {−1, 0, +1} for every node. The model shows each node’s bf above it. If a node reaches +2 (left-heavy) or −2 (right-heavy), it must be fixed.

Rotations

A rotation changes a few parent–child links so that one side gets shorter and the other taller — without breaking the BST order.

Right rotation at node z (when it’s left-heavy):

        z                y
       / \             /   \
      y   T4    →     x     z
     / \             / \   / \
    x   T3          T1 T2 T3 T4
   / \
  T1  T2

y moves up, z moves down to the right, and subtree T3 changes parent. A left rotation is the mirror image. Each rotation is O(1) — just a few pointer changes.

The four cases

Let z be the lowest unbalanced node after inserting x.

Case	Where x went	Fix
LL	left child’s left subtree	single right rotation at z
RR	right child’s right subtree	single left rotation at z
LR	left child’s right subtree	left rotation at z.left, then right rotation at z
RL	right child’s left subtree	right rotation at z.right, then left rotation at z

The double-rotation cases (LR, RL) first turn a “zig-zag” into a straight line, then fix it with a single rotation. Try them all in the model.

Why it guarantees O(log n)

It can be proved that an AVL tree with n nodes has height at most about 1.44 · log₂(n + 2). So search, insert and delete always run in O(log n) — no bad inputs exist. After an insertion, at most one (single or double) rotation is needed.

Code

class Node:
    def __init__(self, v):
        self.v, self.left, self.right, self.h = v, None, None, 1

def h(n):  return n.h if n else 0
def bf(n): return h(n.left) - h(n.right)
def fix(n): n.h = 1 + max(h(n.left), h(n.right))

def rotate_right(z):
    y = z.left
    z.left, y.right = y.right, z
    fix(z); fix(y)
    return y

def rotate_left(z):
    y = z.right
    z.right, y.left = y.left, z
    fix(z); fix(y)
    return y

def insert(node, v):
    if node is None:
        return Node(v)
    if v < node.v:
        node.left = insert(node.left, v)
    elif v > node.v:
        node.right = insert(node.right, v)
    else:
        return node
    fix(node)
    b = bf(node)
    if b > 1 and v < node.left.v:        # LL
        return rotate_right(node)
    if b < -1 and v > node.right.v:      # RR
        return rotate_left(node)
    if b > 1 and v > node.left.v:        # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1 and v < node.right.v:      # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

root = None
for v in [10, 20, 30, 40, 50, 60, 70]:
    root = insert(root, v)
print(root.v, h(root))    # 40 3  — perfectly balanced

AVL vs Red-Black trees

Both are self-balancing BSTs with O(log n) operations.

	AVL	Red-Black
Balance	Stricter (height ≤ 1.44 log n)	Looser (height ≤ 2 log n)
Lookups	Slightly faster	Slightly slower
Inserts/deletes	More rotations	Fewer rotations
Used in	Databases, lookup-heavy apps	C++ std::map, Java TreeMap, Linux kernel

Common mistakes

• Forgetting to update heights after rotating (update the lower node first, then the new root).
• Mixing up LR and RL — check which child (and which grandchild) the new key went into.
• Not re-linking the rotated subtree back to its parent.