AVL Trees

An AVL tree is a self-balancing Binary Search Tree where the height difference between the left and right subtrees of every node is at most 1. Named after its inventors Adelson-Velsky and Landis (1962), it was the first self-balancing BST ever devised. The balancing guarantee eliminates BST degeneration — every operation runs in O(log n) time regardless of insertion order.

The AVL Property

Two concepts define the AVL invariant:

Balance Factor: For any node, the balance factor equals the height of its left subtree minus the height of its right subtree:

$$\text{balance}(node) = \text{height}(node.left) - \text{height}(node.right)$$

AVL Invariant: The balance factor of every node must be −1, 0, or +1:

$$|\text{balance}(node)| \leq 1 \quad \text{for all nodes}$$

When an insertion or deletion violates this invariant (producing a balance factor of −2 or +2), the tree performs one or two rotations to restore balance. These rotations are local operations — they restructure at most three nodes and run in O(1) time.

Node Structure

The AVL node extends the standard BST node with a height field:

class AVLNode {
    int val;
    int height;
    AVLNode left;
    AVLNode right;

    AVLNode(int val) {
        this.val = val;
        this.height = 1; // new node is a leaf with height 1
    }
}

Height is stored (not computed on the fly) because rebalancing needs it at every ancestor during bottom-up updates. Two helper methods keep the code clean:

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

int balanceFactor(AVLNode node) {
    return node == null ? 0 : height(node.left) - height(node.right);
}

void updateHeight(AVLNode node) {
    node.height = 1 + Math.max(height(node.left), height(node.right));
}

The Four Rotations

Rotations are the engine of AVL rebalancing. Each rotation fixes one type of imbalance. Understanding these four cases is essential — interviewers expect you to draw them on a whiteboard and explain when each applies.

Right Rotation (LL Case)

Trigger: A node has balance factor +2 and its left child has balance factor ≥ 0. The tree is “left-heavy on the left side.”

Before:          After:
    z               y
   / \             / \
  y   T4          x   z
 / \             /   / \
x   T3          T1  T3  T4
/
T1

AVLNode rotateRight(AVLNode z) {
    AVLNode y = z.left;
    AVLNode t3 = y.right;

    // Perform rotation
    y.right = z;
    z.left = t3;

    // Update heights (z first, since y depends on z's new height)
    updateHeight(z);
    updateHeight(y);

    return y; // new root of this subtree
}

Node y becomes the new subtree root. Its former right child (T3) becomes z’s left child. The BST property is preserved because all values in T3 are between y and z.

Left Rotation (RR Case)

Trigger: A node has balance factor −2 and its right child has balance factor ≤ 0. The tree is “right-heavy on the right side.”

Before:          After:
  z                 y
 / \               / \
T1   y            z   x
    / \          / \   \
   T2  x        T1  T2  T4
        \
        T4

AVLNode rotateLeft(AVLNode z) {
    AVLNode y = z.right;
    AVLNode t2 = y.left;

    // Perform rotation
    y.left = z;
    z.right = t2;

    // Update heights
    updateHeight(z);
    updateHeight(y);

    return y;
}

This is the mirror image of right rotation.

Left-Right Rotation (LR Case)

Trigger: A node has balance factor +2 and its left child has balance factor < 0. The imbalance is on the left child’s right side — a single rotation cannot fix it.

Before:          Step 1 (Left on y):     Step 2 (Right on z):
    z                z                       x
   / \              / \                     / \
  y   T4           x   T4                 y   z
 / \              / \                     /   / \
T1  x            y   T3                 T1  T3  T4
   / \          / \
  T2  T3       T1  T2

AVLNode rotateLeftRight(AVLNode z) {
    z.left = rotateLeft(z.left);   // Left rotate the left child
    return rotateRight(z);          // Right rotate the root
}

The first rotation transforms the LR case into an LL case. The second rotation fixes it.

Right-Left Rotation (RL Case)

Trigger: A node has balance factor −2 and its right child has balance factor > 0. Mirror of the LR case.

Before:          Step 1 (Right on y):    Step 2 (Left on z):
  z                z                         x
 / \              / \                       / \
T1   y           T1  x                    z   y
    / \              / \                  / \   \
   x  T4           T2  y                T1  T2  T4
  / \                  / \
 T2  T3               T3  T4

AVLNode rotateRightLeft(AVLNode z) {
    z.right = rotateRight(z.right); // Right rotate the right child
    return rotateLeft(z);            // Left rotate the root
}

Rotation Selection Summary

Balance of Node	Balance of Child	Case	Rotation
+2	≥ 0 (left child)	LL	Right
+2	< 0 (left child)	LR	Left-Right
−2	≤ 0 (right child)	RR	Left
−2	> 0 (right child)	RL	Right-Left

Insertion with Rebalancing

AVL insertion follows three steps:

1. Perform standard BST insertion.
2. Update heights from the inserted node up to the root.
3. Check balance factors and apply rotations where needed.

The complete insertion code:

AVLNode insert(AVLNode node, int val) {
    // Step 1: Standard BST insert
    if (node == null) return new AVLNode(val);

    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    } else {
        return node; // duplicates not allowed
    }

    // Step 2: Update height of this ancestor node
    updateHeight(node);

    // Step 3: Get balance factor and rebalance if needed
    int balance = balanceFactor(node);

    // LL Case: left-heavy, and insertion was in left child's left subtree
    if (balance > 1 && val < node.left.val) {
        return rotateRight(node);
    }

    // RR Case: right-heavy, and insertion was in right child's right subtree
    if (balance < -1 && val > node.right.val) {
        return rotateLeft(node);
    }

    // LR Case: left-heavy, and insertion was in left child's right subtree
    if (balance > 1 && val > node.left.val) {
        node.left = rotateLeft(node.left);
        return rotateRight(node);
    }

    // RL Case: right-heavy, and insertion was in right child's left subtree
    if (balance < -1 && val < node.right.val) {
        node.right = rotateRight(node.right);
        return rotateLeft(node);
    }

    return node; // no rebalancing needed
}

How case detection works: After inserting val, the direction of imbalance (left or right) combined with where val landed relative to the imbalanced node’s child determines the rotation type. Comparing val with the child’s value tells you whether the insertion went to the child’s left or right subtree.

Time complexity: O(log n) — BST insertion takes O(log n), and at most two rotations (each O(1)) restore balance.

Space complexity: O(log n) for the recursion stack. The tree height is always O(log n) by the AVL guarantee.

Deletion Overview

AVL deletion is structurally similar to insertion rebalancing but handles more cases:

1. Perform standard BST deletion (three cases: leaf, one child, two children).
2. Update heights bottom-up.
3. Check balance factors at each ancestor.
4. Apply the appropriate rotation.

The critical difference from insertion: deletion can require rotations at multiple ancestors, not a single one. In the worst case, deletion triggers O(log n) rotations — one at each level. Despite this, the total operation remains O(log n).

AVLNode deleteNode(AVLNode node, int val) {
    if (node == null) return null;

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

        AVLNode successor = findMin(node.right);
        node.val = successor.val;
        node.right = deleteNode(node.right, successor.val);
    }

    updateHeight(node);

    int balance = balanceFactor(node);

    // LL
    if (balance > 1 && balanceFactor(node.left) >= 0)
        return rotateRight(node);
    // LR
    if (balance > 1 && balanceFactor(node.left) < 0) {
        node.left = rotateLeft(node.left);
        return rotateRight(node);
    }
    // RR
    if (balance < -1 && balanceFactor(node.right) <= 0)
        return rotateLeft(node);
    // RL
    if (balance < -1 && balanceFactor(node.right) > 0) {
        node.right = rotateRight(node.right);
        return rotateLeft(node);
    }

    return node;
}

AVLNode findMin(AVLNode node) {
    while (node.left != null) node = node.left;
    return node;
}

Notice the case detection uses balanceFactor(node.left) and balanceFactor(node.right) instead of comparing the inserted value. During deletion, you do not know which value was removed from a subtree, so you inspect the child’s balance factor directly.

AVL vs Red-Black Tree Comparison

Both AVL and Red-Black trees are self-balancing BSTs that guarantee O(log n) operations. Their trade-offs matter in system design and interview discussions:

Property	AVL Tree	Red-Black Tree
Balance strictness	|balance| ≤ 1 (strict)	Longest path ≤ 2× shortest
Max height (n nodes)	1.44 log₂(n)	2 log₂(n + 1)
Lookup speed	Faster (shorter height)	Slightly slower
Insertion rotations	At most 2	At most 2
Deletion rotations	Up to O(log n)	At most 3
Insert/Delete speed	Slower (more rotations)	Faster (fewer rotations)
Memory per node	height field (int)	color bit (1 bit)
Used in practice	Read-heavy workloads	General purpose (Java TreeMap)

When to prefer AVL: Applications with far more lookups than insertions/deletions — database indexes where queries vastly outnumber writes.

When to prefer Red-Black: General-purpose ordered maps and sets where inserts and deletes are frequent. All standard library implementations (Java TreeMap, C++ std::map, Linux kernel) use Red-Black trees.

Practical Usage

In real-world Java applications, you rarely implement AVL trees from scratch. Java’s TreeMap and TreeSet use Red-Black trees internally. However, understanding AVL trees is valuable for:

• Interview whiteboard problems: Explaining rotation mechanics and balance restoration.
• Database internals: B-trees (used in database indexes) extend the self-balancing concept to multi-way trees.
• Custom data structures: When you need guaranteed O(log n) lookups in a specialized context — interval trees, augmented order-statistics trees.

Interviewer Tips

Interviewers rarely ask you to implement a full AVL tree from scratch — that takes too long for a 45-minute session. What they do ask:

• “Explain how AVL trees maintain balance.” Describe balance factors and the four rotation cases.
• “Walk through an insertion that triggers a rotation.” Pick a concrete example: insert 3, 2, 1 into an empty AVL tree. After inserting 1, node 3 has balance +2 (LL case), triggering a right rotation that makes 2 the root.
• “What’s the difference between AVL and Red-Black?” Give the comparison table from memory. Emphasize the lookup-vs-write trade-off.
• “Why does Java use Red-Black trees instead of AVL?” Red-Black trees perform fewer rotations on insertion and deletion, and the slightly taller height (2 log n vs 1.44 log n) has negligible impact with modern CPU caches.

If asked to code rotations, start with the single rotation (left or right), then compose the double rotations from them. This modular approach is cleaner and less error-prone.