Qu'est-ce qu'un arbre rouge-noir?

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

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

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

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