AVL tree visualizer
An AVL tree is a binary search tree that rebalances itself: no node's two subtrees may differ in height by more than one. Insert and delete keys below and watch the balance factors and rotations step by step. Further down: the four rotation cases, worked examples, the height bound, and AVL versus red-black trees.
involved in this step out of balance (|balance factor| = 2) balance factor = height(left) − height(right)
- Every balance factor in −1..+1
- yes
- Keys in order
- yes
- Height
- 3
- AVL bound for 7 keys
- 4.24
- Perfectly balanced would be
- 3
How to use the simulator
Type a key and press Insert or Delete. The number beside each node is its balance factor, the height of its left subtree minus the height of its right. The panel lists every step: where the key went, each node whose height changed on the way back up, and any rotation. Step back and forth through them to see the tree mid-repair; a node that is out of balance is drawn in red.
- Press Insert 1 to 10 in order. Without balancing this would be a chain of ten; the AVL tree stays 4 levels tall, using 6 rotations along the way.
- On the starting tree, insert 10 and then 5: the second insertion unbalances 20, and a single right rotation fixes it.
- Insert 65 and then 63: a right-left case at 60, fixed with two rotations.
- Delete keys from one side until the root tilts, and watch deletion rebalance higher up.
The code was checked by 80,000 random insertions and deletions against a sorted set: after each one every balance factor was between −1 and +1, every stored height was right, and the keys were in order.
What is an AVL tree?
An AVL tree is a binary search tree with one extra rule: for every node, the heights of its left and right subtrees differ by at most one. A binary search tree keeps smaller keys on the left and larger on the right, so a lookup takes as many steps as the tree is tall; without a balancing rule, keys inserted in sorted order produce a tree that is just a chain. The AVL rule keeps the height logarithmic, so search, insertion and deletion take O(log n) time even in the worst case.
The name comes from its inventors, Georgy Adelson-Velsky and Evgenii Landis, who described it in 1962 in "An algorithm for the organization of information". It was the first self-balancing binary search tree.
Balance factor
Each node keeps its height (the number of nodes on the longest path down to a leaf), or just its balance factor. The balance factor is
balance factor = height(left subtree) − height(right subtree)
and in an AVL tree it is −1, 0 or +1 at every node. Some books define it the other way round, right minus left; only the signs change. An insertion or deletion changes heights only along the path between the changed position and the root, so only those nodes need checking. The first node found with a balance factor of +2 or −2 is fixed with a rotation.
AVL tree rotations: the four cases
A rotation rearranges three nodes and their subtrees without changing the key order. Which rotation is needed depends on where the extra height is: in the unbalanced node's left or right child, and in that child's left or right subtree. The four smallest examples, built by the simulator:
The single cases (left-left, right-right) need one rotation at the unbalanced node. The double cases (left-right, right-left) first rotate the child to turn the problem into a single case, then rotate the node itself. In every case, the middle key of the three ends up on top.
AVL tree insertion
- Insert the key as a new leaf, as in a plain binary search tree.
- Walk back up towards the root, updating each node's height.
- At the first node whose balance factor becomes +2 or −2, apply the matching rotation.
After that one rotation, single or double, the subtree has the same height it had before the insertion, so nothing above it changes. An insertion therefore needs at most one rotation case, and the walk back up can stop early once a node's height does not change.
AVL tree insertion example
Inserting 10, 20, 30, 40, 50, 25 into an empty AVL tree, as the simulator does it:
| Insert | What happens |
|---|---|
| 10 | 10 becomes the root. |
| 20 | Search for 20: 10. Insert it as a leaf under 10. Back up at 10: height now 2, balance factor -1. Still within ±1. |
| 30 | Search for 30: 10 → 20. Insert it as a leaf under 20. Back up at 20: height now 2, balance factor -1. Still within ±1. 10 has balance factor -2: its right subtree is 2 taller. Its right child 20 leans right too (right-right case), so one left rotation at 10 fixes it. Rotate left at 10: 20 moves up. |
| 40 | Search for 40: 20 → 30. Insert it as a leaf under 30. Back up at 30: height now 2, balance factor -1. Still within ±1. Back up at 20: height now 3, balance factor -1. Still within ±1. |
| 50 | Search for 50: 20 → 30 → 40. Insert it as a leaf under 40. Back up at 40: height now 2, balance factor -1. Still within ±1. 30 has balance factor -2: its right subtree is 2 taller. Its right child 40 leans right too (right-right case), so one left rotation at 30 fixes it. Rotate left at 30: 40 moves up. |
| 25 | Search for 25: 20 → 40 → 30. Insert it as a leaf under 30. Back up at 30: height now 2, balance factor +1. Still within ±1. Back up at 40: height now 3, balance factor +1. Still within ±1. 20 has balance factor -2, but its right child 40 leans left (right-left case): first rotate right at 40, then left at 20. Rotate right at 40: 30 moves up, and the problem becomes right-right. Rotate left at 20: 30 moves up and becomes the root of this subtree. |
The final tree, with balance factors:
AVL tree deletion
Delete the key as in a binary search tree: remove a leaf directly, replace a node that has one child with that child, and for a node with two children copy in its in-order successor (the smallest key in its right subtree) and delete the successor from below. Then walk back up to the root, updating heights and rotating wherever a balance factor reaches ±2.
The rotation cases are the same four, chosen by the balance factor of the taller child; when that child is exactly balanced (factor 0), the single rotation is used. The important difference from insertion is that a rotation after a deletion can leave the subtree one level shorter than before, so the parent may become unbalanced in turn. Deletion can therefore need a rotation at every level, O(log n) in the worst case, where insertion needs at most one.
How tall can an AVL tree get?
The least balanced AVL tree of height h has a root whose subtrees are the least balanced trees of heights h − 1 and h − 2. So the minimum number of nodes is N(h) = N(h − 1) + N(h − 2) + 1, which grows like the Fibonacci numbers: 1, 2, 4, 7, 12, 20, 33, 54, 88, 143 for heights 1 to 10. Turning that around gives the height bound: an AVL tree with n nodes has height below 1.4405 log₂(n + 2) − 0.3277, at most about 44% taller than a perfectly balanced tree.
In practice AVL trees are much closer to perfect. Inserting 1 to 15 in order, which turns a plain binary search tree into a chain of 15, gives an AVL tree of height 4, a perfect binary tree, after 11 rotations:
Time complexity
| Operation | Time | Rotations |
|---|---|---|
| Search | O(log n) | None |
| Insert | O(log n) | At most one single or double rotation |
| Delete | O(log n) | Up to one per level, O(log n) |
| Minimum, maximum, successor | O(log n) | None |
Space is O(n). Each node stores its height or balance factor in addition to its key and two child pointers; a balance factor needs only two bits.
AVL tree vs red-black tree
| Aspect | AVL tree | Red-black tree |
|---|---|---|
| Balance rule | Subtree heights differ by at most 1 | Colour rules; longest path at most twice the shortest |
| Maximum height | About 1.44 log₂ n | 2 log₂(n + 1) |
| Lookups | Slightly faster | Slightly slower |
| Rotations per insert | At most 2 | At most 2 |
| Rotations per delete | O(log n) | At most 3 |
| Where you meet it | Textbooks and read-heavy indexes | std::map, Java TreeMap, the Linux kernel |
Ben Pfaff's 2004 study of binary search trees in real system software found that the best choice depends on the input: red-black trees did best when keys arrived mostly in random order, AVL trees when keys often arrived in sorted order and were later looked up at random, and splay trees when later accesses were sequential or clustered. See the red-black tree visualizer for the other side.
AVL trees in exams and interviews
Exam questions usually ask you to insert a sequence of keys and draw the tree after each rotation, so practise naming the case from the shape: find the lowest unbalanced node, then look one and two steps down towards the newly inserted key. "Left then right" is the left-right case. Coding interviews rarely ask for a full AVL implementation, but often ask related questions: checking whether a binary tree is height-balanced (LeetCode 110), building a balanced tree from a sorted array (108), or rebalancing an existing binary search tree (1382).
AVL tree questions and answers
What is an AVL tree?
An AVL tree is a self-balancing binary search tree in which the heights of the two subtrees of every node differ by at most one. After each insertion or deletion, the tree checks the nodes on the path back to the root and restores the rule with rotations. It was the first self-balancing binary search tree, described by Georgy Adelson-Velsky and Evgenii Landis in 1962.
What is the balance factor in an AVL tree?
The balance factor of a node is the height of its left subtree minus the height of its right subtree. In an AVL tree it must be −1, 0 or +1 for every node. A value of +2 or −2 after an update means the node is unbalanced and needs a rotation.
What are the four rotation cases in an AVL tree?
Left-left: the left child’s left subtree is too tall; fix with one right rotation. Right-right: the mirror image; one left rotation. Left-right: the left child’s right subtree is too tall; rotate left at the child, then right at the node. Right-left: the mirror image; rotate right at the child, then left at the node.
What is the time complexity of an AVL tree?
Search, insertion and deletion all take O(log n) time in the worst case, because the height of an AVL tree with n nodes is at most about 1.44 log2(n + 2). An insertion needs at most one single or double rotation; a deletion may need a rotation at each level, O(log n) in total.
What is the difference between AVL and red-black trees?
AVL trees balance more strictly, so they are shallower and lookups touch fewer nodes; red-black trees allow paths up to twice as long but rebalance with fewer rotations, especially on deletion. Read-heavy workloads lean towards AVL trees; most standard libraries use red-black trees for general-purpose ordered maps.
What is the maximum height of an AVL tree?
An AVL tree of height h has at least N(h) = N(h − 1) + N(h − 2) + 1 nodes, a Fibonacci-like sequence, so its height is less than about 1.4405 log2(n + 2) − 0.3277 for n nodes. A perfectly balanced tree has height about log2 n, so an AVL tree is at most 44% taller.
How do you delete a node from an AVL tree?
Delete as in a binary search tree: remove a leaf, replace a node with one child by that child, or replace a node with two children by its in-order successor. Then walk back up to the root, updating heights and rotating at every node whose balance factor has become +2 or −2. Unlike insertion, deletion can need rotations at several levels.
Is AVL tree balancing worth it?
When keys can arrive in sorted or nearly sorted order, yes: an unbalanced binary search tree degrades to a linked list with O(n) operations, while an AVL tree stays at O(log n). For random insertion orders a plain binary search tree is balanced on average, but nothing guarantees it.
Further reading
- Ben Pfaff, 2004Performance Analysis of BSTs in System SoftwareAVL, red-black and splay trees measured on real workloads.
- Sedgewick and WayneAlgorithms, 4th edition: Balanced Search TreesBalanced trees from 2-3 trees to red-black BSTs.
- SemicolonyRed-black tree visualizerThe other common self-balancing binary search tree.