В чем разница между бинарным и красно-черным деревьями

Бинарное дерево - это структура данных, где каждый узел имеет не более двух потомков. Основное требование: левый потомок меньше родителя, правый - больше.

Красно-черное дерево - это самобалансирующееся бинарное дерево с дополнительными свойствами:

1. Каждый узел красный или черный
2. Корень всегда черный
3. Красные узлы не могут иметь красных потомков
4. Все пути от узла до листьев содержат одинаковое количество черных узлов

Пример красно-черного дерева:

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

Главное отличие: красно-черное дерево автоматически балансируется при вставке/удалении, сохраняя сложность O(log n), тогда как обычное бинарное дерево может выродиться в список с O(n) в худшем случае.