На этом шаге мы рассмотрим варианты, возникающие после удаления узла и пути их исправления.
Рассмотрим решение проблем, возникающих после удаления узла S.
1. Ситуация "чёрный отец, красный брат".
Исправим нарушение свойства чёрного узла:
- (1) перекрасим узел D в красный, а B - в чёрный цвет;
- (2) выполним левую ротацию узла B.
2. Ситуация "чёрный отец, чёрный брат с чёрными племянниками".
Исправим нарушение свойства чёрного узла: перекрасим узел B в красный цвет.
Ситуация исправлена, однако проблемная область переместилась вверх к родительскому узлу. Теперь "нарушителем" свойства чёрного узла стала вершина D, поэтому продолжим процесс балансировки конструируемого дерева, повторяя действия алгоритма.
3. Ситуация "красный отец, чёрный брат с чёрными племянниками".
Исправим нарушение свойства чёрного узла: перекрасим узел D в чёрный цвет, а B - в красный.
Все рассмотренные случаи имеют аналоги, являющиеся их зеркальными отражениями, но при этом анализ каждого из случаев удаления остаётся тем же.
На следующем шаге мы закнчим изучение этого вопроса.
