🌴 AVL Tree
Self-balancing rotations
Setup
Stats
Node count
0
Tree height
0
Last rotation
—
Rotations
0
Info & Theory

An AVL tree (Adelson-Velsky & Landis, 1962) is a binary search tree that keeps itself height-balanced after every insertion and deletion, guaranteeing O(log n) search, insert, and delete in the worst case.

Balance factor

Every node stores a balance factor: height(left) − height(right). The AVL invariant requires this value to stay in {−1, 0, 1} for every node. After a change, heights are recomputed bottom-up from the modified node to the root.

Detecting imbalance

Walking upward, the first ancestor whose balance factor falls outside {−1,0,1} is the pivot for rebalancing.

The four rotation cases

  • LL: left-heavy, left child left-heavy → single right rotation.
  • RR: right-heavy, right child right-heavy → single left rotation.
  • LR: left-heavy, left child right-heavy → rotate left child left, then rotate node right.
  • RL: right-heavy, right child left-heavy → rotate right child right, then rotate node left.

Each rotation is an O(1) pointer rewrite; at most one (single or double) rotation is needed after an insertion, while deletion can require a rotation at every level up to the root.

Why it matters

A plain unbalanced BST degrades to O(n) on sorted input (it becomes a linked list). AVL's strict balance keeps height at O(log n) ≈ 1.44·log₂(n+2), so lookups stay fast regardless of insertion order.

About AVL Tree — Self-Balancing Rotations

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

An AVL tree, named after inventors Georgy Adelson-Velsky and Evgenii Landis who published it in 1962, is the earliest self-balancing binary search tree. Every node stores a balance factor equal to the height of its left subtree minus the height of its right subtree, and the tree maintains the invariant that this value stays within {−1, 0, 1} at all times. After an insertion or deletion, heights are recomputed along the path back to the root, and the first ancestor found to be out of balance is corrected with a single rotation (left-left or right-right imbalance) or a double rotation (left-right or right-left imbalance) — each an O(1) pointer rewrite. This strict discipline keeps the tree height at O(log n) in the worst case, unlike a naive BST which can degrade to a linked list on sorted input. Compared to red-black trees, AVL trees are more rigidly balanced, giving faster lookups at the cost of more frequent rotations on insert and delete, making AVL trees attractive when reads vastly outnumber writes.

Frequently Asked Questions

Why must the balance factor stay within {−1, 0, 1}?

This range is the precise threshold that keeps tree height provably O(log n). Adelson-Velsky and Landis proved that a tree obeying this invariant has height at most about 1.44·log₂(n+2), so allowing balance factors of ±1 gives enough flexibility for efficient insertion while still guaranteeing logarithmic height.

What is the difference between a single and a double rotation?

A single rotation (LL or RR case) fixes an imbalance caused by a subtree that is heavy on the same side as its own heavy child — one pointer rewrite suffices. A double rotation (LR or RL case) handles a "zig-zag" imbalance where the heavy child leans the opposite way, requiring two rotations: first on the child to convert it into a single-rotation case, then on the node itself.

How does an AVL tree compare to a red-black tree?

Both guarantee O(log n) height, but AVL trees enforce a tighter balance invariant, giving shorter trees and faster search. Red-black trees relax the balance constraint (allowing the longest root-to-leaf path to be up to twice the shortest), which means fewer rotations on insert and delete. This makes AVL trees favorable for read-heavy workloads and red-black trees favorable for write-heavy workloads.

Why can deletion require rotations at every level up to the root, unlike insertion?

An insertion only adds height to one subtree, so at most one rotation (single or double) is ever needed to restore balance, after which the overall subtree height is restored to its pre-insertion value. A deletion can reduce a subtree's height, and that reduction can propagate upward, potentially triggering a rebalancing rotation at every ancestor on the path to the root — up to O(log n) rotations in the worst case.