AVL tree
An AVL tree is a binary search tree that refuses to get lopsided. After each insert, every node on the way back up compares the heights of its two sides. If they differ by two, a rotation lifts the taller side up one level without changing the order.
empty tree
Insert the values one at a time. After each one, every node on the way back up checks that its two sides differ in height by at most one.
1function insert(node, value) {2 if (node === null) return newNode(value);3 if (value < node.value) node.left = insert(node.left, value);4 else node.right = insert(node.right, value);5 update(node);6 const balance = height(node.left) - height(node.right);7 if (balance > 1) {8 if (value >= node.left.value) node.left = rotateLeft(node.left);9 return rotateRight(node);10 }11 if (balance < -1) {12 if (value < node.right.value) node.right = rotateRight(node.right);13 return rotateLeft(node);14 }15 return node;16}1718function rotateRight(y) {19 const x = y.left;20 y.left = x.right;21 x.right = y;22 update(y); update(x);23 return x;24}25// rotateLeft is the mirror image.Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | log n | per insert: the height never exceeds about 1.44 log n |
| average | log n | per insert, search or delete |
| worst | log n | even sorted input, which ruins a plain BST |
| space | n | one node per value, plus a height each |
Where it breaks
- Sorted input no longer hurts. Pick Sorted 1 to 15: a plain BST would be a chain 15 levels tall. Here the rotations keep it at 4, the height of a perfect tree.
- Zig-zags need two rotations. Pick Zig-zag: 2 lands on the inside, under 1 under 3. One rotation would just move the problem across, so the first rotation straightens the zig-zag and the second balances it.
- The price is upkeep. Every node stores a height and inserts may rotate. Red-black trees relax the rule a little to rotate less, which is why most standard libraries use them.