AVL Tree Visualization — Step by Step

The balance factor

Every AVL node tracks its height, and its balance factor is height(left subtree) − height(right subtree). The AVL rule says this must stay within {−1, 0, +1} at every node: +2 means dangerously left-heavy, −2 dangerously right-heavy. After every insert or delete, the tree walks back up the exact path it came down, recomputing heights and re-checking factors. The first node found with a factor of ±2 is where a rotation happens. In this visualizer, watch the step descriptions: each balance check reports the node's exact factor before the tree decides whether — and how — to rotate.

Single rotations: LL and RR

When a node's factor hits +2 and its left child is not right-heavy (child factor ≥ 0), that is the LL case: the extra weight sits on the left child's left side. One right rotation fixes it — the left child rises to become the subtree root, the old root descends to become its right child, and the child's former right subtree transfers across to hang under the old root. That transfer is safe because its values lie strictly between the two rotating nodes. The RR case is the exact mirror: factor −2 with a right child that is not left-heavy, fixed by one left rotation. Both are O(1) pointer surgery.

Double rotations: LR and RL

A single rotation fails when the weight sits in the *inner* subtree — the zigzag shapes. Factor +2 with a right-heavy left child is the LR case: rotating right would just shift the bulge to the other side. The fix is two rotations — first left-rotate the left child, straightening the zigzag into an LL line, then right-rotate the node itself. RL mirrors this: right-rotate the right child, then left-rotate the node. The visualizer animates every case as choreographed movement — one group of nodes rising, one descending, and the transferred subtree gliding across — and it splits LR and RL into two distinct phases so you can watch each half separately.

An insert-and-rebalance trace

Insert 30, 10, 20 into an empty AVL tree. 30 becomes the root and 10 its left child — all factors fine. Then 20 goes to the right of 10, and unwinding back up finds 30 with balance factor +2 while its left child 10 has factor −1: a zigzag, so LR. Step one left-rotates at 10, making 20 the middle of a straight line; step two right-rotates at 30, and 20 rises to the root with 10 and 30 as its children — a perfect little tree. Now try 10, 20, 30 instead: that triggers the RR case, one left rotation, and 20 ends up as the root again.

The height guarantee

Rotations buy a hard mathematical promise: an AVL tree with n nodes has height at most about 1.44 log₂ n. The proof shows the sparsest possible AVL tree of height h contains a Fibonacci-like minimum number of nodes, so height cannot outrun the node count. Compare a plain BST, whose height can reach n. The consequence is that search, insert, and delete are O(log n) in the *worst case*, not merely on average. The maintenance is cheap, too: an insert performs at most one rebalancing rotation (single or double), while a delete may rotate at several levels on the way up — still O(log n) total work.

What you pay compared to a plain BST

Balance is not free. Versus a plain binary search tree, every AVL node stores an extra height field, and every insert or delete pays to update heights and check balance factors along the path — occasionally triggering rotations. Reads are pure profit: no overhead, and a strictly shorter tree to descend. That trade shapes the standard advice: AVL trees shine when lookups outnumber updates. One semantic difference in this app: the BST workspace accepts duplicate values, while the AVL implementation rejects them. Try both workspaces with the same sorted input — 1, 2, 3, 4, 5 — and watch one grow a chain while the other keeps rotating itself flat.

JavaScript

const height = (n) => (n ? n.height : 0);
const balance = (n) => height(n.left) - height(n.right);
const update = (n) => {
  n.height = 1 + Math.max(height(n.left), height(n.right));
};

function rotateRight(y) {
  const x = y.left;
  y.left = x.right; // transferred subtree crosses over
  x.right = y;
  update(y);
  update(x);
  return x; // x is the new subtree root
}

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left;
  y.left = x;
  update(x);
  update(y);
  return y;
}

function rebalance(node) {
  update(node);
  const bf = balance(node);
  if (bf > 1) { // left-heavy: LL or LR
    if (balance(node.left) < 0) node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  if (bf < -1) { // right-heavy: RR or RL
    if (balance(node.right) > 0) node.right = rotateRight(node.right);
    return rotateLeft(node);
  }
  return node; // still balanced
}

Python

def height(n): return n.height if n else 0
def balance(n): return height(n.left) - height(n.right)

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

def rotate_right(y):
    x = y.left
    y.left = x.right  # transferred subtree crosses over
    x.right = y
    update(y); update(x)
    return x  # x is the new subtree root

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y

def rebalance(node):
    update(node)
    bf = balance(node)
    if bf > 1:  # left-heavy: LL or LR
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)  # LR: fix child first
        return rotate_right(node)
    if bf < -1:  # right-heavy: RR or RL
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)  # RL: fix child first
        return rotate_left(node)
    return node  # still balanced

Java

class AVLNode { int value, height = 1; AVLNode left, right; }

class Rotations {
    static int height(AVLNode n) { return n == null ? 0 : n.height; }
    static int balance(AVLNode n) { return height(n.left) - height(n.right); }
    static void update(AVLNode n) {
        n.height = 1 + Math.max(height(n.left), height(n.right));
    }

    static AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        y.left = x.right; // transferred subtree crosses over
        x.right = y;
        update(y); update(x);
        return x;
    }

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

    static AVLNode rebalance(AVLNode node) {
        update(node);
        int bf = balance(node);
        if (bf > 1) {  // left-heavy: LL, or LR if child leans right
            if (balance(node.left) < 0) node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        if (bf < -1) { // right-heavy: RR, or RL if child leans left
            if (balance(node.right) > 0) node.right = rotateRight(node.right);
            return rotateLeft(node);
        }
        return node;
    }
}