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

Основные свойства красно-чёрного дерева:

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

Пример использования в Java — класс TreeMap основан на красно-чёрном дереве, что обеспечивает упорядоченное хранение ключей с эффективным доступом.

Что такое красно-чёрное дерево?