AVL Trees: Balance Factors, Rotations & Implementation

A standard Binary Search Tree (BST) promises O(log N) average-time operations. However, if keys are inserted in sorted or near-sorted order (e.g., [10, 20, 30, 40, 50]), the tree degrades into a degenerate linked list where search, insertion, and deletion plummet to an unacceptable O(N) linear time.

Named after Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis (1962), the AVL Tree was the first self-balancing binary search tree ever invented. By enforcing a strict height-balance invariant across every node, an AVL tree guarantees that the maximum height never exceeds ≈ 1.44 log2(N), strictly locking worst-case search, insertion, and deletion to O(log N).

The Balance Factor Invariant

The core invariant of an AVL tree is that for every node N, the height difference between its left and right subtrees must differ by at most 1:

BalanceFactor(N) = Height(LeftSubtree) - Height(RightSubtree)

At all times, every node in an AVL tree must satisfy:

BalanceFactor(N) ∈ {-1, 0, +1}

• BF = 0: Perfectly balanced; left and right subtrees have identical height.
• BF = +1: Left-heavy by 1 level (valid).
• BF = -1: Right-heavy by 1 level (valid).
• BF ≥ +2 or BF ≤ -2: Unbalanced! Requires immediate tree rotation.

The 4 Rebalancing Rotations

When an insertion or deletion pushes a node's balance factor to +2 or -2, balance is restored using one of four deterministic tree rotations:

Complete Production-Grade Java Implementation

Below is a production-ready implementation of a complete AVLTree supporting insertion, deletion, rebalancing, and in-order traversal with full height maintenance:

public class AVLTree {
    public static class Node {
        int key;
        int height;
        Node left;
        Node right;

        Node(int key) {
            this.key = key;
            this.height = 1; // Leaf node starts with height 1
        }
    }

    private Node root;

    // Helper: Safely get node height (handles null)
    private int height(Node n) {
        return (n == null) ? 0 : n.height;
    }

    // Helper: Compute balance factor
    private int getBalance(Node n) {
        return (n == null) ? 0 : height(n.left) - height(n.right);
    }

    // Single Right Rotation (Clockwise)
    private Node rightRotate(Node z) {
        Node y = z.left;
        Node T2 = y.right;

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

        // Update heights (z first since it is now child of y)
        z.height = Math.max(height(z.left), height(z.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y; // New root of rotated subtree
    }

    // Single Left Rotation (Counter-Clockwise)
    private Node leftRotate(Node z) {
        Node y = z.right;
        Node T2 = y.left;

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

        // Update heights (z first)
        z.height = Math.max(height(z.left), height(z.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y; // New root
    }

    // Public Insertion API
    public void insert(int key) {
        root = insertRecursive(root, key);
    }

    private Node insertRecursive(Node node, int key) {
        // 1. Standard BST Insertion
        if (node == null) return new Node(key);

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

        // 2. Update height of current ancestor node
        node.height = Math.max(height(node.left), height(node.right)) + 1;

        // 3. Get balance factor to check if it became unbalanced
        int balance = getBalance(node);

        // Case 1: Left-Left (LL) → Single Right Rotate
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }

        // Case 2: Right-Right (RR) → Single Left Rotate
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }

        // Case 3: Left-Right (LR) → Double Rotate (Left then Right)
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Case 4: Right-Left (RL) → Double Rotate (Right then Left)
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // Public Deletion API
    public void delete(int key) {
        root = deleteRecursive(root, key);
    }

    private Node deleteRecursive(Node root, int key) {
        if (root == null) return null;

        // 1. Standard BST Deletion
        if (key < root.key) {
            root.left = deleteRecursive(root.left, key);
        } else if (key > root.key) {
            root.right = deleteRecursive(root.right, key);
        } else {
            // Node found: 0 or 1 child
            if (root.left == null || root.right == null) {
                Node temp = (root.left != null) ? root.left : root.right;
                if (temp == null) {
                    root = null; // No children
                } else {
                    root = temp; // 1 child
                }
            } else {
                // Node with 2 children: get in-order successor (smallest in right subtree)
                Node temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = deleteRecursive(root.right, temp.key);
            }
        }

        if (root == null) return null;

        // 2. Update height
        root.height = Math.max(height(root.left), height(root.right)) + 1;

        // 3. Rebalance
        int balance = getBalance(root);

        // Left-Left
        if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root);

        // Left-Right
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        // Right-Right
        if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root);

        // Right-Left
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

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

Python Implementation

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

class AVLTree:
    def get_height(self, node: AVLNode | None) -> int:
        return node.height if node else 0

    def get_balance(self, node: AVLNode | None) -> int:
        return self.get_height(node.left) - self.get_height(node.right) if node else 0

    def right_rotate(self, z: AVLNode) -> AVLNode:
        y = z.left
        T2 = y.right
        y.right = z
        z.left = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def left_rotate(self, z: AVLNode) -> AVLNode:
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def insert(self, root: AVLNode | None, key: int) -> AVLNode:
        if not root:
            return AVLNode(key)
        
        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)
        else:
            return root

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        balance = self.get_balance(root)

        # Case 1: LL
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # Case 2: RR
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # Case 3: LR
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # Case 4: RL
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

AVL Trees vs Red-Black Trees vs Standard BSTs