AVL Tree Data Structure Explained Tutorial

What Is an AVL Tree?

An AVL tree is a self-balancing binary search tree in which the height difference between the left and right subtrees of every node is kept within a defined limit. The name AVL comes from Adelson-Velsky and Landis, who introduced the structure.

Like a normal binary search tree, an AVL tree stores smaller values on the left and larger values on the right. The additional balancing rule prevents the tree from becoming excessively skewed after insertions and deletions.

Why Do We Need AVL Trees?

A regular binary search tree can become unbalanced when values are inserted in an unfortunate order. For example, inserting values in increasing order can produce a tree that resembles a linked list.

Searching this tree may require visiting almost every node. The search complexity can therefore degrade to O(n).

An AVL tree detects this imbalance and restructures the tree using rotations. This keeps the tree height logarithmic and maintains O(log n) worst-case search, insertion, and deletion.

AVL Tree Balance Rule

Each AVL node has a balance factor, calculated using the heights of its left and right subtrees.

Balance Factor =
Height(left subtree) - Height(right subtree)

For an AVL tree, the balance factor of every node must be one of: -1, 0, or 1.

Balance Factor	Meaning
0	Left and right subtree heights are equal
1	Left subtree is one level taller
-1	Right subtree is one level taller

A balance factor of 2 or -2 indicates that the node is no longer balanced and requires rebalancing.

Structure of an AVL Node

An AVL node normally stores the value, references to its children, and information about its height. Keeping the height at each node makes it possible to calculate balance factors efficiently.

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

The initial height of a newly created leaf node is commonly represented as 1. Implementations may use a different height convention, but the balance calculations must remain consistent.

Calculating Node Height

The height of a node is one more than the maximum height of its children. A missing child is commonly treated as having height zero in this implementation.

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

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

Calculating the Balance Factor

Once the height of each child is available, the balance factor can be calculated directly.

function getBalance(node) {
  if (node === null) {
    return 0;
  }

  return height(node.left) - height(node.right);
}

This value tells the insertion or deletion algorithm whether the current node is balanced or whether a rotation may be necessary.

AVL Rotations

AVL trees use rotations to restore balance while preserving the binary search tree ordering property. There are two fundamental rotations:

Left rotation
Right rotation

These basic operations are combined to handle four common AVL imbalance cases: LL, RR, LR, and RL.

Right Rotation

A right rotation is commonly used when a node becomes too heavy on its left side.

Before:

      30
     /
   20
  /
10


After:

    20
   /   10   30

A JavaScript implementation can be written as follows:

function rightRotate(root) {
  const newRoot = root.left;
  const subtree = newRoot.right;

  newRoot.right = root;
  root.left = subtree;

  updateHeight(root);
  updateHeight(newRoot);

  return newRoot;
}

Left Rotation

A left rotation is used when a node becomes too heavy on its right side.

Before:

10
     20
           30


After:

    20
   /   10   30

function leftRotate(root) {
  const newRoot = root.right;
  const subtree = newRoot.left;

  newRoot.left = root;
  root.right = subtree;

  updateHeight(root);
  updateHeight(newRoot);

  return newRoot;
}

The Four AVL Imbalance Cases

The type of rotation required depends on where the imbalance occurs relative to the unbalanced node.

Case	Pattern	Rotation
LL	Left of left subtree	Right rotation
RR	Right of right subtree	Left rotation
LR	Right of left subtree	Left rotation, then right rotation
RL	Left of right subtree	Right rotation, then left rotation

LL Case

The LL case occurs when a node becomes unbalanced because a new value is inserted into the left subtree of its left child. A single right rotation restores the balance.

Before:

      30
     /
   20
  /
10


Right rotation:

    20
   /   10   30

RR Case

The RR case occurs when the imbalance is caused by insertion into the right subtree of the right child. A single left rotation restores the balance.

Before:

10
     20
           30


Left rotation:

    20
   /   10   30

LR Case

The LR case occurs when the new value is inserted into the right subtree of the left child. This requires two rotations.

First perform a left rotation on the left child, then perform a right rotation on the unbalanced node.

After:

    20
   /   10   30

RL Case

The RL case occurs when the new value is inserted into the left subtree of the right child. It is resolved using a right rotation followed by a left rotation.

Before:

10
     30
   /
 20

First perform a right rotation on the right child, then perform a left rotation on the unbalanced node.

After:

    20
   /   10   30

AVL Insertion

AVL insertion starts like ordinary binary search tree insertion. After the new node is inserted, the algorithm moves back toward the root, updates node heights, calculates balance factors, and performs rotations when necessary.

The general process is:

Insert the value using normal BST rules.
Update the height of each ancestor.
Calculate the balance factor.
Identify whether the node has become unbalanced.
Apply the appropriate rotation.
Return the new root of the affected subtree.

AVL Insertion Implementation

The following implementation demonstrates the main AVL insertion logic, including height updates and all four rotation cases.

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

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

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

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

function rightRotate(root) {
  const newRoot = root.left;
  const subtree = newRoot.right;

  newRoot.right = root;
  root.left = subtree;

  updateHeight(root);
  updateHeight(newRoot);

  return newRoot;
}

function leftRotate(root) {
  const newRoot = root.right;
  const subtree = newRoot.left;

  newRoot.left = root;
  root.right = subtree;

  updateHeight(root);
  updateHeight(newRoot);

  return newRoot;
}

function insert(root, value) {
  if (root === null) {
    return new Node(value);
  }

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

  updateHeight(root);

  const balance = getBalance(root);

  // LL
  if (balance > 1 && value < root.left.value) {
    return rightRotate(root);
  }

  // RR
  if (balance < -1 && value > root.right.value) {
    return leftRotate(root);
  }

  // LR
  if (balance > 1 && value > root.left.value) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
  }

  // RL
  if (balance < -1 && value < root.right.value) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
  }

  return root;
}

Example of AVL Insertion

Suppose the values 30, 20, and 10 are inserted in that order. A normal BST would become left-heavy.

The root has a balance factor of 2, so the tree is unbalanced. This is an LL case, and a right rotation produces:

   20
  /  10   30

The resulting tree satisfies the AVL balance condition.

AVL Deletion

Deletion in an AVL tree begins with the normal binary search tree deletion process. However, removing a node can change the height of multiple ancestors, so the tree must be checked and rebalanced while moving back toward the root.

The general process is:

Find the node to delete.
Remove it using BST deletion rules.
Update the heights of affected ancestors.
Calculate balance factors.
Apply the required rotations.
Continue rebalancing toward the root.

AVL deletion can require more rebalancing work than insertion because removing a node may reduce subtree height and cause imbalances at multiple levels.

AVL Search

Searching an AVL tree works exactly like searching a binary search tree. At each node, the target is compared with the current value. The search continues into either the left or right subtree.

function search(root, target) {
  if (root === null || root.value === target) {
    return root;
  }

  if (target < root.value) {
    return search(root.left, target);
  }

  return search(root.right, target);
}

Because an AVL tree maintains logarithmic height, the worst-case search complexity is O(log n).

AVL Tree Complexity

Operation	Time Complexity
Search	O(log n)
Insertion	O(log n)
Deletion	O(log n)
Rotation	O(1)
Space	O(n)

The O(log n) bounds depend on maintaining the AVL balance invariant. Without balancing, an ordinary binary search tree can degrade to O(n).

AVL Trees and In-Order Traversal

Rotations change the shape of an AVL tree but preserve the binary search tree ordering. Therefore, an in-order traversal still produces values in sorted order.

function inOrder(root, result = []) {
  if (root === null) {
    return result;
  }

  inOrder(root.left, result);
  result.push(root.value);
  inOrder(root.right, result);

  return result;
}

This property is important because balancing changes the structure without changing the ordered set represented by the tree.

AVL Tree vs Binary Search Tree

Property	Ordinary BST	AVL Tree
Self-balancing	No	Yes
Worst-case search	O(n)	O(log n)
Worst-case insertion	O(n)	O(log n)
Balance information	Not required	Node height
Rotations	Not normally required	Used for rebalancing

AVL Tree vs Red-Black Tree

AVL trees and Red-Black trees are both self-balancing binary search trees, but they use different balancing strategies. AVL trees maintain a stricter height balance, while Red-Black trees use color-based structural rules.

Feature	AVL Tree	Red-Black Tree
Balancing method	Balance factor and height	Node colors and structural rules
Balance strictness	Stricter	Less strict
Search	O(log n)	O(log n)
Typical focus	Maintaining tighter height balance	Efficient updates with bounded height

Where AVL Trees Are Useful

AVL trees are useful when ordered data needs predictable search performance and the workload benefits from a relatively tightly balanced tree. They are particularly relevant when searches are frequent and maintaining a shorter search path is valuable.

Ordered in-memory data
Search-oriented applications
Dictionary and set implementations
Indexing structures
Symbol tables and compiler-related structures
Applications requiring predictable logarithmic search performance

Common AVL Tree Mistakes

Calculating the balance factor using the wrong subtree heights.
Forgetting to update node heights after a rotation.
Confusing LL with LR or RR with RL cases.
Performing rotations in the wrong order for double-rotation cases.
Returning the wrong subtree root after a rotation.
Forgetting to rebalance ancestors after deletion.
Changing child references during rotation without preserving the middle subtree.
Assuming a balanced tree means every node must have exactly equal subtree heights.

Key Takeaways

An AVL tree is a self-balancing binary search tree.
Every node maintains a balance factor of -1, 0, or 1 after rebalancing.
Node height is used to calculate the balance factor.
Left and right rotations restore balance after structural changes.
AVL trees have four major imbalance cases: LL, RR, LR, and RL.
Search, insertion, and deletion have O(log n) worst-case complexity.
Rotations preserve the binary search tree ordering property.

Topics

AVL Tree Data Structure Explained