Красно-чёрные деревья

Количество черных узлов на ветви от корня до листа называется чёрной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с чёрной высотой равной 2. Кратчайшее возможное расстояние от корня до листа равно двум - когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырём - узлы при этом покрашены (от корня к листу) так: красный, чёрный, красный, чёрный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия чёрной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.
Операции

Красно-чёрное дерево - это бинарное дерево обладающее следующими свойствами:
Каждый узел покрашен либо в чёрный, либо в красный цвет.
Листьями объявляются как NIL-узлы (т.е. «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели). Листья покрашены в чёрный цвет.
Если узел красный, то оба его потомка черные.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Пример красно – чёрного дерева приведён на рисунке 1.