Красно-черное дерево — это разновидность самобалансирующегося бинарного дерева поиска, которое гарантирует, что длина пути от корня до любого листа не будет более чем в два раза длиннее минимального пути. Это достигается за счёт следующих свойств:

Каждый узел окрашен либо в красный, либо в чёрный цвет.
Корень всегда чёрный.
Все листья (NIL-узлы) считаются чёрными.
Если узел красный, то оба его потомка чёрные (нет двух красных подряд).
Для каждого узла все пути до листьев содержат одинаковое число чёрных узлов (чёрная высота).

Эти правила обеспечивают балансировку дерева, что гарантирует операции поиска, вставки и удаления за время O(log n). В отличие от других деревьев, например, AVL, красно-черные деревья допускают более «мягкий» баланс, что делает операции вставки и удаления менее затратными по времени на перестройку.

Пример на Java (упрощённый фрагмент):

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

// Основные операции включают повороты и перекраску для поддержания свойств дерева

Что делает красно-черное дерево особенным среди других самобалансирующихся деревьев поиска?