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

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

1. Считается, что нулевые дочерние связи на периферии дерева указывают на другие узлы (естественно, несуществующие). Эти невидимые нулевые узлы называются внешними узлами и всегда окрашены в черный цвет.

2. Условие для черных узлов: все пути от корневого узла до каждого из внешних узлов содержат одинаковое количество черных узлов.

3. Условие для красных узлов: каждый красный узел, не являющийся корневым, имеет черный родительский узел.

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

Набор простых красно-черных деревьев показан на рис. 8.6, при этом красные узлы изображены серыми квадратами (возможности одноцветной печати довольно-таки ограничены!), а внешние узлы - маленькими черными квадратами. Первое дерево (рисунок а) представляет пустое дерево - оно состоит всего из одного внешнего узла, который является черным - и, следовательно, по определению является красно-черным деревом. На примере второго и третьего деревьев (b и c) видно, что независимо от окрашивания корневого узла в красный или черный цвет, мы получаем красно-черное дерево. Эти деревья явно удовлетворяют всем трем правилам.

Рисунок 8.6. Набор простых красно-черных деревьев

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

Взглянем на это под другим углом. Посмотрите на рис. 8.7. Внутренние узлы этого дерева еще не окрашены. Можно ли их окрасить так, чтобы дерево удовлетворяло правилам 2 и 3? Никакого реального решения не существует. Невозможно окрасить внутренние узлы так, чтобы одновременно удовлетворить условия и для черных, и для красных узлов. Дерево, изображенное на рис. 8.7, не может быть красно-черным ни при каких условиях - и это хорошо, поскольку оно представляет начальную стадию вырождения дерева. Итак, важно усвоить следующий принцип: не все деревья могут быть окрашены в красный и черный цвета.

Фактически можно показать, что высота красно-черного дерева, содержащего n внутренних узлов, пропорциональна log n. Иначе говоря, в самом худшем случае для поиска в красно-черном дереве потребуется время, которое пропорционально O(log(n)). Именно к этому мы стремимся при использовании дерева бинарного поиска. Деревья, время поиска в которых пропорционально O(n), являются вырожденными.

Рисунок 8.7. Дерево, которое не может быть окрашено в красный и черный цвета

Теперь, когда мы ознакомились с правилами, определяющими структуру красно-черного дерева, возникает вопрос, как их использовать для вставки нового узла в красно-черное дерево? Начнем со знакомой операции, и выполним поиск узла. Если он будет найден, мы сигнализируем об ошибке (в красно-черном дереве дубликаты не допускаются, точно так же, как это имело место в стандартном дереве бинарного поиска). В противном случае необходимо обратиться к узлу, который можно использовать в качестве родительского узла нового узла, и определяющего, каким дочерним узлом должен быть новый узел. Теперь необходимо заменить внешний узел (вспомните, что это общее имя несуществующего узла на конце нулевой связи) новым узлом. Новый узел автоматически будет вставлен с двумя внешними узлами, которые в соответствии с правилом 1 окрашены в черный цвет. Но в какой цвет должен быть окрашен новый узел?

Начнем с того, что окрасим его в красный цвет. Как это сказывается на соблюдении правил, определенных для красно-черных деревьев? Во-первых, условие для черных узлов по-прежнему выполняется: мы заменяем черный внешний узел красным узлом и двумя черными внешними узлами. Путь от каждого из двух новых внешних узлов до корневого узла по-прежнему содержит столько же черных узлов, сколько и путь от замещенного внешнего узла до корневого узла. А как насчет условия, определенного для красных узлов? Продолжает ли оно выполняться? Возможно, да, а, возможно, и нет. Если новый узел является корневым, и, следовательно, не имеет родительского узла, созданное дерево остается красно-черным (в действительности, при желании новый узел можно было бы перекрасить в черный цвет, и при этом дерево осталось бы красно-черным). Если же новый узел не является корневым, он будет иметь родительский узел. Если этот родительский узел черный, правило 3, определенное для красных узлов, остается применимым, и дерево по-прежнему является красно-черным. Если родительский узел нового узла является корневым, то, чтобы дерево осталось красно-черным, достаточно при необходимости перекрасить родительский узел в черный цвет. (Фактически, в красно-черном дереве, если оба дочерних узла корневого узла являются черными, корневой узел может быть как красным, так и черным - это никак не сказывается на соблюдении правил.)

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

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

Назовем новый узел s (от son - сын), его родительский узел d (от dad - отец), родительский узел родительского узла g (granddad - дед), а родственный с родительским узлом - и (uncle - дядя). Непосредственно после добавления узла s возникает следующая ситуация: узлы s и d являются красными (что является нарушением правила 2), узел g должен быть черным (согласно правилу 2), а узел и может быть либо красным, либо черным.