Ответ
Красно-черное дерево — это частный случай самобалансирующегося бинарного дерева поиска (BST), решающий главную проблему обычного BST.
Обычное бинарное дерево поиска:
- Следует базовому правилу:
left child < parent < right child. - При неудачной последовательности вставок (например, отсортированные данные) может выродиться в линейный список.
- Худшая временная сложность операций поиска, вставки, удаления: O(n).
Красно-черное дерево (Red-Black Tree):
- Налагает дополнительные ограничения для поддержания баланса:
- Каждый узел имеет цвет: красный или черный.
- Корень всегда черный.
- Два красных узла не могут быть родителем и потомком (нет двух подряд идущих красных узлов).
- Все пути от любого узла до его листьев содержат одинаковое количество черных узлов (черная высота).
- Эти правила гарантируют, что дерево остается примерно сбалансированным.
- Гарантированная временная сложность операций: O(log n).
Пример структуры узла и балансировки:
class RBNode {
int key;
RBNode left, right, parent;
boolean isRed; // true для красного, false для черного
}
// При вставке/удалении выполняются вращения и перекрашивания для сохранения свойств.
Итог: Красно-черное дерево жертвует небольшой сложностью операций (из-за перекрашиваний) для гарантии логарифмической производительности, что критично для реализаций TreeMap или TreeSet в Java.