В чем разница красно-черного дерева и бинарного дерева?
Что проверяют
Понимаете ли вы, зачем деревьям балансировка, и знаете ли, где это лежит в стандартной библиотеке.
Как отвечать
Бинарное дерево поиска это структура, где у каждого узла не больше двух потомков, слева меньшие ключи, справа большие. Поиск, вставка и удаление стоят как высота дерева. Проблема в том, что высота не гарантирована: при вставке уже упорядоченных данных дерево вырождается в список, и операции становятся линейными.
Красно-чёрное дерево это то же дерево поиска, но с правилами балансировки, которые держат высоту логарифмической:
- каждый узел красный или чёрный, корень чёрный;
- у красного узла не бывает красных потомков;
- на любом пути от узла до листьев одинаковое число чёрных узлов.
Из этих правил следует, что самый длинный путь не более чем вдвое длиннее самого короткого, а значит операции гарантированно логарифмические. Восстанавливается баланс поворотами и перекрашиванием при вставке и удалении.
Где это встречается на практике: TreeMap и TreeSet в Java построены на красно-чёрном дереве, отсюда упорядоченность ключей и методы firstKey, headMap, subMap. Дополнительно с Java 8 корзина HashMap превращается в красно-чёрное дерево, когда в неё попадает слишком много коллизий, чтобы худший случай оставался логарифмическим.
Полезно сравнить с AVL: тот балансируется строже и даёт чуть более быстрый поиск, но дороже на вставке и удалении, поэтому в библиотеках общего назначения чаще берут красно-чёрное.
Где спотыкаются
Говорят, что бинарное дерево поиска само по себе даёт логарифмическую сложность. Только в среднем и при случайных данных.
Не могут объяснить, зачем нужны цвета, и перечисляют правила наизусть.
Забывают, что упорядоченность и есть главная причина брать TreeMap вместо HashMap, а не скорость.