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

Листинг 8.24. Интеллектуальная подпрограмма IsRed

function IsRed(aNode : PtdBinTreeNode): boolean;

begin

if (aNode = nil) then

Result := false else

Result := aNode^.btColor = rbRed;

end;

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

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

узел имеет один реальный дочерний узел и один внешний дочерний узел;

и, наконец, узел имеет два реальных дочерних узла. Удаление узла выполняется так же, как это делалось в стандартном неокрашенном дереве бинарного поиска.

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

А как насчет второй возможности (когда удаляемый узел окрашен в черный цвет)? Что ж, в этом случае правило 2, сформулированное для черных узлов, неизбежно нарушается. Количество черных узлов в пути до корневого узла уменьшается на 1. Возникающая в результате такого преобразования проблема проиллюстрирована на нижней части рисунка 8.10. Мысленно заложим в этом месте закладку и рассмотрим другие случаи.

Рисунок 8.10. Удаление узла, имеющего два внешних дочерних узла

Второй случай удаления - удаление узла, который имеет один реальный дочерний узел и один внешний дочерний узел. Предположим, что удаляемый узел является красным. Его единственный реальный дочерний узел будет черным. Можно удалить узел и заменить его единственным дочерним узлом. Это не приведет к нарушению правила 2, - в конечном счете, мы удаляем красный узел, - а правило 3 в данном случае не затрагивается, следовательно, дерево остается красно-черным. Этот случай представлен первым преобразованием на рис. 8.11.

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

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

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

Рисунок 8.11.

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

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

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

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

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