Самобалансирующиеся деревья: AVL и красно-чёрное дерево

Коротко: Деревья поиска, которые перестраиваются после вставки и удаления, чтобы не выродиться в длинную цепочку и операции оставались быстрыми.

Подробнее: Двоичное дерево поиска находит значения за O(log n), если оно сбалансировано. Но если вставлять отсортированные данные (1, 2, 3, 4, …), получается длинная «цепочка» с затратами O(n). Самобалансирующиеся деревья обнаруживают такой дисбаланс и восстанавливают баланс вращениями.