PK

PKBytes

Explore tracks
Chapter 26: Self-Balancing Search Trees and B-Trees
26.01Intermediate / Advanced5 topics19 min4 interactive animations

AVL trees

AVL trees: the balance factor, the four rotation cases, rebalancing after insertion and deletion, and why the height stays logarithmic.

Learning goals

  • Compute a balance factor and recognise the four imbalance cases
  • Fix each case with one or two rotations
  • Write AVL insertion and deletion with rebalancing on the way back up
  • Derive the logarithmic height bound from the smallest AVL trees

Prerequisites

Binary search trees and ordered sets

A plain BST becomes a list when keys arrive in order. An AVL tree repairs its own shape after every update, so searches stay at O(log n) whatever the input order.

26.01.1

Balance factor

The **balance factor** of a node is the height of its left subtree minus the height of its right subtree. An **AVL tree** is a BST in which every node has a balance factor of -1, 0 or +1. The invariant is local, one number per node, and a node only needs its two children's heights to check it, so each node stores its own height.

The animation prints the factor under every node. Insert 10, 20 and 30 in that order (the first preset): after 30 arrives the root 10 has factor -2, which breaks the invariant and triggers a rotation. With a leaf at height 0 and an empty subtree at -1, the height of a node is 1 + max(child heights).

Java
1static class Node {
2    int key, height;                             // a leaf has height 0
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static int h(Node n) { return n == null ? -1 : n.height; }
7static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
8static int balance(Node n) { return h(n.left) - h(n.right); }     // allowed values: -1, 0, +1

AVL tree: insertion and deletion with rotations

Interactive · edit the input

Your input

Try
Setup

An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.

Step 1 / 34
Java
1static class Node { int key, height; Node left, right; Node(int k) { key = k; } }   // a leaf has height 0
2static int h(Node n) { return n == null ? -1 : n.height; }
3static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
4static int balance(Node n) { return h(n.left) - h(n.right); }
5static Node rotateRight(Node y) {                // the left child x becomes the subtree root
6    Node x = y.left;
7    y.left = x.right;
8    x.right = y;
9    update(y); update(x);
10    return x;
11}
12static Node rotateLeft(Node x) {
13    Node y = x.right;
14    x.right = y.left;
15    y.left = x;
16    update(x); update(y);
17    return y;
18}
19static Node rebalance(Node n) {
20    update(n);
21    int b = balance(n);
22    if (b > 1) {                                 // left-heavy
23        if (balance(n.left) < 0) n.left = rotateLeft(n.left);       // LR: first turn it into LL
24        return rotateRight(n);
25    }
26    if (b < -1) {                                // right-heavy
27        if (balance(n.right) > 0) n.right = rotateRight(n.right);   // RL: first turn it into RR
28        return rotateLeft(n);
29    }
30    return n;
31}
32static Node insert(Node n, int key) {
33    if (n == null) return new Node(key);
34    if (key < n.key) n.left = insert(n.left, key);
35    else if (key > n.key) n.right = insert(n.right, key);
36    else return n;                               // duplicates are ignored
37    return rebalance(n);                         // repair this node on the way back up
38}
39static Node delete(Node n, int key) {
40    if (n == null) return null;
41    if (key < n.key) n.left = delete(n.left, key);
42    else if (key > n.key) n.right = delete(n.right, key);
43    else {
44        if (n.left == null) return n.right;
45        if (n.right == null) return n.left;
46        Node s = n.right;
47        while (s.left != null) s = s.left;       // inorder successor
48        n.key = s.key;
49        n.right = delete(n.right, s.key);
50    }
51    return rebalance(n);
52}

Live state

0 rotations

height

-1

No condition evaluated on this step
Execution trace (dry run table)Show 34 steps
StepLineStateWhat happens
1L32height=-1An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.
2L33height=0 inserted=10Insert 10: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
3L35height=0 inserted=2020 > 10: go right.
4L33height=0 inserted=20Insert 20: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
5L22height=1 node=10 balance=-1Back at 10: heights updated, balance factor -1. Within ±1, so no rotation.
6L35height=1 inserted=3030 > 10: go right.
7L35height=1 inserted=3030 > 20: go right.
8L33height=1 inserted=30Insert 30: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
9L22height=1 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
10L26height=2 node=10 balance=-2 case=RRNode 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 has balance -1, so this is the right-right (RR) case.
11L28height=1 case=RRRotate 10 left: 20 becomes the subtree root, 10 its left child. The subtree's height is back to 1.
12L35height=1 inserted=4040 > 20: go right.
13L35height=1 inserted=4040 > 30: go right.
14L33height=1 inserted=40Insert 40: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
15L22height=1 node=30 balance=-1Back at 30: heights updated, balance factor -1. Within ±1, so no rotation.
16L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
17L35height=2 inserted=5050 > 20: go right.
18L35height=2 inserted=5050 > 30: go right.
19L35height=2 inserted=5050 > 40: go right.
20L33height=2 inserted=50Insert 50: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
21L22height=2 node=40 balance=-1Back at 40: heights updated, balance factor -1. Within ±1, so no rotation.
22L26height=2 node=30 balance=-2 case=RRNode 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance -1, so this is the right-right (RR) case.
23L28height=2 case=RRRotate 30 left: 40 becomes the subtree root, 30 its left child. The subtree's height is back to 1.
24L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
25L35height=2 inserted=2525 > 20: go right.
26L34height=2 inserted=2525 < 40: go left.
27L34height=2 inserted=2525 < 30: go left.
28L33height=2 inserted=25Insert 25: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
29L22height=2 node=30 balance=+1Back at 30: heights updated, balance factor +1. Within ±1, so no rotation.
30L22height=2 node=40 balance=+1Back at 40: heights updated, balance factor +1. Within ±1, so no rotation.
31L26height=3 node=20 balance=-2 case=RLNode 20 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance +1, so this is the right-left (RL) case.
32L27height=3 case=RLRL step 1: rotate 40 right, so 30 moves above it. Now the case is RR.
33L28height=2 case=RLRotate 20 left: 30 becomes the subtree root, 20 its left child. The subtree's height is back to 2.
34L50keys=6 height=2 minimum height=24 rotations in total. Height 2 for 6 keys; a perfectly balanced tree would have 2.
26.01.2

LL/RR/LR/RL rotations

When a node's factor reaches +2 or -2, a **rotation** restores it without breaking the BST order: it lifts one child above its parent and moves one grandchild across. Name the case after the path from the unbalanced node z toward the new weight. **LL**: left child, left-heavy: rotate z right. **RR**: mirror image: rotate z left. **LR**: z's left child is right-heavy: rotate that child left (making it LL), then rotate z right. **RL**: the mirror image.

The first four presets show one case each: inserting 10, 20, 30 is RR (one left rotation), 30, 20, 10 is LL, 30, 10, 20 is LR and 10, 30, 20 is RL; each single rotation counts 1 and each double rotation 2. After any of the four, the subtree has its old height again, which is why a single repair suffices after an insertion.

Java
1static Node rotateRight(Node y) {                // the left child x becomes the subtree root
2    Node x = y.left;
3    y.left = x.right;                            // x's right subtree switches sides
4    x.right = y;
5    update(y); update(x);                        // lower node first: its height feeds the upper one
6    return x;
7}
8static Node rotateLeft(Node x) {
9    Node y = x.right;
10    x.right = y.left;
11    y.left = x;
12    update(x); update(y);
13    return y;
14}
15static Node rebalance(Node n) {
16    update(n);
17    int b = balance(n);
18    if (b > 1) {                                 // left-heavy
19        if (balance(n.left) < 0) n.left = rotateLeft(n.left);        // LR: first turn it into LL
20        return rotateRight(n);
21    }
22    if (b < -1) {                                // right-heavy
23        if (balance(n.right) > 0) n.right = rotateRight(n.right);    // RL: first turn it into RR
24        return rotateLeft(n);
25    }
26    return n;
27}

AVL tree: insertion and deletion with rotations

Interactive · edit the input

Your input

Try
Setup

An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.

Step 1 / 34
Java
1static class Node { int key, height; Node left, right; Node(int k) { key = k; } }   // a leaf has height 0
2static int h(Node n) { return n == null ? -1 : n.height; }
3static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
4static int balance(Node n) { return h(n.left) - h(n.right); }
5static Node rotateRight(Node y) {                // the left child x becomes the subtree root
6    Node x = y.left;
7    y.left = x.right;
8    x.right = y;
9    update(y); update(x);
10    return x;
11}
12static Node rotateLeft(Node x) {
13    Node y = x.right;
14    x.right = y.left;
15    y.left = x;
16    update(x); update(y);
17    return y;
18}
19static Node rebalance(Node n) {
20    update(n);
21    int b = balance(n);
22    if (b > 1) {                                 // left-heavy
23        if (balance(n.left) < 0) n.left = rotateLeft(n.left);       // LR: first turn it into LL
24        return rotateRight(n);
25    }
26    if (b < -1) {                                // right-heavy
27        if (balance(n.right) > 0) n.right = rotateRight(n.right);   // RL: first turn it into RR
28        return rotateLeft(n);
29    }
30    return n;
31}
32static Node insert(Node n, int key) {
33    if (n == null) return new Node(key);
34    if (key < n.key) n.left = insert(n.left, key);
35    else if (key > n.key) n.right = insert(n.right, key);
36    else return n;                               // duplicates are ignored
37    return rebalance(n);                         // repair this node on the way back up
38}
39static Node delete(Node n, int key) {
40    if (n == null) return null;
41    if (key < n.key) n.left = delete(n.left, key);
42    else if (key > n.key) n.right = delete(n.right, key);
43    else {
44        if (n.left == null) return n.right;
45        if (n.right == null) return n.left;
46        Node s = n.right;
47        while (s.left != null) s = s.left;       // inorder successor
48        n.key = s.key;
49        n.right = delete(n.right, s.key);
50    }
51    return rebalance(n);
52}

Live state

0 rotations

height

-1

No condition evaluated on this step
Execution trace (dry run table)Show 34 steps
StepLineStateWhat happens
1L32height=-1An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.
2L33height=0 inserted=10Insert 10: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
3L35height=0 inserted=2020 > 10: go right.
4L33height=0 inserted=20Insert 20: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
5L22height=1 node=10 balance=-1Back at 10: heights updated, balance factor -1. Within ±1, so no rotation.
6L35height=1 inserted=3030 > 10: go right.
7L35height=1 inserted=3030 > 20: go right.
8L33height=1 inserted=30Insert 30: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
9L22height=1 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
10L26height=2 node=10 balance=-2 case=RRNode 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 has balance -1, so this is the right-right (RR) case.
11L28height=1 case=RRRotate 10 left: 20 becomes the subtree root, 10 its left child. The subtree's height is back to 1.
12L35height=1 inserted=4040 > 20: go right.
13L35height=1 inserted=4040 > 30: go right.
14L33height=1 inserted=40Insert 40: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
15L22height=1 node=30 balance=-1Back at 30: heights updated, balance factor -1. Within ±1, so no rotation.
16L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
17L35height=2 inserted=5050 > 20: go right.
18L35height=2 inserted=5050 > 30: go right.
19L35height=2 inserted=5050 > 40: go right.
20L33height=2 inserted=50Insert 50: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
21L22height=2 node=40 balance=-1Back at 40: heights updated, balance factor -1. Within ±1, so no rotation.
22L26height=2 node=30 balance=-2 case=RRNode 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance -1, so this is the right-right (RR) case.
23L28height=2 case=RRRotate 30 left: 40 becomes the subtree root, 30 its left child. The subtree's height is back to 1.
24L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
25L35height=2 inserted=2525 > 20: go right.
26L34height=2 inserted=2525 < 40: go left.
27L34height=2 inserted=2525 < 30: go left.
28L33height=2 inserted=25Insert 25: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
29L22height=2 node=30 balance=+1Back at 30: heights updated, balance factor +1. Within ±1, so no rotation.
30L22height=2 node=40 balance=+1Back at 40: heights updated, balance factor +1. Within ±1, so no rotation.
31L26height=3 node=20 balance=-2 case=RLNode 20 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance +1, so this is the right-left (RL) case.
32L27height=3 case=RLRL step 1: rotate 40 right, so 30 moves above it. Now the case is RR.
33L28height=2 case=RLRotate 20 left: 30 becomes the subtree root, 20 its left child. The subtree's height is back to 2.
34L50keys=6 height=2 minimum height=24 rotations in total. Height 2 for 6 keys; a perfectly balanced tree would have 2.
26.01.3

Insertion rebalancing

Insert as in a plain BST, then **rebalance on the way back up**: each recursive call returns the (possibly new) root of its subtree, and the parent reattaches it. The first ancestor whose factor becomes ±2 is repaired by one single or double rotation, and after that repair every ancestor above is balanced again with the same heights as before the insertion. So an insertion needs **at most one rebalancing step** (one single or one double rotation); in a test with random insertions into trees of up to 200 keys, no insertion ever needed more.

Run the “A mix of all four cases” preset (10, 20, 30, 40, 50, 25): the tree ends at height 2 for 6 keys after 4 rotations. The sorted-input preset (10 to 70) ends as a perfect tree of height 2 with 4 rotations, while a plain BST would be a chain of height 6.

Java
1static Node insert(Node n, int key) {
2    if (n == null) return new Node(key);
3    if (key < n.key) n.left = insert(n.left, key);
4    else if (key > n.key) n.right = insert(n.right, key);
5    else return n;                               // duplicates are ignored
6    return rebalance(n);                         // repair this node on the way back up
7}

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(log n) recursion

AVL tree: insertion and deletion with rotations

Interactive · edit the input

Your input

Try
Setup

An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.

Step 1 / 34
Java
1static class Node { int key, height; Node left, right; Node(int k) { key = k; } }   // a leaf has height 0
2static int h(Node n) { return n == null ? -1 : n.height; }
3static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
4static int balance(Node n) { return h(n.left) - h(n.right); }
5static Node rotateRight(Node y) {                // the left child x becomes the subtree root
6    Node x = y.left;
7    y.left = x.right;
8    x.right = y;
9    update(y); update(x);
10    return x;
11}
12static Node rotateLeft(Node x) {
13    Node y = x.right;
14    x.right = y.left;
15    y.left = x;
16    update(x); update(y);
17    return y;
18}
19static Node rebalance(Node n) {
20    update(n);
21    int b = balance(n);
22    if (b > 1) {                                 // left-heavy
23        if (balance(n.left) < 0) n.left = rotateLeft(n.left);       // LR: first turn it into LL
24        return rotateRight(n);
25    }
26    if (b < -1) {                                // right-heavy
27        if (balance(n.right) > 0) n.right = rotateRight(n.right);   // RL: first turn it into RR
28        return rotateLeft(n);
29    }
30    return n;
31}
32static Node insert(Node n, int key) {
33    if (n == null) return new Node(key);
34    if (key < n.key) n.left = insert(n.left, key);
35    else if (key > n.key) n.right = insert(n.right, key);
36    else return n;                               // duplicates are ignored
37    return rebalance(n);                         // repair this node on the way back up
38}
39static Node delete(Node n, int key) {
40    if (n == null) return null;
41    if (key < n.key) n.left = delete(n.left, key);
42    else if (key > n.key) n.right = delete(n.right, key);
43    else {
44        if (n.left == null) return n.right;
45        if (n.right == null) return n.left;
46        Node s = n.right;
47        while (s.left != null) s = s.left;       // inorder successor
48        n.key = s.key;
49        n.right = delete(n.right, s.key);
50    }
51    return rebalance(n);
52}

Live state

0 rotations

height

-1

No condition evaluated on this step
Execution trace (dry run table)Show 34 steps
StepLineStateWhat happens
1L32height=-1An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.
2L33height=0 inserted=10Insert 10: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
3L35height=0 inserted=2020 > 10: go right.
4L33height=0 inserted=20Insert 20: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
5L22height=1 node=10 balance=-1Back at 10: heights updated, balance factor -1. Within ±1, so no rotation.
6L35height=1 inserted=3030 > 10: go right.
7L35height=1 inserted=3030 > 20: go right.
8L33height=1 inserted=30Insert 30: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
9L22height=1 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
10L26height=2 node=10 balance=-2 case=RRNode 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 has balance -1, so this is the right-right (RR) case.
11L28height=1 case=RRRotate 10 left: 20 becomes the subtree root, 10 its left child. The subtree's height is back to 1.
12L35height=1 inserted=4040 > 20: go right.
13L35height=1 inserted=4040 > 30: go right.
14L33height=1 inserted=40Insert 40: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
15L22height=1 node=30 balance=-1Back at 30: heights updated, balance factor -1. Within ±1, so no rotation.
16L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
17L35height=2 inserted=5050 > 20: go right.
18L35height=2 inserted=5050 > 30: go right.
19L35height=2 inserted=5050 > 40: go right.
20L33height=2 inserted=50Insert 50: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
21L22height=2 node=40 balance=-1Back at 40: heights updated, balance factor -1. Within ±1, so no rotation.
22L26height=2 node=30 balance=-2 case=RRNode 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance -1, so this is the right-right (RR) case.
23L28height=2 case=RRRotate 30 left: 40 becomes the subtree root, 30 its left child. The subtree's height is back to 1.
24L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
25L35height=2 inserted=2525 > 20: go right.
26L34height=2 inserted=2525 < 40: go left.
27L34height=2 inserted=2525 < 30: go left.
28L33height=2 inserted=25Insert 25: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
29L22height=2 node=30 balance=+1Back at 30: heights updated, balance factor +1. Within ±1, so no rotation.
30L22height=2 node=40 balance=+1Back at 40: heights updated, balance factor +1. Within ±1, so no rotation.
31L26height=3 node=20 balance=-2 case=RLNode 20 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance +1, so this is the right-left (RL) case.
32L27height=3 case=RLRL step 1: rotate 40 right, so 30 moves above it. Now the case is RR.
33L28height=2 case=RLRotate 20 left: 30 becomes the subtree root, 20 its left child. The subtree's height is back to 2.
34L50keys=6 height=2 minimum height=24 rotations in total. Height 2 for 6 keys; a perfectly balanced tree would have 2.
26.01.4

Deletion rebalancing

Deletion is the same BST deletion (leaf, one child, or the successor trick) followed by the same rebalance on every ancestor. Unlike insertion, a rotation may **not** restore the subtree's old height, so the repair can cascade upward: more than one ancestor may need rotating. A deletion costs O(log n) because there is at most one rebalancing step per level. In a random test with trees of up to 200 keys, a single deletion needed as many as 4 rebalancing steps.

One more difference: after deleting, the heavy child may have a balance factor of 0, which does not happen after an insertion. In that case a single rotation is correct (the code treats it as LL or RR), so the double-rotation test checks for a strictly opposite sign. The “Delete causes a rotation” preset builds 20, 10, 30, 5 and deletes 30: the root 20 becomes left-heavy by 2 and one right rotation repairs it.

Java
1static Node delete(Node n, int key) {
2    if (n == null) return null;
3    if (key < n.key) n.left = delete(n.left, key);
4    else if (key > n.key) n.right = delete(n.right, key);
5    else {
6        if (n.left == null) return n.right;
7        if (n.right == null) return n.left;
8        Node s = n.right;
9        while (s.left != null) s = s.left;       // inorder successor
10        n.key = s.key;
11        n.right = delete(n.right, s.key);
12    }
13    return rebalance(n);                         // every ancestor is checked, not just the first
14}

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(log n) recursion

AVL tree: insertion and deletion with rotations

Interactive · edit the input

Your input

Try
Setup

An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.

Step 1 / 34
Java
1static class Node { int key, height; Node left, right; Node(int k) { key = k; } }   // a leaf has height 0
2static int h(Node n) { return n == null ? -1 : n.height; }
3static void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
4static int balance(Node n) { return h(n.left) - h(n.right); }
5static Node rotateRight(Node y) {                // the left child x becomes the subtree root
6    Node x = y.left;
7    y.left = x.right;
8    x.right = y;
9    update(y); update(x);
10    return x;
11}
12static Node rotateLeft(Node x) {
13    Node y = x.right;
14    x.right = y.left;
15    y.left = x;
16    update(x); update(y);
17    return y;
18}
19static Node rebalance(Node n) {
20    update(n);
21    int b = balance(n);
22    if (b > 1) {                                 // left-heavy
23        if (balance(n.left) < 0) n.left = rotateLeft(n.left);       // LR: first turn it into LL
24        return rotateRight(n);
25    }
26    if (b < -1) {                                // right-heavy
27        if (balance(n.right) > 0) n.right = rotateRight(n.right);   // RL: first turn it into RR
28        return rotateLeft(n);
29    }
30    return n;
31}
32static Node insert(Node n, int key) {
33    if (n == null) return new Node(key);
34    if (key < n.key) n.left = insert(n.left, key);
35    else if (key > n.key) n.right = insert(n.right, key);
36    else return n;                               // duplicates are ignored
37    return rebalance(n);                         // repair this node on the way back up
38}
39static Node delete(Node n, int key) {
40    if (n == null) return null;
41    if (key < n.key) n.left = delete(n.left, key);
42    else if (key > n.key) n.right = delete(n.right, key);
43    else {
44        if (n.left == null) return n.right;
45        if (n.right == null) return n.left;
46        Node s = n.right;
47        while (s.left != null) s = s.left;       // inorder successor
48        n.key = s.key;
49        n.right = delete(n.right, s.key);
50    }
51    return rebalance(n);
52}

Live state

0 rotations

height

-1

No condition evaluated on this step
Execution trace (dry run table)Show 34 steps
StepLineStateWhat happens
1L32height=-1An AVL tree keeps every node's balance factor (left height minus right height) within -1..+1 by rotating when an insertion or deletion breaks it. The factor is shown under each node.
2L33height=0 inserted=10Insert 10: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
3L35height=0 inserted=2020 > 10: go right.
4L33height=0 inserted=20Insert 20: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
5L22height=1 node=10 balance=-1Back at 10: heights updated, balance factor -1. Within ±1, so no rotation.
6L35height=1 inserted=3030 > 10: go right.
7L35height=1 inserted=3030 > 20: go right.
8L33height=1 inserted=30Insert 30: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
9L22height=1 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
10L26height=2 node=10 balance=-2 case=RRNode 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 has balance -1, so this is the right-right (RR) case.
11L28height=1 case=RRRotate 10 left: 20 becomes the subtree root, 10 its left child. The subtree's height is back to 1.
12L35height=1 inserted=4040 > 20: go right.
13L35height=1 inserted=4040 > 30: go right.
14L33height=1 inserted=40Insert 40: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
15L22height=1 node=30 balance=-1Back at 30: heights updated, balance factor -1. Within ±1, so no rotation.
16L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
17L35height=2 inserted=5050 > 20: go right.
18L35height=2 inserted=5050 > 30: go right.
19L35height=2 inserted=5050 > 40: go right.
20L33height=2 inserted=50Insert 50: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
21L22height=2 node=40 balance=-1Back at 40: heights updated, balance factor -1. Within ±1, so no rotation.
22L26height=2 node=30 balance=-2 case=RRNode 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance -1, so this is the right-right (RR) case.
23L28height=2 case=RRRotate 30 left: 40 becomes the subtree root, 30 its left child. The subtree's height is back to 1.
24L22height=2 node=20 balance=-1Back at 20: heights updated, balance factor -1. Within ±1, so no rotation.
25L35height=2 inserted=2525 > 20: go right.
26L34height=2 inserted=2525 < 40: go left.
27L34height=2 inserted=2525 < 30: go left.
28L33height=2 inserted=25Insert 25: an empty spot, so it becomes a new leaf (balance factor 0). Now walk back up and repair.
29L22height=2 node=30 balance=+1Back at 30: heights updated, balance factor +1. Within ±1, so no rotation.
30L22height=2 node=40 balance=+1Back at 40: heights updated, balance factor +1. Within ±1, so no rotation.
31L26height=3 node=20 balance=-2 case=RLNode 20 has balance factor -2: its right subtree is 2 taller. Its right child 40 has balance +1, so this is the right-left (RL) case.
32L27height=3 case=RLRL step 1: rotate 40 right, so 30 moves above it. Now the case is RR.
33L28height=2 case=RLRotate 20 left: 30 becomes the subtree root, 20 its left child. The subtree's height is back to 2.
34L50keys=6 height=2 minimum height=24 rotations in total. Height 2 for 6 keys; a perfectly balanced tree would have 2.
26.01.5

Height bound

Why is an AVL tree's height logarithmic? Ask for the **fewest nodes** N(h) in an AVL tree of height h. The sparsest such tree has a root, one subtree of height h - 1 (as sparse as possible) and the other of height h - 2, the smallest allowed: N(h) = N(h - 1) + N(h - 2) + 1, with N(0) = 1 and N(1) = 2. These are the **Fibonacci trees**, and N(h) grows exponentially, about 1.618^h.

The first values are 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232 for heights 0 to 10. Inverting the relation gives h < 1.4405 · log2(n + 2) - 1.328, so an AVL tree is never more than about 44% taller than a perfectly balanced tree, and searches take at most that many comparisons.

Height h012345678910
Fewest nodes N(h)12471220335488143232
Java
1static long minNodes(int height) {               // fewest nodes in an AVL tree of this height
2    long prev = 1, cur = 2;                      // N(0), N(1)
3    if (height == 0) return 1;
4    for (int i = 2; i <= height; i++) { long next = cur + prev + 1; prev = cur; cur = next; }
5    return cur;
6}

Practice ladder

Now try it yourself

Easy

  • Balanced Binary Tree
  • Convert Sorted Array to Binary Search Tree

Medium

  • Balance a Binary Search Tree
  • Count Complete Tree Nodes

Advanced

  • Count of Smaller Numbers After Self (AVL)
  • Implement an AVL tree with order statistics

Key takeaways

  • An AVL tree keeps every balance factor (left height minus right height) in -1, 0, +1.
  • LL and RR need one rotation; LR and RL need two, the first turning the case into LL or RR.
  • Insertion needs at most one rebalancing step; deletion may repair several ancestors.
  • The smallest AVL trees are Fibonacci trees, so the height is below 1.44 log2(n + 2).