An AVL tree is a self-balancing binary search tree. After every insertion, each node checks its balance factor (left height minus right height). If any node exceeds +/-1, a rotation restores balance.
Georgy Adelson-Velsky and Evgenii Landis introduced the AVL tree in 1962, making it the first self-balancing BST. Four rotation cases handle every imbalance: left-left and right-right require a single rotation, while left-right and right-left require a double rotation (rotate the child first, then the parent).
The height difference at every node is maintained at most 1, which means an AVL tree of n nodes has height at most ~1.44 log₂(n). This is stricter than a red-black tree, giving faster lookups at the cost of more rotations during insertion.
Watch the search path light up as a value finds its place. When imbalance triggers, nodes rearrange through single or double rotations. The tree never degenerates into a linked list, guaranteeing O(log n) operations.
Wikipedia