#53_ALG

КРАСНО-ЧЕРНОЕ ДЕРЕВО - бинарное самобалансирующееся дерево должно соответствовать следующим характеристикам:
1. Все вершины дерева покрашены в КРАСНЫЙ или ЧЕРНЫЙ цвет;
2. Корень дерева всегда ЧЕРНОГО цвета;
3. Красно-черное дерево является бинарным деревом, т.е. у каждой вершины имеется не более двух сыновей (потомков) и они могут быть черными вершинами без ключей - ЛИСТЬЯМИ;
4. Потомки красной вершины всегда ЧЕРНЫЕ;
5. Для любой вершины V на любом нисходящем пути от V до листа ОДИНАКОВОЕ количество ЧЕРНЫХ ВЕРШИН.
6. ЛИСТЬЯ красно-черного дерева всегда ЧЕРНЫЕ.

Алгоритм ВСТАВКИ вершины в RBT (red-black tree) - INSERT:
Для вставки вершины X в RBT,
ЕСЛИ дерево было пустым, то просто вставляем X в дерево и красим его в ЧЕРНЫЙ цвет так как Х становиться корнем дерева, а корень должен быть черным;
ИНАЧЕ ЕСЛИ вершина подходящая на роль родителя для Х - ЧЕРНАЯ, ТО осуществляем вставку Х в дерево, красим Х в КРАСНЫЙ и на этом вставка завершается;
ИНАЧЕ ЕСЛИ вершина подходящая на роль родителя для Х - КРАСНАЯ, ТО:
ЕСЛИ ДЯДЯ икса (Х) - КРАСНЫЙ, перекрашиваем ДЯДЮ и РОДИТЕЛЯ в ЧЕРНЫЙ, А ДЕДУШКУ в КРАСНЫЙ и проверяем рекурсивно остальные вершины пока не достигнем корня или балансировки;
ЕСЛИ ДЯДЯ - ЧЕРНЫЙ, то выполняем не более 2-х поворотов и перекрашивание.