Self-Balancing BST (AVL)

A plain binary search tree can degenerate into a linked list — insert 10, 20, 30 in order and you get a straight right spine where search is O(n). An AVL tree is a BST that refuses to get that lopsided: after every insert it checks each node on the path back to the root and, if any node leans too far, it rotates to rebalance. The result is a tree whose height stays O(log n), so search, insert, and delete are all O(log n) guaranteed.

Intuition

A rotation is just a local re-pointing of two parent/child links that keeps the BST ordering intact. Picture the left-leaning chain 30 -> 20 -> 10. Node 20 sits in the middle, with 10 on its left and 30 hanging above on the right. If you grab 20 and pull it up to the top, 30 naturally falls to 20's right (since 30 > 20) and 10 stays on 20's left (since 10 < 20). Nothing about the sorted order changed — only the heights did. The tall side got shorter, the short side got taller, and balance is restored.

This is the left-left case, and its cure is a single right rotation. (Its mirror, right-right, uses a single left rotation; the two zig-zag cases need a double rotation, but they are built from these same two primitives.)

Walk through it

Step through the animation on the right. The number inside each circle is the key; the small bf tag above each node is its current balance factor.

Insert 30 — it is the root, bf 0. Insert 20 — it is less than 30, so it goes left; now 30 has a left subtree but no right subtree, so 30 shows bf +1. Insert 10 — less than both, so it drops to the bottom of the left spine.

Now recompute heights up the path: 20 becomes bf +1, and 30 becomes bf +2 — illegal, and the node flashes as an error. Because the heavy key (10) went left of 20 which went left of 30, this is the left-left case, so we call right_rotate(30). Watch 20 rise to the top, 30 swing down to become 20's right child, and 10 settle as 20's left child. Every bf resets to 0 and the height drops from 3 to 2.

The code, line by line

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.val:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update_height(node)
    bf = balance(node)
    if bf > 1 and key < node.left.val:
        return right_rotate(node)
    return node
 
def right_rotate(y):
    x = y.left
    y.left = x.right
    x.right = y
    update_height(y)
    update_height(x)
    return x
 
def update_height(n):
    hl = height(n.left)
    hr = height(n.right)
    n.height = 1 + max(hl, hr)

• insert is an ordinary recursive BST insert; the AVL work happens on the way back up, after the child has been placed.
• update_height(node) and bf = balance(node) recompute this node's height and balance factor from its (now possibly taller) children.
• Line 10 detects the left-left case: bf > 1 means left-heavy, and key < node.left.val means the new key also went left of the left child. That combination is fixed by a single right rotation.
• right_rotate(y) is the heart of it: x = y.left grabs the left child that will become the new root, y.left = x.right re-parents x's old right subtree under y, and x.right = y hangs the old root beneath x.
• After the pointer swap, update_height(y) then update_height(x) fix the two heights bottom-up (y first, because it is now x's child), and x is returned as the subtree's new root.

Complexity

The key guarantee: because every node obeys |bf| ≤ 1, an AVL tree of n keys has height at most about 1.44 * log2(n). A rotation touches only three nodes and a constant number of pointers, so it is O(1); the only logarithmic cost is descending and unwinding the recursion.

When to use / pitfalls

Practice