Почему красно-черное дерево является красно-черным

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

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

Эти свойства гарантируют, что дерево остается сбалансированным (высота ~O(log n)), что обеспечивает эффективные операции вставки, удаления и поиска.

Пример структуры узла:

class Node {
    int data;
    Node left, right, parent;
    boolean color; // true - красный, false - черный
}