Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Удаление узла, который имеет один внутренний и один внешний дочерний узел

Кратко напомним, в чем они состоят. Удаляемый узел имеет, по меньшей мере, один внешний узел. Если удаляемый узел красный, то его второй дочерний узел должен быть черным (конечно, он может быть внешним узлом, поскольку внешние узлы автоматически окрашиваются в черный цвет). Можно удалить узел, заменить его этим вторым дочерним узлом, и в результате дерево останется красно-черным. Если удаляемый узел является черным и имеет один красный внутренний дочерний узел, то можно удалить узел и заменить его дочерним узлом, окрасив его в черный цвет.

Однако если удаляемый узел черный и имеет, по меньшей мере, один внешний дочерний узел, а другой дочерний узел либо черный, либо внешний, то мы сталкиваемся с двумя ранее описанными проблемами. Повышение ранга дочернего узла в результате удаления приводит к нарушению правила 2 (назовем этот узел нарушающим узлом). Эти случаи представлены последними преобразованиями, изображенными на рисунках 8.10 и 8.11.

Попытаемся свести оба случая к одному. Мы должны принимать во внимание родительский и братский узлы нарушающего узла и два дочерних узла братского узла (узлы-племянники). Обратите внимание, что можно принять наличие у братского узла двух дочерних узлов (т.е. считать, что братский узел не является внешним). Почему? Рассмотрим исходное дерево. Оно было красно-черным. Следовательно, все пути, проходящие через удаленный и родительский узлы, имели то же количество черных узлов, что и пути, проходящие через братский и родительский узлы. Поскольку мы предполагаем, что родительский узел черный, а удаленный узел и заменивший его дочерний узел также были черными, то и все пути, проходящие через братский узел, должны содержать, по меньшей мере, два черных узла. Отсюда следует, что, как минимум, братский узел является черным и имеет два черных дочерних узла.

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

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

Рисунок 8.12. Балансировка после удаления: первый случай

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

Рисунок 8.13. Балансировка после удаления: второй случай

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