AVL Tree
Last Updated: May 30, 2026
A plain BST is only fast on average. Insert 1, 2, 3, 4, 5 in order and you get a tree shaped like a linked list: search, insert, and delete all degrade to O(n).
An AVL tree is the first historical answer to it. Invented in 1962 by Adelson-Velsky and Landis, it was the first self-balancing binary search tree. The idea is simple: after every insertion or deletion, check whether any node has become "too lopsided" and fix it with a local rotation. The shape of the tree stays close to a perfectly balanced one, and every operation stays at O(log n).
In this chapter, we'll cover:
- The exact balance condition that defines an AVL tree
- The four rotation cases and how to recognize each one
- Insertion and deletion with rebalancing
- A height proof that shows why O(log n) is guaranteed
- When to pick an AVL tree over a red-black tree
- A complete, working implementation