An AVL tree is a binary search tree that repairs itself. Each node stores its height; after an insert or delete, the walk back up recomputes heights and balance factors (left height minus right height). Where a node reaches ±2, one or two rotations lift the taller side, keeping the order intact. The small numbers beside each node are its balance factor and height.
- Typical operation
- O(log n)
- Space
- O(n)