AVL Trees and Rotations

An AVL tree (Adelson-Velsky and Landis, 1962) is a self-balancing BST that stores one extra integer per node — the balance factor — and performs local restructuring called rotations to keep the factor in the range [-1, 0, 1] after every mutation. Because height stays O(log n), all operations remain O(log n) in the worst case.

Balance Factor

balanceFactor(node) = height(node.left) - height(node.right)

A factor of -1, 0, or +1 is acceptable. A factor of -2 or +2 signals an imbalance that must be corrected immediately.

class AVLNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.height = 0;    // leaf starts at height 0
  }
}

function nodeHeight(n) { return n ? n.height : -1; }

function updateHeight(n) {
  n.height = 1 + Math.max(nodeHeight(n.left), nodeHeight(n.right));
}

function balanceFactor(n) {
  return nodeHeight(n.left) - nodeHeight(n.right);
}

The Four Rotation Cases

Every imbalance falls into one of four shapes. Two are single rotations; two are double rotations (a single rotation on a child followed by a single rotation on the current node).

Case 1 — Left-Left (Right Rotation) The left subtree is too tall and the heavy side of the left child is also left.

function rotateRight(y) {
  const x = y.left;
  const T2 = x.right;
  x.right = y;
  y.left = T2;
  updateHeight(y);
  updateHeight(x);
  return x;   // x is the new root of this subtree
}

Case 2 — Right-Right (Left Rotation) Mirror of Case 1.

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

Case 3 — Left-Right (Left then Right Rotation) The left subtree is too tall but the heavy side of the left child is right. Rotate the left child left first, then rotate the current node right.

Case 4 — Right-Left (Right then Left Rotation) Mirror of Case 3.

function rebalance(node) {
  updateHeight(node);
  const bf = balanceFactor(node);

  if (bf > 1) {
    if (balanceFactor(node.left) < 0)
      node.left = rotateLeft(node.left);   // Left-Right: double rotation
    return rotateRight(node);
  }
  if (bf < -1) {
    if (balanceFactor(node.right) > 0)
      node.right = rotateRight(node.right); // Right-Left: double rotation
    return rotateLeft(node);
  }
  return node;  // already balanced
}

Insert With Rebalancing

function insert(node, val) {
  if (!node) 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;  // duplicate — no change

  return rebalance(node);
}

After inserting at a leaf, the recursion unwinds upward. At each ancestor rebalance updates the height and rotates if necessary. At most one or two rotations are needed per insert.

Complexity

Other Self-Balancing Trees

Red-black trees use a color bit (red or black) instead of an explicit height. They allow a slightly looser balance (height up to 2 log n) in exchange for fewer rotations on average — which is why red-black trees back most standard library maps (Java TreeMap, C++ std::map).

Treaps combine a BST with a random priority heap property. No explicit balancing logic is needed because random priorities keep the expected height at O(log n). They are simpler to implement than AVL or red-black trees and useful when the input distribution is unknown.

Up Next

Self-balancing trees solve one specialization of the heap problem. The next track section covers binary heaps — another array-based tree structure optimized for fast min/max extraction.