Зачем нужны самобалансирующиеся деревья

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

Понимаете ли вы, откуда берётся гарантия O(log n) и почему у обычного дерева поиска её нет. Следом обычно просят сравнить AVL и красно-чёрное дерево или рассказать, на чём построены std::map и std::set.

Как отвечать

• проблема: обычное BST даёт O(log n) только в среднем. Вставьте ключи по возрастанию, и дерево выродится в список высотой n, поиск станет O(n). На реальных данных (id по порядку, временные метки) это обычный случай, а не экзотика;
• решение: после вставки и удаления дерево восстанавливает инвариант высоты поворотами, и поиск, вставка, удаление, переход к соседнему элементу гарантированно O(log n) в худшем случае;
• AVL: высоты поддеревьев отличаются не больше чем на 1. Дерево ниже, поиск чуть быстрее, но изменения требуют больше работы по балансировке;
• красно-чёрное: сбалансировано слабее, высота не больше 2·log₂(n+1), зато вставке хватает двух поворотов, удалению трёх. Поэтому в libstdc++, libc++ и MSVC std::map, std::set и их multi-версии построены на нём. Стандарт реализацию не фиксирует, он требует сложность и упорядоченность;
• B-деревья: тоже сбалансированы, но узел хранит много ключей. Это основа индексов баз данных и файловых систем, где важно число чтений с диска.

Главное преимущество перед std::unordered_map: порядок. Обход по возрастанию, lower_bound, upper_bound, диапазонные запросы и гарантия худшего случая вместо средней оценки. Цена: отдельный узел на элемент, указатели, плохая локальность кэша. Для небольших наборов часто быстрее отсортированный std::vector с бинарным поиском, а в C++23 для этого появился std::flat_map.

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

Говорят, что std::map это AVL-дерево или хэш-таблица. В основных реализациях это красно-чёрное дерево, а хэш-таблица это std::unordered_map.

Считают балансировку бесплатной и не могут объяснить, почему при частых вставках выбирают красно-чёрное дерево, а не AVL.

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