Какая сложность вставки и удаления элементов в красно-черном дереве

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

Знаете ли вы, откуда берётся логарифм и почему он гарантирован, а не «обычно». В Java вопрос сразу ведут к TreeMap и TreeSet, а следом спрашивают, чем красно-чёрное дерево отличается от AVL.

Как отвечать

Короткий ответ: вставка, удаление и поиск стоят O(log n) в худшем случае. Дальше объясните, почему:

• инварианты: узел красный или чёрный, корень чёрный, у красного узла нет красных детей, на любом пути от узла до листьев одинаковое число чёрных узлов;
• следствие: самый длинный путь не более чем вдвое длиннее самого короткого, высота не превышает 2·log₂(n + 1). Поиск места для вставки или удаления идёт по этой высоте;
• вставка: новый узел красный, дальше перекраска и повороты. Поворотов не больше двух, перекраска может подниматься к корню, но это тоже O(log n), а амортизированно O(1);
• удаление: случаев больше, но поворотов не больше трёх, итог тот же O(log n).

Практическая часть для Java. На красно-чёрном дереве построены TreeMap и TreeSet, поэтому put, remove, get, floorKey, ceilingKey работают за O(log n). Такое же дерево HashMap строит внутри корзины, когда в ней скапливается много коллизий.

Сравнение с AVL стоит держать наготове: AVL сбалансировано строже (высота около 1,44·log₂ n), поэтому поиск в нём чуть быстрее, а вставка и удаление требуют больше поворотов. Красно-чёрное дерево выбирают, когда изменений много.

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

Называют сложность вставки O(1), имея в виду только перебалансировку, и забывают про поиск места: без спуска по дереву вставить нельзя, а спуск уже O(log n).

Путают красно-чёрное дерево с кучей и отвечают про PriorityQueue, где вставка тоже логарифмическая, но структура и гарантии другие.

Говорят, что TreeMap быстрее HashMap, потому что «дерево сбалансировано». Для точного поиска хэш-таблица в среднем даёт O(1), а дерево нужно ради порядка ключей и диапазонных запросов.