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

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

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

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

Разница:

• Красно-черное дерево гарантирует балансировку (O(log n) для операций), а обычное бинарное дерево может выродиться в список (O(n)).

Пример вставки в красно-черное дерево (Java):

class Node {
    int data;
    Node left, right, parent;
    boolean isRed;
}

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