Leg de structuur en de belangrijkste eigenschappen van rode-zwart bomen uit

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

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

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

Эти правила обеспечивают, что дерево остаётся примерно сбалансированным, что позволяет эффективно выполнять операции вставки, удаления и поиска.

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