Understanding self-balancing BSTs with a strict balance factor using rotations.
An AVL (Adelson-Velsky and Landis) tree is the first self-balancing binary search tree to be invented. It maintains its balance by ensuring that for any node, the heights of its two child subtrees differ by at most one. This difference is called the 'balance factor'. The balance factor of a node can be -1, 0, or 1. If an insertion or deletion causes this property to be violated (i.e., the balance factor becomes -2 or 2), the tree performs re-balancing operations called 'rotations'. There are four types of rotations to handle imbalance: Left rotation, Right rotation, Left-Right rotation, and Right-Left rotation. These rotations are local transformations that restructure the tree to restore the AVL property while preserving the BST property. Because AVL trees maintain a strict balance, they guarantee a height of O(log n), which in turn ensures that search, insertion, and deletion operations are always performed in logarithmic time. The trade-off is the overhead of performing rotations, which can make insertions and deletions slightly slower than in less strictly balanced trees like Red-Black Trees. AVL trees are particularly useful in applications where searches are far more frequent than modifications.