Как устроено бинарное дерево поиска и зачем нужна балансировка?

BST хранит ключи так, что слева от узла меньшие, справа большие: поиск, вставка и удаление стоят O(h); без балансировки дерево вырождается в список с O(n), поэтому AVL и красно-чёрные деревья удерживают высоту O(log n).

Проблема вырождения

Вставка уже отсортированных данных в обычное BST строит «гирлянду» высоты n — поиск становится линейным.

AVL-дерево

• Для каждого узла высоты поддеревьев различаются не более чем на 1.
• Нарушение чинится поворотами (LL, RR, LR, RL) за O(1) на уровень.
• Баланс строже: поиск быстрее, вставки дороже из-за частых поворотов.

Красно-чёрное дерево

• Инварианты: корень чёрный, у красного узла дети чёрные, чёрная высота всех путей равна.
• Баланс слабее (высота до 2·log n), зато меньше поворотов на вставку и удаление, поэтому их выбирают в стандартных библиотеках (TreeMap, std::map).

Коротко для собеседования

Поиск в BST — спуск влево или вправо, и его цена равна высоте дерева. На отсортированных вставках обычное дерево вырождается в список, поэтому на практике берут самобалансирующиеся варианты: AVL, если важнее чтение, и красно-чёрное, если много изменений.