A self-balancing tree is a binary search tree that takes active steps to keep itself short. A plain binary search tree can degenerate into a long chain when keys arrive in sorted order, making operations slow; a self-balancing tree avoids this by restructuring itself during insertions and deletions so that its height stays on the order of log n no matter what order the keys come in.
The first such structure was described in 1962 by Georgy Adelson-Velsky and Evgenii Landis in their paper “An algorithm for the organization of information,” now known after their initials as the AVL tree. The AVL tree keeps, at every node, the heights of the two subtrees differing by at most one. When an insertion or deletion violates this balance condition, the tree performs local rotations, small rearrangements of a few nodes that restore balance without disturbing the search ordering.
Rotations are the shared mechanism behind self-balancing trees. A rotation changes the parent-child relationships of a small cluster of nodes while preserving the left-less-than-right invariant, so the tree remains a valid search tree but becomes shorter where it had grown too deep. Different balancing schemes choose different rules for when and how to rotate.
Later designs such as red-black trees relax the strict height-balance of AVL trees in favor of a looser coloring rule that still guarantees logarithmic height while making updates cheaper in some workloads. These balanced trees underpin ordered containers in many language standard libraries, such as the ordered map and set types that keep their keys sorted and support fast lookup.