AVL Trees

Fix one height convention and use it everywhere

These notes use height(null) = 0 and height(leaf) = 1. For a non-null node,height = 1 + max(height(left), height(right)). Define the balance factor as BF(v) = height(v.left) − height(v.right); positive means left-heavy and negative means right-heavy. The alternative null = −1, leaf = 0 convention is equally valid, but mixing conventions creates off-by-one bugs.

Interactive: insert into an AVL tree

This original visualization shows rotations occurring during live insertion. Insert ascending or descending keys and compare the shape with a plain BST built from the same sequence.

Interactive: derive LL, RR, LR, and RL repairs

Switch among the four imbalance shapes. Track the balance factor, the subtree root returned by each rotation, the preserved inorder sequence, and why the demoted node's height must be updated before the promoted node's height.

A rotation is an order-preserving local rewrite

Classify imbalance from subtree balance, not from names alone

In insertion-only explanations, the newly inserted key can identify LL/RR/LR/RL. That shortcut is unsafe for deletion because the removed key is no longer on the heavy path. Inspect child balance factors instead.

Insertion: BST update, height update, rebalance

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


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


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


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


def rotate_right(y):
    x = y.left
    middle = x.right
    x.right = y
    y.left = middle
    update(y)                 # demoted first
    update(x)
    return x


def rotate_left(x):
    y = x.right
    middle = y.left
    y.left = x
    x.right = middle
    update(x)                 # demoted first
    update(y)
    return y


def rebalance(node):
    update(node)
    bf = balance(node)
    if bf > 1:
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node             # reject duplicate
    return rebalance(node)

final class AvlTree {
static final class Node {
    int key, height = 1;
    Node left, right;
    Node(int key) { this.key = key; }
}

static int height(Node node) {
    return node == null ? 0 : node.height;
}

static void update(Node node) {
    node.height = 1 + Math.max(height(node.left), height(node.right));
}

static int balance(Node node) {
    return height(node.left) - height(node.right);
}

static Node rotateRight(Node y) {
    Node x = y.left;
    Node middle = x.right;
    x.right = y;
    y.left = middle;
    update(y);                 // demoted first
    update(x);
    return x;
}

static Node rotateLeft(Node x) {
    Node y = x.right;
    Node middle = y.left;
    y.left = x;
    x.right = middle;
    update(x);                 // demoted first
    update(y);
    return y;
}

static Node rebalance(Node node) {
    update(node);
    int bf = balance(node);
    if (bf > 1) {
        if (balance(node.left) < 0) {
            node.left = rotateLeft(node.left);
        }
        return rotateRight(node);
    }
    if (bf < -1) {
        if (balance(node.right) > 0) {
            node.right = rotateRight(node.right);
        }
        return rotateLeft(node);
    }
    return node;
}

static Node insert(Node node, int key) {
    if (node == null) return new Node(key);
    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    } else {
        return node;           // reject duplicate
    }
    return rebalance(node);
}
}

Deletion can propagate imbalance to the root

First perform ordinary BST deletion. Removing a node can shorten a subtree. Even after one ancestor is rotated, the repaired subtree may remain one level shorter than before, so its parent can become unbalanced too. Continue recomputing and rebalancing on the entire return path. There can be O(log n) rebalanced ancestors, with at most a constant number of rotations at each.

# Uses Node and rebalance from the insertion implementation.
def delete(node, key):
    if node is None:
        return None

    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left

        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.key = successor.key
        node.right = delete(node.right, successor.key)

    return rebalance(node)     # every surviving ancestor

final class AvlDelete {
static final class Node {
    int key, height = 1;
    Node left, right;
    Node(int key) { this.key = key; }
}

static int height(Node node) {
    return node == null ? 0 : node.height;
}

static void update(Node node) {
    node.height = 1 + Math.max(height(node.left), height(node.right));
}

static int balance(Node node) {
    return height(node.left) - height(node.right);
}

static Node rotateRight(Node y) {
    Node x = y.left;
    Node middle = x.right;
    x.right = y;
    y.left = middle;
    update(y);
    update(x);
    return x;
}

static Node rotateLeft(Node x) {
    Node y = x.right;
    Node middle = y.left;
    y.left = x;
    x.right = middle;
    update(x);
    update(y);
    return y;
}

static Node rebalance(Node node) {
    update(node);
    int bf = balance(node);
    if (bf > 1) {
        if (balance(node.left) < 0) node.left = rotateLeft(node.left);
        return rotateRight(node);
    }
    if (bf < -1) {
        if (balance(node.right) > 0) node.right = rotateRight(node.right);
        return rotateLeft(node);
    }
    return node;
}

static Node delete(Node node, int key) {
    if (node == null) return null;

    if (key < node.key) {
        node.left = delete(node.left, key);
    } else if (key > node.key) {
        node.right = delete(node.right, key);
    } else {
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;

        Node successor = node.right;
        while (successor.left != null) {
            successor = successor.left;
        }
        node.key = successor.key;
        node.right = delete(node.right, successor.key);
    }

    return rebalance(node);    // every surviving ancestor
}
}

Why the height is logarithmic

Let N(h) be the fewest nodes in an AVL tree of height h under the leaf-height-1 convention. To make a height-h tree as sparse as possible while remaining balanced, one child has height h − 1 and the other h − 2:

This grows like the Fibonacci sequence, exponentially in h. Inverting the relationship gives h = O(log n). Since a binary tree can also require Ω(log n) height, AVL height is Θ(log n). A path operation and its recursive stack both use O(log n) space/time depth in the worst case; search itself can be iterative with Θ(1) auxiliary space.

Audit all invariants in one postorder pass

A useful test helper returns facts upward rather than recomputing height repeatedly. It checks strict BST bounds, derives the actual height, compares it with the stored value, and rejects a balance factor outside −1…1.

Language-neutral pseudocode

audit(node, low, high):
    if node is null:
        return (valid=true, actualHeight=0, nodeCount=0)
 
    if not (low < node.key < high):
        return (valid=false, actualHeight=0, nodeCount=0)
 
    L = audit(node.left,  low,      node.key)
    if not L.valid:
        return L
 
    R = audit(node.right, node.key, high)
    if not R.valid:
        return R
 
    actual = 1 + max(L.actualHeight, R.actualHeight)
 
    valid = node.height == actual
            and abs(L.actualHeight - R.actualHeight) <= 1
 
    return (valid, actual, 1 + L.nodeCount + R.nodeCount)

Run this after randomized insert/delete sequences in tests. Comparing inorder output with a trusted sorted set catches membership errors; the structural audit catches stale heights and balance violations that output alone cannot see.

Trade-offs: balance is not free

AVL nodes need at least height or balance metadata. Rotations also require pointer writes and careful updates to parent links and augmentations. Tighter height can improve lookup path length, while red-black trees often trade slightly taller paths for less rebalancing in update-heavy workloads. Actual performance also depends on allocation and cache locality.

Pitfalls that corrupt the next operation