Сбалансированные деревья поиска. Красно-черные деревья.
Определение
Красно-черное дерево (Red-Black Tree) — это разновидность сбалансированного бинарного дерева поиска, которая обеспечивает логарифмическое время выполнения основных операций (вставка, удаление, поиск). Такое дерево используется для поддержания отсортированных данных и часто используется в реализации ассоциативных массивов и других абстрактных типов данных.
Cвойства
- Каждый узел окрашен в красный или черный цвет.
- Корень дерева всегда черный.
- Все листья (NULL-узлы) считаются черными.
- Если узел красный, то оба его потомка черные (нет двух красных узлов подряд).
- Для каждого узла все пути от него до всех его потомков-листьев содержат одинаковое количество черных узлов.
Операции
При вставке нового узла красно-черное дерево может нарушить свои свойства. Для восстановления баланса дерева применяются следующие операции
- Перекрашивание: Изменение цвета узлов.
- Левый и правый повороты: Повороты узлов для поддержания баланса дерева.
При удалении узла также могут быть нарушены свойства красно-черного дерева. Процесс удаления включает в себя:
- Замещение удаляемого узла подходящим кандидатом (обычно минимальным элементом из правого поддерева или максимальным из левого).
- Применение аналогичных техник, как и при вставке, для поддержания баланса дерева.