AVL Tree

AVL Tree (Self-Balancing BST)

An AVL Tree is a self-balancing Binary Search Tree where the difference in heights of left and right subtrees (balance factor) is at most 1 for every node.

Steps:

  1. Start with an empty AVL Tree.
  2. Insert nodes like a regular BST.
  3. After each insertion or deletion, update the height of the affected nodes.
  4. Calculate the balance factor (height(left) - height(right)).
  5. If balance factor is not between -1 and 1, perform rotations to restore balance.

Code:

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

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

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

  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
    x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right));
    return x;
  }

  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right));
    y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
    return y;
  }

  insert(node, value) {
    if (!node) return new AVLNode(value);
    if (value < node.value) node.left = this.insert(node.left, value);
    else if (value > node.value) node.right = this.insert(node.right, value);
    else return node;

    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    const balance = this.getBalance(node);

    // Left Left Case
    if (balance > 1 && value < node.left.value) return this.rotateRight(node);

    // Right Right Case
    if (balance < -1 && value > node.right.value) return this.rotateLeft(node);

    // Left Right Case
    if (balance > 1 && value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }

    // Right Left Case
    if (balance < -1 && value < node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }
}

✅ Pros:

  • Always balanced — guarantees O(log n) insert, delete, and search.
  • Better performance for dynamic data with frequent insertions/deletions.
  • Used in databases and memory-intensive systems.

❌ Cons:

  • More complex to implement than regular BST.
  • Rotations add overhead during insertion and deletion.
  • Slightly slower than simple BSTs for read-only operations.

AVL Tree Visualization