AVL Tree, step by step.

// how avl trees work

How an AVL tree works

What is an AVL tree?

An AVL tree is a binary search tree that repairs its own shape: at every node, the left and right subtrees may differ in height by one level at most. When an insertion or deletion breaks this, rotations restore it and keep the keys in order. AVL stands for its inventors, Adelson-Velsky and Landis, who described it in 1962.

AVL tree height and balance factor

The height of a node counts the edges on the longest path down to a leaf. Here a leaf has height 0 and an empty subtree −1. The balance factor is height(left) − height(right), so positive means left-heavy. Sources that count a leaf as 1 get the same factors; sources that subtract the other way flip every sign. A node is balanced at −1, 0 or +1 and unbalanced at +2 or −2.

In the figure below, node 30 has only a left child, the leaf 20: 0 − (−1) = +1, balanced. Node 50 has 30 on its left and nothing on its right: 1 − (−1) = +2, unbalanced.

AVL tree insertion: finding the unbalanced node

The new key goes down as in a plain binary search tree and becomes a leaf; a key already in the tree is refused. The path is then walked back up, updating heights and balance factors. The first node found at +2 or −2 is the unbalanced node.

Which AVL rotation: the LL, RR, LR and RL cases

The four imbalances, often called cases, are named by the first two steps from the unbalanced node towards the new key.

Imbalance	New key in	Unbalanced node	Child on the tall side	Fix
LL	left child's left subtree	+2	+1	single right rotation
RR	right child's right subtree	−2	−1	single left rotation
LR	left child's right subtree	+2	−1	left-right rotation
RL	right child's left subtree	−2	+1	right-left rotation

A rotation is named after the direction in which the node it rotates moves down. Many sources name the fix after the case instead: an “LL rotation” is a single right rotation, an “RR rotation” a single left one.

AVL single right rotation (LL case)

The unbalanced node moves down to the right, and its left child takes its place. Here, 10 is inserted as the left child of 15. Node 17 reaches +2, with 15 at +1. A right rotation on 17 lifts 15 under 8, with 10 and 17 as its children. Step through it below.

Single Right Rotation: Insert node 10

All steps as text

1. The highlighted node shows where the new key will go. Step forward to insert it.
2. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.
3. The node with key 17 is unbalanced. To restore balance, a single right rotation is required.
4. An arrow is now displayed above the node around which the rotation will occur.
5. The node with key 17 is rotated downwards and to the right.
6. Update the tree structure: set the node with key 15 as the right child of the node with key 8.
7. Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.

AVL single left rotation (RR case)

The mirror image: the unbalanced node moves down to the left, and its right child takes its place. Here, 80 is inserted as the right child of 79. Node 66 reaches −2, with 79 at −1. A left rotation on 66 lifts 79 under 57, with 66 and 80 as its children. Step through it below.

Single Left Rotation: Insert node 80

All steps as text

1. The highlighted node shows where the new key will go. Step forward to insert it.
2. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.
3. The node with key 66 is unbalanced. To restore balance, a single left rotation is required.
4. An arrow is now displayed above the node around which the rotation will occur.
5. The node with key 66 is rotated downwards and to the left.
6. Update the tree structure: set the node with key 79 as the right child of the node with key 57.
7. Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.

AVL left-right rotation (LR case): a double rotation

When the path to the new key bends, one rotation at the unbalanced node would only bend it the other way. A double rotation is needed: a left rotation on the left child straightens the path, then a right rotation on the unbalanced node lifts the grandchild to the top.

Here, 6 is inserted as the right child of 5, so the new key is itself the grandchild. Node 7 reaches +2, with its left child 5 at −1. A left rotation on 5 lifts 6; a right rotation on 7 leaves 6 under 44, with 5 and 7 as its children. Step through it below.

Left-Right Rotation: Insert node 6

All steps as text

1. The highlighted node shows where the new key will go. Step forward to insert it.
2. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.
3. The node with key 7 is unbalanced. To restore balance, a left-right rotation is required.
4. An arrow is now displayed above the node around which the rotation will occur.
5. The node with key 5 is rotated downwards and to the left.
6. Update the tree structure: set the node with key 6 as the left child of the node with key 7.
7. An arrow is now displayed above the node around which the rotation will occur.
8. The node with key 7 is rotated downwards and to the right.
9. Update the tree structure: set the node with key 6 as the left child of the node with key 44.
10. Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.

AVL right-left rotation (RL case): a double rotation

The mirror case: a right rotation on the right child, then a left rotation on the unbalanced node. Here, 22 is inserted as the left child of 36. Node 19 reaches −2, with its right child 36 at +1. A right rotation on 36 lifts 22; a left rotation on 19 leaves 22 under 50, with 19 and 36 as its children. Step through it below.

Right-Left Rotation: Insert node 22

All steps as text

1. The highlighted node shows where the new key will go. Step forward to insert it.
2. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.
3. The node with key 19 is unbalanced. To restore balance, a right-left rotation is required.
4. An arrow is now displayed above the node around which the rotation will occur.
5. The node with key 36 is rotated downwards and to the right.
6. Update the tree structure: set the node with key 22 as the right child of the node with key 19.
7. An arrow is now displayed above the node around which the rotation will occur.
8. The node with key 19 is rotated downwards and to the left.
9. Update the tree structure: set the node with key 22 as the left child of the node with key 50.
10. Observe the tree's balance, indicated by the balance factors on each node. The tree is balanced.

How an AVL rotation works: re-parenting the middle subtree

In the general right rotation below, A and B are the left child's subtrees, and C is the unbalanced node's right subtree.

A and C keep their parents. B moves, with its shape unchanged, from the child that went up to the node that went down: this is re-parenting. The in-order sequence stays the same, and only a fixed number of links change, so a rotation takes O(1) time. When the new key lies below the grandchild in a double rotation, it moves in this way with one of the grandchild's subtrees. In the four examples above, the moving subtree is empty.

Why one rotation is enough after an AVL insertion

After the rotation, the repaired subtree is exactly as tall as before the insertion, so every ancestor keeps its old height and balance factor and one single or double rotation is enough. In the single right rotation example, the subtree in 17's place has height 1 both before and after.

AVL tree deletion

Deletion starts as in a binary search tree. A leaf is removed; a node with one child is replaced by it. A node with two children takes the key of its in-order successor, the smallest key in its right subtree, which is then removed. Every ancestor up to the root is then checked. A rotation can leave a subtree one level shorter, so rotations may follow at several levels. A child on the tall side with balance factor 0 occurs only after a deletion and gets a single rotation.

AVL tree time complexity and height

Each operation follows one root-to-leaf path, with constant work per level, rotations included. The fewest nodes in an AVL tree of height h follow N(h) = N(h − 1) + N(h − 2) + 1, with N(0) = 1 and N(1) = 2. This Fibonacci-like growth keeps the height below about 1.44 log₂ n, so search, insertion and deletion are O(log n) in the worst case, not only on average.

Measure	Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Rotation	O(1)
Height	O(log n)
Space	O(n)

AVL tree vs binary search tree

Inserted in ascending order, the keys 10, 20, 30, 40, 50, 60 and 70 turn a plain binary search tree into a chain seven levels tall, with O(n) search. The AVL tree of the same keys has three levels, 40 above 20 and 60. Its first rotation comes when 30 pushes 10 to −2.

AVL tree vs red-black tree

An AVL tree is balanced more strictly: its height stays below about 1.44 log₂ n, against about 2 log₂ n for a red-black tree, so lookups are shorter. Both need at most one single or double rotation per insertion. On deletion, an AVL tree may rotate at several levels, a red-black tree at most three times. C++ std::map and Java's TreeMap are usually red-black trees, and databases use B-trees.