AVL Tree — Height Update Order That Breaks Rotations

How AVL Trees Work — Plain English and Rotations

An AVL tree is a self-balancing BST that maintains the invariant: for every node, |height(left) - height(right)| <= 1 (balance factor in {-1, 0, 1}). This guarantees O(log n) height, giving O(log n) search, insert, and delete.

After every insert/delete, the tree checks balance factors bottom-up. If any node becomes unbalanced (factor becomes -2 or 2), a rotation is applied.

Four rotation cases: 1. Left-Left (LL): right rotation on the unbalanced node. 2. Right-Right (RR): left rotation on the unbalanced node. 3. Left-Right (LR): left rotation on left child, then right rotation on node. 4. Right-Left (RL): right rotation on right child, then left rotation on node.

Worked example — insert 3, 2, 1 into AVL tree: Insert 3: [3]. BF(3)=0. Insert 2: [3, left=2]. BF(3)=-1. OK. Insert 1: [3, left=2, 2.left=1]. BF(3)=-2! Left-Left case. Right rotate at 3: 2 becomes root. 2.right=3. 2.left=1. 2 / 1 3 BF(2)=0, BF(1)=0, BF(3)=0. Balanced.

Advantages and Disadvantages of AVL Trees

Advantages: - Guaranteed O(log n) search, insert, delete due to strict balance. - Faster lookups than Red-Black trees (height ≤ 1.44 log n). - Simple to implement recursively.

Disadvantages: - More rotations during deletions (cascade up to O(log n)). - Extra memory per node (height integer). - Not ideal for write-heavy workloads compared to Red-Black trees.

Table: | Aspect | Advantage | Disadvantage | |--------|-----------|---------------| | Search | O(log n) guaranteed | None | | Insert | O(log n), ≤1 rotation | More complex than BST | | Delete | O(log n) | Cascade rotations; code complexity | | Memory | Only height field | Slightly more than BST | | Use case | Read-heavy | Write-heavy better for Red-Black |

Balance Factor and Height

The fundamental invariant of an AVL tree is the Balance Factor (BF). BF = height(left subtree) - height(right subtree). For a tree to remain an AVL tree, every single node must have a BF of -1, 0, or +1. If a node hits +2 or -2, it is 'unbalanced' and requires immediate rotation.

In production code, we store the height in each node rather than recalculating it recursively to keep our operations at O(1) per node visited.

package io.thecodeforge.java.dsa;

/**
 * Production-grade AVL Node structure.
 * Storing height explicitly avoids O(N) recalculations.
 */
public class AVLNode {
    public int key, height;
    public AVLNode left, right;

    public AVLNode(int key) {
        this.key = key;
        this.height = 1; // New nodes are leaves with height 1
    }

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

    public static int getBalanceFactor(AVLNode node) {
        return (node == null) ? 0 : getHeight(node.left) - getHeight(node.right);
    }

    public void updateHeight() {
        this.height = 1 + Math.max(getHeight(this.left), getHeight(this.right));
    }
}

The Four Rotation Cases

When a node becomes unbalanced

package io.thecodeforge.java.dsa;

public class AVLUtility {

    public static AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode t2 = x.right;

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

        // Update heights in correct order (bottom-up)
        y.updateHeight();
        x.updateHeight();

        return x; // New root of subtree
    }

    public static AVLNode rotateLeft(AVLNode x) {
        AVLNode y = x.right;
        AVLNode t2 = y.left;

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

        // Update heights
        x.updateHeight();
        y.updateHeight();

        return y; // New root of subtree
    }

    public static AVLNode rebalance(AVLNode node) {
        node.updateHeight();
        int balance = AVLNode.getBalanceFactor(node);

        // LL Case
        if (balance > 1 && AVLNode.getBalanceFactor(node.left) >= 0)
            return rotateRight(node);

        // LR Case
        if (balance > 1 && AVLNode.getBalanceFactor(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        // RR Case
        if (balance < -1 && AVLNode.getBalanceFactor(node.right) <= 0)
            return rotateLeft(node);

        // RL Case
        if (balance < -1 && AVLNode.getBalanceFactor(node.right) > 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }
}

LL Rotation — Step 1: Initial Unbalanced State

The tree has a left-left imbalance at node 10. The left subtree height is 2, right subtree height is 0, balance factor = +2.

LL Rotation — Step 2: Apply Right Rotation

During the right rotation, the left child (5) becomes the new root. The right subtree of 5 (T2) becomes the left subtree of 10. Pointers are updated in O(1).

LL Rotation — Step 3: Final Balanced Tree

After updating heights and reassigning pointers, the tree is balanced. Height of root is 2, both children have height 1. Balance factors are 0.

RR Rotation — Step 1: Initial Unbalanced State

Mirror case of LL. Root 10 has right subtree height 2, left subtree height 0, balance factor = -2.

RR Rotation — Step 2: Apply Left Rotation

In a left rotation, the right child (15) becomes the new root. The left subtree of 15 becomes the right subtree of 10.

RR Rotation — Step 3: Final Balanced Tree

After rotation, root is 15 with left child 10 and right child 20. Heights are 2,1,1. Balanced.

LR Rotation — Step 1: Initial Unbalanced State

Root 10 has left subtree height 2, right subtree height 0. Left child 5 has right child 7, causing a left-right imbalance (BF = +2, left child BF = -1).

LR Rotation — Step 2: Left Rotate Left Child

First, perform a left rotation on the left child (5). The child's right child (7) becomes new left child of root. This converts the imbalance to LL case.

LR Rotation — Step 3: Right Rotate Root (Final)

Now apply a right rotation on the root (10). The new root 7 becomes parent, with left child 5 and right child 10. All nodes balanced.

RL Rotation — Step 1: Initial Unbalanced State

Root 10 has right subtree height 2, left subtree height 0. Right child 15 has left child 12, causing right-left imbalance (BF = -2, right child BF = +1).

RL Rotation — Step 2: Right Rotate Right Child

First, right rotate the right child (15). The left child of 15 (12) becomes new right child of root. Now it's an RR case.

RL Rotation — Step 3: Left Rotate Root (Final)

Now left rotate the root (10). The new root 12 becomes parent, with left child 10 and right child 15. All nodes balanced.

Insertion and Recursive Rebalancing

Insertion in an AVL tree follows standard BST logic, but as the recursion 'unwinds' (goes back up the tree), we call our rebalance function on every parent node. This ensures the entire path from the new leaf to the root is checked and fixed if needed.

package io.thecodeforge.java.dsa;

public class AVLTree {
    private AVLNode root;

    public void insert(int key) {
        root = insertRecursive(root, key);
    }

    private AVLNode insertRecursive(AVLNode node, int key) {
        if (node == null) return new AVLNode(key);

        if (key < node.key) {
            node.left = insertRecursive(node.left, key);
        } else if (key > node.key) {
            node.right = insertRecursive(node.right, key);
        } else {\n            return node; // Duplicate keys not allowed\n        }

        // Rebalance during call stack unwinding
        return AVLUtility.rebalance(node);
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        // Inserting sorted data that would break a normal BST
        int[] data = {10, 20, 30, 40, 50, 25};
        for (int val : data) tree.insert(val);
        
        System.out.println("Tree Balanced. Root is: " + tree.root.key);
    }
}

Deletion in AVL Trees — Cascade Balancing

Deletion in AVL is more involved than insertion because removing a node can cause multiple rotations up the tree (cascade). After standard BST deletion, we rebalance from the parent of the removed node upward, potentially causing rotations at multiple levels.

Steps: 1. Perform BST deletion (three cases: leaf, one child, two children via successor). 2. Rebalance starting from the parent of the physically removed node. 3. Continue rebalancing up the tree until root or no imbalance.

Unlike insertion which requires at most one rotation per operation, deletion can require O(log n) rotations in worst case.

package io.thecodeforge.java.dsa;

public class AVLTreeDeletion {

    // Delete node with given key, return new root
    public static AVLNode delete(AVLNode root, int key) {
        if (root == null) return null;

        if (key < root.key) {
            root.left = delete(root.left, key);
        } else if (key > root.key) {
            root.right = delete(root.right, key);
        } else {\n            // Node with only one child or no child\n            if (root.left == null)\n                return root.right;\n            else if (root.right == null)\n                return root.left;\n\n            // Node with two children: get inorder successor\n            AVLNode successor = minValueNode(root.right);\n            root.key = successor.key;\n            root.right = delete(root.right, successor.key);\n        }

        // Rebalance this node
        return AVLUtility.rebalance(root);
    }

    private static AVLNode minValueNode(AVLNode node) {
        AVLNode current = node;
        while (current.left != null)
            current = current.left;
        return current;
    }
}

C++ Implementation of AVL Tree

Below is a complete production-quality C++ implementation of an AVL tree, including node structure, rotations, insertion, deletion, and rebalancing.

#include <iostream>
#include <algorithm>

struct Node {
    int key, height;
    Node *left, *right;
    Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};

int getHeight(Node* n) { return n ? n->height : 0; }
int getBalance(Node* n) { return n ? getHeight(n->left) - getHeight(n->right) : 0; }

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    return x;
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
    return y;
}

Node* rebalance(Node* node) {
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
    int bf = getBalance(node);
    if (bf > 1 && getBalance(node->left) >= 0) return rotateRight(node);
    if (bf > 1 && getBalance(node->left) < 0) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (bf < -1 && getBalance(node->right) <= 0) return rotateLeft(node);
    if (bf < -1 && getBalance(node->right) > 0) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    return node;
}

Node* insert(Node* node, int key) {\n    if (!node) return new Node(key);\n    if (key < node->key) node->left = insert(node->left, key);\n    else if (key > node->key) node->right = insert(node->right, key);\n    else return node;\n    return rebalance(node);\n}

Node* minValueNode(Node* node) {
    while (node->left) node = node->left;
    return node;
}

Node* deleteNode(Node* root, int key) {\n    if (!root) return root;\n    if (key < root->key) root->left = deleteNode(root->left, key);\n    else if (key > root->key) root->right = deleteNode(root->right, key);\n    else {\n        if (!root->left || !root->right) {\n            Node* temp = root->left ? root->left : root->right;\n            delete root;\n            return temp;\n        } else {
            Node* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }
    return rebalance(root);
}

void inorder(Node* root) {
    if (root) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

int main() {
    Node* root = nullptr;
    int keys[] = {10, 20, 30, 40, 50, 25};
    for (int key : keys) root = insert(root, key);
    inorder(root);
    std::cout << std::endl;
    root = deleteNode(root, 40);
    inorder(root);
    return 0;
}

Visualizing Deletion — Case 1: Leaf Node

Deleting a leaf node is straightforward: remove the node and rebalance its parent. The diagram shows the removal of node 3 (leaf) from a small AVL tree.

Visualizing Deletion — Case 2: Node with One Child

When the node has one child, replace the node with its child and rebalance. Here, node 5 (with right child 7) is removed and replaced by 7.

Visualizing Deletion — Case 3: Node with Two Children

For a node with two children, we find the inorder successor (smallest in right subtree), copy its key, and then delete the successor. The diagram shows deleting root 10, replacing with 12 (successor), then rebalancing.

AVL vs Red-Black Trees — When to Choose AVL

Both AVL and Red-Black trees guarantee O(log n) operations, but with different constants: - AVL: stricter balance (height ≤ 1.44 log n). Better search performance. - Red-Black: looser balance (height ≤ 2 log n). Faster insert/delete because fewer rotations (O(1) per operation).

AVL consumes slightly more memory per node (stores height as integer; Red-Black stores a color bit). For millions of nodes, the difference is negligible.

Practice Problems for AVL Trees

1. Convert Sorted Array to Binary Search Tree – [LeetCode 108](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/): Build a height-balanced BST from sorted array.
2. Balance a Binary Search Tree – [LeetCode 1382](https://leetcode.com/problems/balance-a-binary-search-tree/): Convert an unbalanced BST into a balanced one.
3. Delete Node in a BST – [LeetCode 450](https://leetcode.com/problems/delete-node-in-a-bst/): Standard BST deletion, foundation for AVL deletion.
4. Insert into a Binary Search Tree – [LeetCode 701](https://leetcode.com/problems/insert-into-a-binary-search-tree/): BST insertion base.
5. Kth Smallest Element in a BST – [LeetCode 230](https://leetcode.com/problems/kth-smallest-element-in-a-bst/): Use inorder traversal; works on AVL too.
6. Validate Binary Search Tree – [LeetCode 98](https://leetcode.com/problems/validate-binary-search-tree/): Ensure BST property holds after insertions/deletions.
7. Construct Binary Search Tree from Preorder Traversal – [LeetCode 1008](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/): Reconstruct BST, checking balance.

Applications of AVL Trees

AVL trees are used in systems where guaranteed fast lookups are critical. Two notable applications:

1. Database Indexing (B-Tree Context): While databases typically use B-Trees (or B+ Trees) for on-disk indexes due to I/O optimization, AVL trees are used for in-memory indexes or as a building block. B-Trees are more efficient for disk-based storage because they minimize disk seeks with high fanout, whereas AVL trees are better suited for main memory due to pointer overhead. However, AVL's strict balance ensures predictable O(log n) search times, which is useful for small in-memory lookup tables or as an alternative to hash tables when range queries are needed.

2. Linux Completely Fair Scheduler (CFS): The Linux kernel uses a Red-Black tree (closely related to AVL) for task scheduling. CFS maintains a tree of runnable tasks with virtual runtime as the key. The choice of Red-Black over AVL is because Red-Black requires fewer rotations on deletion, which is frequent in scheduling. However, AVL's better search performance could benefit systems with read-dominant scheduling patterns.

Other uses: in-memory databases (Redis uses skip lists), memory management, and symbol tables in compilers.