Können Sie die Struktur und die wichtigsten Eigenschaften von Rot-Schwarz-Bäumen erklären?

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

Основные свойства:

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

Эти свойства обеспечивают, что дерево остается примерно сбалансированным, предотвращая вырождение в список.

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