Какую проблему решают красно-черные деревья?
Что проверяют
Понимаете ли вы, почему обычное бинарное дерево поиска ненадёжно и какой ценой балансировка возвращает гарантии. Питонистам следом задают практический вопрос: что в Python использовать, если нужен упорядоченный словарь.
Как отвечать
Проблема: обычное BST на отсортированных данных вырождается в список, высота становится n, и поиск, вставка, удаление идут за O(n). Красно-чёрное дерево держит высоту не больше 2·log2(n+1), поэтому все три операции гарантированно O(log n) даже в худшем случае.
Как оно этого добивается:
- цвет узла: каждый узел красный или чёрный, корень и пустые листья чёрные;
- нет двух красных подряд: у красного узла оба потомка чёрные;
- одинаковая чёрная высота: на любом пути от узла до листьев одно и то же число чёрных узлов. Из двух последних правил следует, что самый длинный путь не более чем вдвое длиннее самого короткого;
- восстановление: после вставки или удаления свойства чинятся перекрашиванием и поворотами, поворотов не больше двух при вставке и трёх при удалении.
Сравнение с AVL: AVL балансирует строже, поиск в нём чуть быстрее, но изменения дороже. Красно-чёрное дерево выгоднее, когда вставок и удалений много. Отсюда применения: TreeMap в Java, std::map в C++, планировщик и таймеры в ядре Linux.
Мост к Python: сбалансированного дерева в стандартной библиотеке нет. dict и set это хэш-таблицы, порядок в dict только по вставке. Для отсортированной коллекции берут bisect над списком (вставка O(n) из-за сдвига элементов), heapq, если нужен только минимум, или библиотеку sortedcontainers с SortedDict и SortedList.
Где спотыкаются
Говорят, что дерево идеально сбалансировано. Нет, допускается перекос до двух раз, в этом и смысл компромисса.
Считают, что dict в Python упорядочен по ключам. Он помнит порядок вставки, а не сортировку.
Приписывают красно-чёрные деревья индексам баз данных. На диске там B-деревья: у них большой коэффициент ветвления и мало обращений к страницам.