Как выглядит красно-черное дерево

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

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

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

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

Балансировка достигается за счет операций поворота и перекрашивания при вставке/удалении. Пример поворота влево:

void rotateLeft(Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != null) y.left.parent = x;
    y.parent = x.parent;
    if (x.parent == null) root = y;
    else if (x == x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.left = x;
    x.parent = y;
}