Какие свойства определяют красно-черное дерево и почему оно так называется?

Красно-черное дерево — это тип самобалансирующегося бинарного дерева поиска (BST). Оно называется так потому, что каждый узел помечается дополнительным битом — цветом (красным или черным). Эти цветные метки и набор строгих правил обеспечивают приближенную балансировку, гарантируя эффективность операций.

Пять обязательных свойств красно-черного дерева:

1. Цвет узла. Каждый узел либо красный, либо черный.
2. Корень. Корень дерева всегда черный.
3. Листья (NIL). Все листья (NIL-узлы, фиктивные потомки) считаются черными.
4. Ограничение на красные узлы. У красного узла оба потомка должны быть черными (т.е. два красных узла не могут быть соседними).
5. Путевое свойство. Для каждого узла все простые пути от него до любых листьев-потомков содержат одинаковое количество черных узлов (это число называется черной высотой).

Зачем нужны эти свойства? Они ограничивают "разбалансировку" дерева. В худшем случае длина пути от корня до листа не более чем в два раза превышает самый короткий путь. Это гарантирует, что высота дерева O(log n), а операции поиска, вставки и удаления выполняются за логарифмическое время.

Пример структуры узла (упрощенно):

class RBNode<K, V> {
    K key;
    V value;
    RBNode<K, V> left, right, parent;
    boolean color; // Конвенция: true для RED, false для BLACK
    // ... методы
}

Название "красно-черное" прямо указывает на ключевой механизм балансировки — управление цветом узлов согласно заданным правилам.