Module 6 · Interactive topic

AVL Trees

A BST that balances itself with rotations

A plain BST can turn into a long line and become slow. An AVL tree checks the balance factor of every node on the way back up after an insert or delete, and when one becomes ±2 it rotates a few links to make the tree short again. Every operation stays O(log n).

  • Balance factorheight(left) − height(right)
  • Ruleevery balance is −1, 0 or +1
  • Fixrotate: LL, RR, LR, RL
AVL Tree Ready
nodes 5
height 3
root 30
  • Current
  • Path / y, x
  • Unbalanced
  • New / fixed
  • +1balance = height(left) − height(right)

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

What does an AVL node store?

The same as a BST node, plus its height. Here a leaf has height 1 and NULL has height 0. From the heights of the two children we get the balance factor = height(left) − height(right). In an AVL tree it must always be −1, 0 or +1 — the small badge on every node in the visualizer shows it.

struct Node {
    int key;
    struct Node *left, *right;
    int height;          // leaf = 1
};

int height(struct Node *n) {
    return n == NULL ? 0 : n->height;
}

int balance(struct Node *n) {
    return height(n->left) - height(n->right);
}

Balance factor

  1. balance = height(left) − height(right).
  2. +1: left side is one level taller.
  3. −1: right side is one level taller.
  4. ±2: too unbalanced — rotate!

Insert

  1. Insert like a normal BST (a new leaf).
  2. Walk back up to the root.
  3. Update each node's height and balance.
  4. At most ONE rotation (single or double) fixes it.

LL and RR: one rotation

  1. LL: the extra height is left of the left child.
  2. Rotate RIGHT at the unbalanced node z.
  3. RR is the mirror image: rotate LEFT.
  4. Only 3 links change — O(1).

LR and RL: two rotations

  1. LR: extra height is right of the left child (a zig-zag).
  2. First rotate LEFT at the child y — now it is LL.
  3. Then rotate RIGHT at z.
  4. RL is the mirror image.

Delete

  1. Delete like a normal BST.
  2. Walk back up, updating heights and balances.
  3. Pick the case from the CHILD's balance.
  4. Unlike insert, several rotations may be needed.

Build tree

  1. Start with an empty tree.
  2. Insert the typed values one by one, in that order.
  3. An insert rotates only when a balance becomes ±2.
  4. Compare the height with a plain BST built the same way.

Try each rotation (Rotate tab)

  1. Pick LL, RR, LR or RL.
  2. A small unbalanced tree appears, with the red ±2.
  3. Follow z, y and x, and the subtree that moves across.
  4. The sorted (inorder) order never changes.

Why it is worth it

  1. Height stays below about 1.44 · log₂ n.
  2. Search, insert and delete are all O(log n)…
  3. …even for sorted input (try the Sorted button).
  4. Rotations never change the sorted (inorder) order.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 RIGHT-ROTATE(z) // z is left-heavy
2 y ← z.left
3 z.left ← y.right // y's right subtree moves across
4 y.right ← z
5 update height(z), then height(y)
6 return y // y is the new root of this part
Complexity

How fast is each operation?

n = number of nodes. An AVL tree's height is always O(log n), so no operation ever degrades to O(n) like a skewed BST. A single rotation is O(1). Building a tree of n values is n inserts, so O(n log n).

Operation Best Average Worst Speed
Search O(1) O(log n) O(log n) Grows with n
Insert O(log n) O(log n) O(log n) Grows with n
Delete O(log n) O(log n) O(log n) Grows with n
One rotation O(1) O(1) O(1) Instant
Build tree (n values) O(n log n) O(n log n) O(n log n) Grows with n

The four cases

Case Unbalanced node z Where the extra height is Fix
LL balance +2 Left child's LEFT side Right rotation at z
RR balance −2 Right child's RIGHT side Left rotation at z
LR balance +2 Left child's RIGHT side Left rotation at y, then right rotation at z
RL balance −2 Right child's LEFT side Right rotation at y, then left rotation at z

BST vs AVL tree

Plain BST AVL tree
Height Between log n and n Always about log n
Search / insert / delete (worst) O(n) O(log n)
Sorted input 10, 20, 30… Becomes a straight line Rotates and stays short
Extra memory None One height per node
Extra work None Height updates + at most a few rotations
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

A node's left subtree has height 3 and its right subtree has height 1. What is its balance factor?

Question 2

You insert 30, 20, 10 into an empty AVL tree. Which case happens, and what is the new root?

Question 3

You insert 30, 10, 20 into an empty AVL tree. Which case is it?

Question 4

Does a rotation change the inorder (sorted) order of the values?

Question 5

What is the worst-case time to search an AVL tree with n nodes?

Question 6

After an INSERT, how many places may need rebalancing?

Assessment

Trees quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic B+ Trees Next topic → Heaps