A plain binary search tree promises O(log n) search, insert, and delete — but only if the tree stays roughly balanced. Insert already-sorted data into a plain BST and it degrades into a straight line, with search slowing to O(n). An AVL tree is a self-balancing BST that fixes this by automatically restructuring itself after every insertion or deletion, guaranteeing O(log n) operations no matter what order the data arrives in.

AVL trees (named after inventors Adelson-Velsky and Landis) were the first self-balancing BST structure, and they remain one of the clearest examples of the idea even though other variants like red-black trees are more common in standard libraries today.

The Balance Factor

Every node in an AVL tree tracks its balance factor: the height of its left subtree minus the height of its right subtree. An AVL tree enforces the rule that this value must always be -1, 0, or 1 for every node. The moment an insertion or deletion pushes a node's balance factor outside that range, the tree performs a rotation to restore it.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1  # height of this node's subtree

def height(node):
    return node.height if node else 0

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

Rotations: How Rebalancing Works

A rotation is a local restructuring that swaps a parent and one of its children while preserving the BST ordering invariant (left < node < right everywhere). The simplest case is a right rotation, used when a tree becomes left-heavy:

#      Before                After
#        z                     y
#       /                     / \
#      y          -->        x   z
#     /
#    x

def right_rotate(z):
    y = z.left
    z.left = y.right   # y's right subtree becomes z's left subtree
    y.right = z        # z becomes y's right child

    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y  # y is now the new root of this subtree

A left rotation is the mirror image, used when a tree becomes right-heavy. Two more cases — left-right and right-left — handle "zig-zag" imbalances by combining both rotations: rotate the child first, then rotate the node itself. Together these four cases cover every possible imbalance, and each one only touches a constant number of pointers, so a rotation itself is O(1).

Why This Keeps Insert/Search at O(log n)

After every insertion, an AVL tree walks back up from the newly inserted node to the root, checking the balance factor at each ancestor and rotating wherever it's violated. Because this check-and-rotate happens at every level on the path back to the root, the tree's height is mathematically guaranteed to stay within about 1.44 × log₂(n) — still O(log n), just with a slightly larger constant than a perfectly balanced tree.

The tradeoff is that every insertion and deletion does a bit more work than a plain BST (tracking heights, checking balance, occasionally rotating), which is why AVL trees favor read-heavy workloads — lots of searches, comparatively few writes. If you'd like to see the plain, unbalanced version of this same idea first, the BST tutorial covers it without the rebalancing machinery.