Какие полезные свойства имеет красно-черное дерево и почему оно используется
Что проверяют
Понимаете ли вы, какую гарантию даёт красно-чёрное дерево и почему стандартная библиотека выбрала именно его. Следом обычно спрашивают, чем оно отличается от AVL-дерева и когда std::map проигрывает другим контейнерам.
Как отвечать
Сначала правила, на которых держится баланс:
- цвет: каждый узел красный или чёрный, корень чёрный, пустые листья (NIL) считаются чёрными;
- красный узел: оба его потомка чёрные, двух красных подряд не бывает;
- чёрная высота: на любом пути от узла до листьев одинаковое число чёрных узлов.
Из правил следует главное: высота не больше 2 * log2(n + 1), самый длинный путь максимум вдвое длиннее самого короткого. Отсюда поиск, вставка и удаление за O(log n) в худшем случае, а не в среднем.
Второе свойство, ради которого его выбирают, это дешёвая балансировка. Вставке нужно не больше двух поворотов, удалению не больше трёх, остальное исправляет перекраска. AVL-дерево сбалансировано строже, поиск в нём чуть быстрее, но при изменениях поворотов больше.
Применение: std::map, std::set и их multi-версии в libstdc++, libc++ и MSVC. Стандарт не требует именно этого дерева, он требует логарифмическую сложность, упорядоченный обход и стабильность итераторов: вставка итераторы не инвалидирует, удаление инвалидирует только удалённый элемент. Упорядоченность даёт lower_bound и диапазонные запросы, которых нет у std::unordered_map.
Назовите и цену: каждый узел это отдельная аллокация с тремя указателями и цветом, обход прыгает по памяти и плохо ложится в кэш. Для небольших наборов, которые в основном читают, быстрее отсортированный std::vector с бинарным поиском или std::flat_map из C++23.
Где спотыкаются
Говорят, что дерево идеально сбалансировано. Разница путей допускается до двух раз, и это сознательный компромисс.
Утверждают, что стандарт требует для std::map красно-чёрное дерево. Требования касаются сложности и поведения итераторов, реализацию выбирают авторы библиотек.
Считают, что std::unordered_map всегда быстрее. Он даёт O(1) в среднем, но без порядка, с перехешированием и деградацией при плохой хеш-функции.