AVL Trees

Why Balance Matters

Remember how a BST can become a linked list if you insert sorted data? That's a disaster. A linked list gives you O(n) search instead of O(log n). You need a way to keep the tree balanced.

AVL trees solve this by enforcing a strict rule: for every node, the height difference between its left and right subtrees can never be more than 1. If an insertion or deletion breaks this rule, the tree rotates itself to fix it.

It's like a self-correcting bookshelf. If one side gets too heavy, the shelf automatically rebalances itself. The result is always a tree with height O(log n), guaranteeing fast operations.

Understanding Rotations

There are four rotation cases. A right rotation fixes a left-heavy subtree — the left child becomes the new root, and the old root becomes its right child. A left rotation does the opposite.

Sometimes you need two rotations. Left-right means rotate the left child left, then rotate the node right. Right-left means rotate the right child right, then rotate the node left. These handle the "zig-zag" cases.

Sounds complicated? It is a bit. But once you understand the logic, implementations are straightforward. The key insight is that rotations preserve the BST property while reducing height.

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

function getHeight(node) {
  return node ? node.height : 0;
}

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

function getBalance(node) {
  return node ? getHeight(node.left) - getHeight(node.right) : 0;
}

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

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

AVL vs Regular BST

An AVL tree always has height O(log n), so every operation is guaranteed O(log n). A regular BST can degrade to O(n) in the worst case. That's the main advantage — predictable performance.

The trade-off is that AVL trees do more work during insertions and deletions because of the rotations. If you're mostly reading and rarely writing, an AVL tree is worth it. If you're doing lots of inserts with few reads, a regular BST might be fine.

In practice, most standard library implementations use balanced trees (like red-black trees, a cousin of AVL trees) for their sorted map and set types. Understanding AVL trees gives you the foundation to understand all of them.

function insert(node, value) {
  if (!node) return new AVLNode(value);

  if (value < node.value) {
    node.left = insert(node.left, value);
  } else if (value > node.value) {
    node.right = insert(node.right, value);
  } else {
    return node;
  }

  updateHeight(node);
  const balance = getBalance(node);

  if (balance > 1 && value < node.left.value) {
    return rotateRight(node);
  }
  if (balance < -1 && value > node.right.value) {
    return rotateLeft(node);
  }
  if (balance > 1 && value > node.left.value) {
    node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  if (balance < -1 && value < node.right.value) {
    node.right = rotateRight(node.right);
    return rotateLeft(node);
  }

  return node;
}

let root = null;
[10, 20, 30, 40, 50, 25].forEach(v => root = insert(root, v));
console.log(root.value);