Что такое красно-чёрное дерево

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

Основные свойства:

1. Каждый узел — либо красный, либо чёрный.
2. Корень всегда чёрный.
3. Все листья (NIL) — чёрные.
4. У красного узла оба потомка чёрные.
5. Пути от узла до листьев содержат одинаковое число чёрных узлов.

Пример (вставка):

class Node {
    int data;
    Node left, right, parent;
    boolean isRed;
    
    Node(int data) {
        this.data = data;
        this.isRed = true; // Новый узел всегда красный
    }
}

Балансировка достигается перекрашиванием и поворотами при нарушении свойств.