Home/Trees/AVL tree
Search algorithmsCTRL K

AVL tree

· self-balancing · the four rotations
/trees/avl-tree
NODES
1/ 12
in the tree
ROTATIONS
0
so far
HEIGHT
1
levels, root included
BALANCE
0
left height − right height
COMPARISONS
0
key against key
comparingpathnew noderotating
12 keys · seed 7 · 89 steps
step 0 / 88
Keys12
avl_tree.ts
1
function insert(node: Node | null, key: number): Node {
2
  if (node === null) return { key, left: null, right: null, height: 1 };
3
  if (key < node.key) node.left = insert(node.left, key);
4
  else node.right = insert(node.right, key);
5
  node.height = 1 + Math.max(height(node.left), height(node.right));
6
  const balance = height(node.left) - height(node.right);
7
  if (balance > 1 && key < node.left!.key) return rotateRight(node);
8
  if (balance < -1 && key > node.right!.key) return rotateLeft(node);
9
  if (balance > 1) { node.left = rotateLeft(node.left!); return rotateRight(node); }
10
  if (balance < -1) { node.right = rotateRight(node.right!); return rotateLeft(node); }
11
  return node;
12
}
13
function rotateRight(node: Node): Node {
14
  const pivot = node.left!;
15
  node.left = pivot.right;
16
  pivot.right = node;
17
  update(node); update(pivot);
18
  return pivot;
19
}
CURRENT STEP
line 2

The tree is empty: 24 becomes the root.

// how it works

Understanding AVL tree

AVL · heights may differ by one, never by two
01

The idea

An AVL tree is a binary search tree that stores the height of every node and keeps the balance factor, left height minus right height, within −1, 0 or +1. Insertion walks down like a plain BST, then on the way back up recomputes heights; the first node whose balance reaches ±2 is rebalanced by a rotation.

There are four cases. Left-left and right-right take a single rotation: the heavy child comes up and the node drops to the other side. Left-right and right-left first rotate the child to turn the case into a single one, then rotate the node. The label under each node is its balance factor.

02

The four stages

1
descendlike a plain BST insert
2
updateheight and balance on the way back up
3
rotatebalance ±2: single or double rotation
4
settleat most one rebalance per insertion
03

Complexity

best
O(log n)height ≤ 1.44 log₂ n
average
O(log n)search, insert and delete alike
worst
O(log n)guaranteed, whatever the input order
space
O(n)one height per node
04

Versus its siblings

WORST HEIGHT · 1 000 000 KEYS
bst, random
60
bst, sorted
1M
avl
29
red-black
40
b-tree, order 128
3
a lookup costs one comparison per level
05

Pseudocode

INSERT(node, key)
  insert as in a BST, then on the way back up:
  height(node) ← 1 + max(height(left), height(right)); balance ← height(left) − height(right)
  if balance = +2 and the key went left-left: ROTATERIGHT(node)
  if balance = −2 and the key went right-right: ROTATELEFT(node)
  if balance = +2 (left-right): left ← ROTATELEFT(left); ROTATERIGHT(node)
  if balance = −2 (right-left): right ← ROTATERIGHT(right); ROTATELEFT(node)
06

When to use

Lookup-heavy ordered sets: the strict balance makes AVL the shallowest of the binary trees.
In-memory indexes where the input order is adversarial, such as sorted batches.
07

Pitfalls

Deletion can need a rotation at every level on the way up, unlike insertion.
Storing heights as full integers wastes space; the balance factor fits in two bits.
Rotations must fix parent pointers too if the nodes carry them; a missed link corrupts the tree silently.
08

History

Georgy Adelson-Velsky and Evgenii Landis published the tree in 1962; it was the first self-balancing search tree and takes its name from their initials. Knuth called it one of the most elegant data structures known, and it remains the reference against which red-black trees and B-trees are compared.

Back to Trees