Что такое красно-черные деревья?

Что проверяют

Знаете ли вы, зачем дереву поиска балансировка и какой ценой она достигается. Для питониста это ещё и проверка трезвости: в самом языке такой структуры нет, и в рабочей задаче вы сначала посмотрите на словарь или на отсортированный список.

Как отвечать

Красно-чёрное дерево это двоичное дерево поиска с битом цвета у каждого узла и набором инвариантов, которые держат высоту логарифмической: корень и пустые листовые заглушки чёрные, у красного узла оба потомка чёрные, и от любого узла до всех его листьев на пути одинаковое число чёрных узлов. Отсюда самый длинный путь не более чем вдвое длиннее самого короткого, а поиск, вставка и удаление стоят O(log n) в худшем случае.

Вставка идёт как в обычном дереве поиска, новый узел красится в красный, дальше инварианты чинятся перекрашиваниями и поворотами вверх по дереву, причём поворотов на операцию константное число. Уместно сравнить: AVL балансирует строже и выигрывает на чтении, красно-чёрное дешевле при частых вставках и удалениях, поэтому его выбрали для TreeMap, std::map и структур ядра Linux.

В Python готового красно-чёрного дерева в стандартной библиотеке нет: dict и set это хеш-таблицы, для упорядоченного доступа берут bisect поверх списка или sortedcontainers, где внутри не дерево, а список списков. Сказать это прямо сильнее, чем пересказывать чужую реализацию.

Где спотыкаются

Формулируют инвариант про чёрные узлы в отрыве от узла отсчёта. Считаются пути от конкретного узла до его собственных листьев, а листьями при этом считаются пустые заглушки, а не последние узлы со значениями.

Утверждают, что индексы в базах данных строятся на красно-чёрных деревьях. Там B-деревья и B+-деревья: узел подбирается под страницу диска, чтобы уменьшить число чтений, а двоичное дерево на диске означает лишнее обращение почти на каждом уровне.

Берутся писать вставку и удаление у доски и тонут в разборе случаев с дядей и дедом. Сильнее проговорить инварианты, идею поворотов и сложность, а про полный разбор удаления честно сказать, что его держат в голове единицы.