Home▸Algorithms & AI▸AVL Tree — Self-Balancing Rotations

🌳 AVL Tree — Self-Balancing Rotations

Insert and delete keys in an AVL tree and watch balance factors update after every change. When a subtree tips past ±1, single and double rotations restore height balance automatically.

Algorithms & AI2DAdvanced60 FPS

About AVL Tree — Self-Balancing Rotations

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.

⚙ Under the hood

Insert and delete keys in an AVL tree and watch balance factors update after every change. When a subtree tips past ±1, single and double rotations restore height balance automatically.

data structurestreesalgorithmsbalancingcomputer science

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install