Чем красно-чёрное дерево отличается от АВЛ-дерева?

Оба — самобалансирующиеся BST с O(log n) на операции, но АВЛ держит баланс строже и быстрее ищет, а красно-чёрное допускает больший перекос и делает меньше вращений при изменениях.

Инварианты

• АВЛ: высоты поддеревьев любого узла отличаются не больше чем на 1; высота ≤ ≈1,44·log₂n.
• Красно-чёрное: корень чёрный, у красного узла нет красных детей, на всех путях до листьев одинаковое число чёрных узлов; высота ≤ 2·log₂(n+1).
• КЧ-дерево — кодировка 2-3-4-дерева: чёрный узел с красными детьми — один узел B-дерева с 2–3 ключами.

Цена изменений

• Вставка: АВЛ — не больше одного одинарного или двойного вращения; КЧ — не больше двух вращений.
• Удаление: АВЛ может потребовать вращений на каждом уровне, до O(log n); КЧ — не больше трёх вращений.
• Перекраски в КЧ бывают на всём пути вверх, но амортизированно O(1).
• Служебные данные: АВЛ хранит высоту или баланс-фактор, КЧ — один бит цвета.

Где что используют

• Красно-чёрное: std::map, TreeMap в Java, корзины HashMap с Java 8, ядро Linux — планировщик, epoll, таймеры высокого разрешения.
• АВЛ: структуры с преобладанием чтения, где важна минимальная глубина поиска; на практике разница в 1,44 против 2 редко решающая.

Как выбрать

Много вставок и удалений вперемешку с поиском — КЧ. Дерево строится редко, а читается постоянно — АВЛ или вообще отсортированный массив.

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

АВЛ балансирует строже, поэтому поиск чуть быстрее, а красно-чёрное терпит больший перекос и делает меньше вращений при вставках и удалениях. Поэтому стандартные библиотеки выбирают КЧ, а для редко меняющихся данных часто выгоднее вообще отсортированный массив.