Шаг 161.
Основы языка Haskell. Рекурсивные типы данных.... Удаление узла из красно-чёрного дерева. Корректировка свойств красно-чёрного дерева после удаления узла

    На этом шаге мы рассмотрим варианты, возникающие после удаления узла и пути их исправления.

    Рассмотрим решение проблем, возникающих после удаления узла S.

    1. Ситуация "чёрный отец, красный брат".

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

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

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

    Ситуация исправлена, однако проблемная область переместилась вверх к родительскому узлу. Теперь "нарушителем" свойства чёрного узла стала вершина D, поэтому продолжим процесс балансировки конструируемого дерева, повторяя действия алгоритма.

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

    Исправим нарушение свойства чёрного узла: перекрасим узел D в чёрный цвет, а B - в красный.

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

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




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