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

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

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

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

Разница:

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

// Пример узла красно-черного дерева
data class RBNode(
    val value: Int,
    var left: RBNode? = null,
    var right: RBNode? = null,
    var color: Boolean = RED // RED = true, BLACK = false
)