AVL tree
hardOne number per node - the balance factor - decides everything. Feed it sorted keys and watch it rotate after almost every insert, keeping the height under 1.44 log n forever.
O(log n)Average O(log n)Worst O(log n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How avl tree works
An AVL tree is a BST that refuses to lean. Every node stores its height, and its balance factor - height(node.left) minus height(node.right) - must stay in {-1, 0, +1}. Insert works exactly like a plain BST insert, but the recursion then walks back up refreshing heights, and the first node whose factor hits +2 or -2 gets repaired on the spot.
The repair is a rotation: local pointer surgery that lifts the taller side one level while preserving the in-order sequence, which is why it cannot break the BST property. Four named cases collapse into two mirror pairs. Left-Left and Right-Right take a single rotation. Left-Right and Right-Left are the inside-heavy shapes - a single rotation only mirrors the problem, so the child is rotated first to straighten the path.
The reward is a hard ceiling: height never exceeds 1.44 log n, so search, insert, and delete are O(log n) in the worst case, not just on average. Feed it the sorted keys that flatten a plain BST and it simply rotates after almost every insert, staying flat forever. Red-black trees loosen the balance to cut rotations, which is why standard libraries usually pick them instead.
Step by step
- Start empty. Insert 10, then 20 - it lands right of 10. Balance factors read 0 and -1, all within range.
- Insert 30: it attaches right of 20, and 10's balance factor drops to -2. The invariant is broken at 10.
- 30 went right of 10's right child - Right-Right. One left rotation about 10: 20 becomes the root, 10 and 30 its children.
- Insert 5 as 10's left child. The root's balance factor moves to +1 - legal, so nothing rotates.
- Insert 3: node 10 hits +2, and 3 sits left of 10's left child 5 - Left-Left. Rotate right about 10.
- 5 now heads that subtree with 3 and 10 as children. Five keys, height 3 - the minimum possible - despite two forced repairs.
Complexity
| Best case time | O(log n) |
|---|---|
| Average time | O(log n) |
| Worst case time | O(log n) |
| Space | O(n) |
Balance factors are held in {−1, 0, +1}, which bounds the height.
Reference implementation
Python
def height(n): return n.height if n else 0
def balance(n): return height(n.left) - height(n.right) if n else 0
def rotate_right(y):
x, t2 = y.left, y.left.right
x.right, y.left = y, t2 # rotate
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x # x is the new subtree root
def rotate_left(x):
y, t2 = x.right, x.right.left
y.left, x.right = x, t2
x.height = 1 + max(height(x.left), height(x.right))
y.height = 1 + max(height(y.left), height(y.right))
return y
def insert(node, k):
if node is None:
return Node(k)
if k < node.key: node.left = insert(node.left, k)
elif k > node.key: node.right = insert(node.right, k)
else: return node
node.height = 1 + max(height(node.left), height(node.right))
b = balance(node)
if b > 1 and k < node.left.key: return rotate_right(node) # LL
if b < -1 and k > node.right.key: return rotate_left(node) # RR
if b > 1: # LR
node.left = rotate_left(node.left)
return rotate_right(node)
if b < -1: # RL
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeJavaScript
const h = (n) => (n ? n.height : 0);
const bal = (n) => (n ? h(n.left) - h(n.right) : 0);
function rotateRight(y) {
const x = y.left;
y.left = x.right;
x.right = y;
y.height = 1 + Math.max(h(y.left), h(y.right));
x.height = 1 + Math.max(h(x.left), h(x.right));
return x;
}
function rotateLeft(x) {
const y = x.right;
x.right = y.left;
y.left = x;
x.height = 1 + Math.max(h(x.left), h(x.right));
y.height = 1 + Math.max(h(y.left), h(y.right));
return y;
}Worth noticing
One number per node decides everything
The balance factor is height(left) − height(right). AVL's whole contract is keeping it in {−1, 0, +1} at every node. The moment an insert pushes it to ±2, a rotation puts it back.
Four cases, but really only two
Left-Left and Right-Right are mirror images fixed by one rotation. Left-Right and Right-Left are the awkward ones - a single rotation just moves the problem, so you first rotate the child to turn it into an LL or RR, then fix that.
Rotation preserves in-order order
A rotation reshapes the tree without changing the sorted sequence its in-order walk produces. That is precisely why it is safe: the BST property is an in-order property.
Height stays under 1.44·log₂n
Guaranteed O(log n) for search, insert and delete - no degenerate case, ever. The price is the height bookkeeping and up to O(log n) rotations per delete, which is why red-black trees (looser balance, fewer rotations) are more common in standard libraries.
Common pitfalls
- Refreshing heights in the wrong order after a rotation. The demoted node is now a child, so its height must be recomputed before the promoted node's - reversed, both are stale.
- Forgetting that a rotation returns a new subtree root. The parent must be relinked to it, as in node.left = rotateLeft(node.left) - otherwise the rotated nodes leak out of the tree.
- Fixing Left-Right with a single right rotation. That just mirrors the imbalance into Right-Left; the left child must first be rotated left, then the node rotated right.
- Choosing the case by comparing the inserted key works during insert, but delete-time rebalancing has no inserted key - there you must read the child's balance factor instead.
- Recomputing heights recursively on demand. That makes every insert O(n); the design depends on each node caching its own height and updating it in O(1).
Where it is used
- Ordered maps where lookups dominate writes - AVL's stricter balance keeps searches slightly shorter than a red-black tree's.
- In-memory indexes that need hard worst-case bounds rather than average-case comfort.
- The canonical whiteboard exercise for rotations - the same mechanics reappear in red-black trees, treaps, and B-trees.
- Any workload that might see sorted or adversarial insertion order, where a plain BST would quietly degrade to O(n).
Frequently asked questions
What is the time complexity of an AVL tree?
Search, insert, and delete are all O(log n) - best, average, and worst case - with O(n) space. Holding every balance factor in {-1, 0, +1} bounds the height at 1.44 log n, so no operation can ever see the O(n) degenerate path a plain BST allows.
What is the difference between an AVL tree and a red-black tree?
Both are self-balancing BSTs with O(log n) operations. AVL balances more strictly, so it sits flatter and searches slightly faster, but pays with more rotations - up to O(log n) of them per delete. Red-black tolerates roughly twice the height, rotates less, and is what std::map and TreeMap actually ship.
When does an AVL insert need two rotations?
In the zig-zag cases. Left-Right means the new key went right of the left child; a single right rotation would just mirror the imbalance to the other side. So the child is rotated left first, turning the shape into Left-Left, and one right rotation about the node finishes. Right-Left is the mirror image.
What is a balance factor in an AVL tree?
height(node.left) minus height(node.right), stored per node and refreshed on the way back up after every insert. Values -1, 0, and +1 are legal; +2 or -2 means one side is two levels deeper and triggers a rotation. Where the new key went decides which of the four cases applies.