Data Structures algorithms / interactive lesson

AVL Self-Balancing Tree

Insert values into a self-balancing binary search tree. Follow the search path, recompute heights, inspect balance factors, and watch LL, RR, LR, and RL rotations repair local imbalances.

University Guided lesson

Snapshot 1/78

AVL tree / orange = active / cyan = search path / violet = rotation / badge = balance factor

Insertion timeline

Start with an empty AVL tree

About the algorithm

An AVL tree is a self-balancing binary search tree. It stores a small height summary at every node and repairs local imbalances with rotations after an insertion or deletion. The result keeps search paths logarithmic even when values arrive in an unfriendly order.

History

AVL trees were introduced in 1962 by Georgy Adelson-Velsky and Evgenii Landis. They were the first published self-balancing binary search trees. Their name comes from the initials of their creators.

How it works

Insert a value exactly as in an ordinary binary search tree. Then walk back toward the root, recompute each height, and inspect balance factor = height(left) - height(right). Values -1, 0, and 1 are valid. Any larger difference triggers a local repair.

Rotations and uses

Outer-heavy LL and RR shapes need one rotation. Inner-heavy LR and RL shapes need two. Rotations preserve in-order traversal while reducing height. AVL trees fit indexes and in-memory lookup tables where consistently fast reads matter.

Code companion

Connect each visual decision to an implementation pattern.

insert(node, value):
  if node is empty:
    return new leaf(value)

  if value < node.value:
    node.left = insert(node.left, value)
  else:
    node.right = insert(node.right, value)

  node.height = 1 + max(height(node.left), height(node.right))
  balance = height(node.left) - height(node.right)

  if balance > 1 and value < node.left.value: return rotateRight(node)  // LL
  if balance < -1 and value > node.right.value: return rotateLeft(node) // RR
  if balance > 1: node.left = rotateLeft(node.left)                     // LR
  if balance < -1: node.right = rotateRight(node.right)                 // RL

  return rotate node if needed, otherwise node