На этом шаге мы закончим изучение этого вопроса.

4. Ситуация "чёрный брат с чёрным и красным племянниками".

(а) C - левый потомок D, N_l - чёрный узел, N_r - красный узел:

Исправим нарушение свойства чёрного узла:

(1) перекрасим узел N_r в чёрный цвет, узел B - в цвет родительского узла D, а узел D - в чёрный цвет;
(2) выполним левую ротацию узла B.

(б) зеркальное отражение случая (а): C - правый потомок D, N_l - красный узел, N_r - чёрный узел:

Исправим нарушение свойства чёрного узла:

(1) перекрасим узел N_l в чёрный цвет, узел B - в цвет родительского узла D, а узел D - в чёрный цвет;
(2) выполним правую ротацию узла B.

В рассмотренных случаях (а) и (б) свойство красного узла выполняется, т.к. не было введено никаких новых красных узлов.

Свойство чёрного узла также выполняется, т.к. все пути, проходящие через нарушающий узел, содержат теперь дополнительный чёрный узел. Пути, проходящие через дочерние деревья племянника, который был окрашен в красный цвет, содержат то же количество чёрных узлов, что и ранее.

Следовательно, во всех случаях свойство чёрного узла выполняется, и результирующее дерево является красно-чёрным.

(в) C - левый потомок D, N_l - красный узел, N_r - чёрный узел:

Исправим нарушение свойства чёрного узла:

(1) перекрасим узел N_l в цвет узла D, а узел D - в чёрный цвет;
(2) выполним спаренный двусторонний поворот узла N_l (RL-поворот) для размещения узла N_l на месте узла D.

(г) зеркальное отражение случая (в): C - правый потомок D, N_l - чёрный узел, N_r - красный узел:

Исправим нарушение свойства чёрного узла:

(1) перекрасим узел N_r в цвет узла D, а узел D - в чёрный цвет;
(2) выполним спаренный двусторонний поворот узла N_r (LR-поворот) для размещения узла N_r на месте узла D.

В рассмотренных случаях (в) и (г) свойство красного узла выполняется, т.к. не было введено новых красных узлов.

Свойство чёрного узла также выполняется, т.к. все пути, проходящие через нарушающий узел, содержат дополнительный чёрный узел.

Пути, проходящие через дочерние деревья племянника, который был окрашен в красный цвет, содержат то же количество чёрных узлов, что и ранее.

Следовательно, во всех случаях свойство чёрного узла выполняется, и результирующее дерево является красно-чёрным.

Замечание (важное). Если нарушающий узел удаётся переместить до позиции корневого узла, создаётся предельная ситуация. В этом случае нарушающий узел не имеет родительского узла и, следовательно, не может иметь братский узел. При этом нарушающий узел больше не представляет проблемы.

На следующем шаге мы приведем рассмотренный алгоритм на псевдокоде.

Предыдущий шаг Содержание Следующий шаг