Кратко и по делу.
Что это такое
- Красно‑чёрное дерево — это бинарное дерево поиска, в котором каждому узлу приписан цвет (красный/чёрный) и поддерживаются дополнительные свойства для гарантии логарифмической высоты.
Инварианты (свойства), которые оно поддерживает
1. Каждый узел либо красный, либо чёрный.
2. Корень чёрный.
3. Все NULL‑(sentinel) листья считаются чёрными.
4. Если узел красный, то оба его ребёнка чёрные (нет двух подряд красных узлов).
5. Для каждого узла все простые пути от него до всех его листьев содержат одинаковое число чёрных узлов (одинаковая чёрная высота).
Обозначая число узлов в дереве $n$ и высоту дерева $h$, эти правила дают оценку высоты: $h\le 2{\log }_2(n+1)$.
Когда предпочесть красно‑чёрное дерево вместо AVL
- Операции поиска/вставки/удаления имеют асимптотику $O(\log n)$ в обоих типах деревьев, но характер различается:
- AVL строже сбалансировано (меньшая высота, примерно $\le 1.44{\log }_{2}n$), поэтому даёт чуть быстрее операции поиска — полезно при очень частых чтениях и редких модификациях.
- Красно‑чёрное менее строгое, часто требует меньше вращений при вставке/удалении и допускает меньше изменений структуры в среднем — полезно при частых модификациях (insert/delete).
- Дополнительно: RB‑дерево требует только 1 бита на узел для цвета (против двух‑битного фактора баланса у AVL), и исторически широко используется в системных/библиотечных реализациях (std::map, TreeMap, Linux rb‑tree), что делает его практичным выбором.
Сложности реализации удаления
- Удаление сложнее вставки: сначала выполняется обычное BST‑удаление (возможно замена узлом‑преемником), но если удаляемый (или перемещённый) узел был чёрным — нарушается свойство чёрной высоты.
- Вводится концепция «двойной чёрности» (double‑black) на месте удаления; для её устранения нужен набор случаев:
1. Брат красный → ротация и перекраска (приводит к ситуации с чёрным братом).
2. Брат чёрный и оба его дети чёрные → перекраска брата в красный и перенос проблемы вверх (повторение).
3. Брат чёрный и хотя бы один ребёнок красный → выполняются ротации и перекраски, после чего двойная чёрность исчезает.
- Практические сложности:
- Множество различных случаев и ветвлений в коде — легко допустить ошибку; нужно аккуратно работать с указателями и цветами.
- Необходимо корректно работать с sentinel NULL‑узлами (чёрные листья).
- Исправление может «подниматься» вверх по дереву (в худшем случае до корня), то есть требуется цикл исправления; это даёт время восстановления $O(\log n)$. При этом может потребоваться до $O(\log n)$ перекрашиваний и несколько ротаций (в типичных реализациях ротации выполняются лишь в некоторых ветках цикла).
- При удалении узла с двумя детьми нужно корректно заменить его преемником и перенести цвет, что добавляет дополнительные места для ошибок.
- Вывод по сложности: корректная реализация удаления требует тщательной проработки всех случаев, тестирования и аккуратной работы с sentinel‑узлами; алгоритм выполняется за $O(\log n)$, но программно сложнее и более подвержен багам, чем вставка.