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

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

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

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

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

public void insert(int key) {
    Node newNode = new Node(key);
    // Обычная вставка как в BST
    // Затем балансировка:
    fixInsert(newNode);
}
private void fixInsert(Node node) {
    while (node != root && node.parent.color == RED) {
        // Логика перекрашивания и поворотов
    }
    root.color = BLACK;
}