An ordinary binary search tree's speed depends entirely on staying reasonably balanced — roughly the same number of nodes on each side of any given point in the tree. Insert data in an unlucky order, though, such as a list already sorted from smallest to largest, and a plain binary search tree degrades into something closer to a single lopsided chain, with search times that crawl from the fast logarithmic performance the structure is prized for down to the same slow linear performance as a basic list. Self-balancing trees, like AVL trees and red-black trees, exist specifically to prevent that collapse — automatically, after every single insertion or deletion, without needing anyone to intervene.
Detecting imbalance and fixing it with rotations
AVL trees, one of the earliest self-balancing designs, track a "balance factor" at every node — essentially, how much taller one side of that node's subtree is than the other. Whenever an insertion or deletion pushes that balance factor beyond an allowed threshold, the tree performs a rotation: a local restructuring operation that shifts a small cluster of nodes around a pivot point, restoring balance in that area without disturbing the tree's fundamental ordering property (everything smaller still ends up to the left, everything larger to the right). A single insertion might trigger just one rotation, or occasionally a short cascading sequence of them, but the process always completes quickly, and it guarantees the tree never drifts far from balanced no matter what order data arrives in.
Red-black trees: a looser but cheaper guarantee
Red-black trees take a related but distinct approach, colouring each node either red or black and enforcing a specific set of rules about how those colours can be arranged (for instance, no red node can have a red child, and every path from the root to an empty leaf must pass through the same number of black nodes). Those colour-based rules mathematically guarantee the tree stays reasonably balanced, though somewhat less tightly than an AVL tree does — red-black trees tolerate slightly more imbalance in exchange for requiring fewer rotations on average during insertions and deletions, which is exactly the trade-off that makes them the more common choice in many real-world library implementations, where insertion and deletion speed often matters more than having the absolute tightest possible balance.
What we're still unsure about
The rotation mechanisms and balance guarantees behind AVL and red-black trees are precisely specified, mathematically proven computer science, not in any dispute. What remains more a matter of engineering judgement than settled theory is choosing which self-balancing structure — or an entirely different one, like a B-tree or skip list — best fits a specific real-world workload, since the right choice depends on the actual mix of insertions, deletions, and lookups a system will face, and on hardware details like memory access patterns, which is why several different self-balancing designs continue to coexist in practice rather than one having displaced all the others.
This sits inside Balanced Trees (AVL, Red-Black), one of eight topics in Data Structures, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.