AlgoPlusAlgoPlus
Learn/Data Structures & Algorithms
Lesson

AVL Tree

A BST that rotates itself back into balance after every insert, guaranteeing O(log n) forever.

9 min read Watch it move Build it

An AVL tree is a binary search tree that *refuses to get lopsided*. A plain BST can degenerate into a slow chain when keys arrive in sorted order; an AVL tree prevents that by checking its shape after every change and fixing it immediately with a rotation. The payoff is a hard guarantee: search, insert, and delete stay O(log n) no matter what order the data arrives in. It is named for its inventors, Adelson-Velsky and Landis.

The balance factor

Each node tracks its balance factor — the height of its left branch minus the height of its right branch. AVL's invariant is that this stays in {-1, 0, +1} at *every* node. The instant an insert pushes some node's balance factor to +2 or -2, the tree rebalances at the lowest node where the violation appears.

Rotations preserve sorted order
A rotation pivots two or three nodes to shift height from the heavy side to the light side — but it never breaks the BST property. The keys stay searchable throughout; only the *shape* changes.

Four cases, two kinds of rotation

  1. 1Left-Left (LL): heavy on the left, inserted into the left's left -> one right rotation at the unbalanced node.
  2. 2Right-Right (RR): heavy on the right, inserted into the right's right -> one left rotation.
  3. 3Left-Right (LR): heavy on the left, inserted into the left's right -> left-rotate the child, then right-rotate the node.
  4. 4Right-Left (RL): mirror image -> right-rotate the child, then left-rotate the node.

Worked example — the sorted-input trap, defused

Insert 10, 20, 30. In a plain BST this makes a right-leaning chain. In an AVL tree, after 30 arrives the root 10 has balance factor -2 (Right-Right case), so a single left rotation lifts 20 to the top:

insert 10, 20, 30 (RR case)

  10                     20
    \                   /  \
     20    --left-->  10    30
       \
        30   (10 has balance factor -2)

result: height 2 instead of 3, perfectly balanced.
AVL vs red-black: how strict?
AVL trees are more rigidly balanced than red-black trees, so they give slightly faster *lookups* but do a bit more rotation work on insert/delete. Read-heavy workloads tend to prefer AVL; write-heavy ones often prefer red-black.
OperationTimeSpace
Search / insert / delete · guaranteed, never degeneratesO(log n)O(log n)
Rotations per insert · at most a double rotationO(1)O(1)
Height · always within a constant of optimal<= 1.44 log n—
Check yourself
After an insert violates balance, how much rotation work does an AVL tree do to restore it?