Friday, October 14, 2011

Абстрактные типы данных - Красно-чёрные деревья (Red black trees)

Концепция
Вставка снизу вверх
Удаление снизу вверх
Вставка сверху вниз
Удаление сверху вниз
Заключение

Вместо предисловия

...от переводчика. Данная статья является переводом материалов с сайта Жюльена Валкера (Julienne Walker) eternallyconfuzzled.com. Там вы сможете найти множество других статей на английском, включая и оригинал этой статьи. Итак, почему я решил опубликовать здесь статью про красно-чёрные деревья - абстракный тип данных? Абстрактные типы данных, такие, как бинарные деревья, очереди, хэш-таблицы и проч. интенсивно используются в ядрах операционных систем. От успешности реализации этих структур в немалой степени зависит производительность ядра. Поэтому, я считаю, что знание таких структур и алгоритмов работы с ними не менее важно, чем знание устройства различных подсистем и железа. Для примера, те же самые красно-чёрные деревья используются в драйвере ext3, подсистеме управление памятью при упорядочивании диапазонов выделения виртуальных адресов, планировщике запросов ввода-вывода, драйверах некоторых физических устройств и даже планировщике процессов ядра Linux. Да и вообще, знание таких алгоритмов должно пойти на пользу не только тем, кто хочет лучше познакомиться с ядрами изнутри, но и любому программисту, который, быть может, никогда не имел дело с кодом ядра и занят исключительно юзерлэндом. Современные фреймворки вроде монструозного .NET с его рантаймом, который скрывает от пользователя (программиста) все тонкости таких структур, не заменят знания и для написания небольших по размерам результирующего кода, эффективных и быстрых приложений по прежнему необходимо понимание хотя бы базовых алгоритмов. Для лучшего понимания читателю стоит познакомиться с бинарными деревьями поиска прежде чем приступать к чтению данного материала. У автора данного руководства есть статья и об этих деревьях, но, к сожалению, объём статей достаточно велик, а я не всегда располагаю свободным временем в необходимой мере. Возможно, в будущем я переведу и опубликую здесь и их, но не могу обещать слишком многого. В целях наглядности я преобразовал оригинальные схемы в ASCII в рисунки. Данные картинок внедрены в HTML в виде Base64 строк. По идее, все современные браузеры должны без проблем отображать эти внедрённые строки, как графику. Код, приведённый в статье, не предназначен для работы внутри ядра. Это всего лишь пояснение на примере, если можно так выразиться. Более того, эта реализация деревьев вообще не имеет ничего общего с теми, что в ядре. Цель статьи, однако, дать представление об алгоритмах на красно-чёрных деревьев безотносительно к ядру. Заранее приношу свои извинения за возможные неточности. Перевод делался в тесных временных рамках и поэтому не застрахован от ошибок. Я буду вам весьма признателен, если со временем вы поможете мне улучшить статью, указав в комментариях на найденные вами ошибки, неточности и прочие недочёты. Ещё, на примере прошлых статей я обнаружил прискорбный факт. Люди оставляют свои вопросы или комментарии, но я замечаю их слишком поздно и даже не знаю, есть ли смысл отвечать на вопросы, заданные несколькими месяцами ранее. Я не очень часто захожу сюда, если быть честным до конца и потому прошу прощения у всех, чьи вопросы так и остались без ответов, либо ещё останутся в будущем. Однако, если вы, уважаемый читатель, найдёте в комментариях вопрос, на который сможете ответить и тем самым помочь кому-то, пожалуйста, сделайте это. Я буду только благодарен вам. Ну, вот вроде бы и всё. Приятного чтения и надеюсь, вы найдёте здесь что-то полезное для себя.

Поехали.

Добро пожаловать обратно. Или, если это ваше первое знакомство с красно-чёрными деревьями, приготовьтесь хорошо провести время. Но для начала выясним, зачем нужна ещё одна статья по красно-чёрным деревьям? Любой, кто введёт соответствующий запрос в Google, получит в ответ тонны ссылок на различные ресурсы, включая учебники, общие описания, Java-апплеты, документы, библиотеки и даже презентации в Power Point. Хорошие новости. Но недостаточно хорошие. Большинство ресурсов, посвящённых данной теме ограничивается лишь описанием операции вставки. Прочие не описывают операцию удаления доступным образом, чтобы кто угодно смог понять, почему это работает, полагая, что перечисления различных ситуаций должно быть достаточно. Что ещё хуже, ни один ресурс не упоминает о том, что есть несколько различных реализаций красно-чёрных деревье.

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

Когда речь заходит о красно-чёрных деревьях, только один источник принимается всеми: "Введение в алгоритмы" Кормена, Лейзерсона и Ривеста (“Introduction to Algorithms” by Cormen, Leiserson, and Rivest), книга, также известная под аббревиатурой CLR. И это на самом деле хороший источник, потому что в книге описывается не только вставка и удаление, но приводится достаточно псевдокода для обеих операций. Принимая во внимание, что это известный источник и его текст легко доступен, чуть ли не каждая реализация красно-чёрных деревьев, используемая на практике, является трансляцией той, версии, что изложена в CLR. К сожалению, подход, описанный в CLR сложен и неэффективен, весьма интенсивно использует родительские указатели. Однако красно-чёрные деревья не обязаны быть такими сложными.

Для меня изучение красно-чёрных деревьев было непростым. Имея лишь описание правил, я прорабатывал каждый случай, какой только мог придумать, пытаясь вывести алгоритм. Не имея копии CLR, я не мог увидеть, как предполагалось решать проблему. Это хорошо, потому что я нашёл разные решения и, т.о., я избавился от большинства сложностей оригинального алгоритма. Ранясь об острые углы алгоритмов, я приходил в отчаяние, пытаясь заставить их работать и теперь я делюсь с вами результатами своих усилий, дабы вам не пришлось идти той же тропой.

Эта статья описывает обе разновидности алгоритмов - нерекурсивные операции сверху-вниз и рекурсивные алгоритмы снизу-вверх как для вставки, так и для удаления. Все вариации проиллюстрированы кодом на С. Наиболее распространённая реализация основана на псевдокоде из CLR, однако я не буду её освещать, потому что это всего лишь реализация алгоритма с направлением снизу-вверх. Если вас интересует реализация красно-чёрного дерева с родительскими указателями, в вашем распоряжении либо CLR (см. выше), либо прекрасная онлайн-книга Бена Пфаффа (Ben Pfaff). Если вас интересует нерекурсивная реализация дерева с использованием стека вместо рекурсии, опять же, упомянутая книга Бена Пфаффа описывает и её. Я не вижу смысла лишний раз воспроизводить здесь то, что где-то уже было хорошо описано.

Концепция [наверх]

По своей сути бинарные деревья поиска являются простой структурой данных с эффективными операциями поиска, вставки и удаления за O(lg n) итераций. Это в большой степени справедливое утверждение, если мы предполагаем, что входные данные не упорядочены. Однако по крайней мере в 3 наихудших случаях бинарные деревья поиска перестают быть структурами данных с логарифмической эффективностью, вырождаясь в знаменитый связный список. Два таких наихудших случая - это упорядоченные данные на входе, отсортированные либо в возрастающем, либо в убывающем порядке (третий из упомянутых случаев - the third is outside-in alternating order). При том, что бинарные деревья хранят данные в отсортированном виде, если на входе у нас также упорядоченные данные, это порождает проблему. Например, добавим в бинарное дерево поиска последовательно следующие значения 0, 1, 2, 3, 4. Т.е. каждое новое значение больше предыдущего, оно будет добавлено в правую ветку как дочерний узел к узлу предыдущего значения:

Такое бинарное дерево поиска не очень-то хорошее. Производительность падает с O(lg n) до O(n), потому что теперь дерево фактически является линейной структурой данных. Было бы лучше, если бы каждый узел имел два дочерних узла вместо одного. Т.о., мы бы сполна воспользовались преимуществом бинарной природы дерева поиска:

Много клеток мозга пало в бою за идею, как гарантировать такую оптимальную структуру, которая называется сбалансированным бинарным деревом поиска. К сожалению, поддержание дерева в таком идеально сбалансированном состоянии требует массы усилий, так что невозможно гарантировать постоянство идеальной сбалансированности в любое время. Тем не менее, в наших силах подойти достаточно близко к тому, чтобы гарантировать логарифмическую эффективность дерева. Многие из таких "приближающих" стратегий нашли широкое применение. Два предшественника этих оптимизирующих схем - AVL-деревья и, собственно, красно-чёрные деревья. Здесь мы коснёмся только красно-чёрных деревьев, т.к. по AVL-деревьям есть отдельная статья.

Изначально красно-чёрные деревья были абстракцией абстракции, которая стала самостоятельной структурой данных. Рудольф Байер (Rudolf Bayer) предложил абстракцию, которую он назвал симметричным бинарным B-деревом. Мысль состояла в моделировании B-дерева 4-го порядка (каждый узел может иметь 4 ссылки в то время, как бинарное дерево допускает лишь две ссылки на узел). Принимая во внимание, что все пути, ведущие от корня к некоему листу дерева, содержат одно и то же число узлов, все листья в B-дереве находятся на одном уровне. Это идеально сбалансированное дерево, однако не бинарное дерево поиска, как требовалось.

Основная идея симметричных бинарных B-деревьев состоит в том, что узел может иметь горизонтальные или вертикальные связи. Т.о., бинарное дерево поиска моделирует структуру узлов B-дерева. Вертикальные связи отделяют друг от друга два разных узла, а горизонтальные - узлы, которые логически рассматриваются, как один узел B-дерева. Ниже приведено сравнение эквивалентных B-деревьев и симметричных бинарных B-деревьев (* = неизвестный узел). Обратите внимание, как структура узлов B-дерева подменяется использованием нескольких узлов бинарного дерева:

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

Позже Робертом Седжвиком (Robert Sedgewick) и Леонидасом Гибасом (Leonidas Guibas) была предложена мнемоническая абстракция, которая облегчала понимание симметричных бинарных B-деревьев (кроме того, название тоже сократилось!). Вводя новый атрибут узла - цвет, вы можете легко дифференцировать вертикальные и горизонтальные связи. В рамках этой абстракции узлы, являющиеся частью одного логического узла B-дерева (горизонтальная связь) имеют красный цвет, в то время, как узлы, отделяющие друг от друга логические узлы B-дерева (вертикальные связи) имеют чёрный цвет. Так на свет появились красно-чёрные деревья. Ниже приводятся деревья из 2, 3 и 4 узлов, представленные в виде красно-чёрной абстрактной модели:

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

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

Наконец, вершиной красно-чёрного дерева должен быть узел чёрного цвета. Это не лишено смысла, т.к. только чёрный узел может иметь красных детей, а вершина не имеет родительского узла. Однако, это правило применимо к абстракции B-дерева. На деле вершина может быть либо красной, либо чёрной и это никак не влияет на эффективность красно-чёрного дерева.

Все алгоритмы, обеспечивающие балансировку красно-чёрного дерева, не должны нарушать ни одного из этих правил. Если все правила соблюдаются, то дерево является действительно красно-чёрным и его высота не может быть короче lg (n + 1), но также не выше 2lg (n + 1). Эти величины логарифмические, так что красно-чёрное дерево гарантирует аппроксимацию наилучшего случая бинарного дерева поиска.

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

Прежде чем мы приступим, нам понадобится основа и небольшой скелет для кода. Для начала, структуры узла и дерева. Каким образом вы введёте цвет, зависит от вас. Общее решение - поле перечисляемого типа, принимающее значение одной из констант - одна для чёрного цвета, вторая - для красного. Однако, я считаю, что проще использовать флаг. Если он установлен, узел красный, если не установлен - чёрный. Естественно, можно и инвертировать значения, но в данной статье взведённый флаг будет обозначать красный цвет:

1 struct node {
2        int red;
3        int data;
4        struct node *link [2];
5 };
6
7 struct tree {
8        struct node *root;
9 };

Уверен, что если вы не читали прежде прочие мои статьи о деревьях, то массив ссылок будет вас путать. Вместо использования двух указателей - левого и правого, как это делается обычно, я предпочитаю использовать массив, где элемент с индексом 0 содержит левый указатель, а элемент с индексом 1 - правый указатель. Это облегчает задачу объединения симметричных случаев и сокращает код, гарантируя корректность. Это моя личная идиома и насколько мне известно, только я использую её для объединения симметричных случаев. Чтобы свести шок к минимуму, ниже показана разница между "классической" идиомой и моей собственной:

1 /* Classic binary search tree insertion */
2 struct cbt_node *cbt_insert (struct cbt_node *root, int data)
3 {
4         if (root == NULL)
5                 root = make_node (data);
6         else if (data < root->data)
7                 root->left = cbt_insert (root->left, data);
8         else
9                 root->right = cbt_insert (root->right, data);
10
11        return root;
12 }
13
14 /* Julienne Walker's binary search tree insertion */
15 struct node *insert (struct node *root, int data)
16 {
17         if (root == NULL)
18                 root = make_node (data);
19         else {
20                 int dir = root->data < data;
21                 root->link [dir] = insert (root->link [dir], data);
22         }
23
24         return root;
25 }

Пока что здесь вроде не видно экономии кода, но если вы добавите 50 строк кода перебалансировки для обоих случаев - левого и правого направления, то легко увидеть, что классическая вставка требует дополнительных 100 строк кода, однако мой код для операции вставки умещается всего в 50 строк, потому что оба симметричных случая объединены в один. В реализации алгоритма результатом этого объединения является использование флага dir, который указывает направление, по которому мы работаем, а !dir - противоположное направление. Когда вы поймёте эту идиому, чтение кода, использующего его перестанет быть трудным.

Вернёмся обратно к нашему каркасу. Чтобы не захламлять код дополнительными проверками, му будем использовать небольшую вспомогательную функцию, которая будет определять, что цвет узла красный. Чтобы облегчить жизнь, мы будем исходить из предположения, что лист чёрный, потому что наши листья - указатели на NULL, а попытки исправить красное нарушение с NULL-указателями способны свести с ума :-)

1 int is_red (struct node *root)
2 {
3         return root != NULL && root->red == 1;
4 }

Наконец, вращение. Любая схема балансировки дерева использует вращения, чтобы изменить структуру дерева без нарушения правил, действующих для бинарных деревьев поиска. Также в этом случае было бы логично использовать перекраску узлов, когда они вращаются. Одиночный поворот в красно-чёрном дереве просто поворачивает узлы, как обычно, затем "окрашивает" старую вершину в красный цвет, а новую - в чёрный. Двойной поворот это просто два одиночных поворота. Этого достаточно для операции вставки, но с удалением всё сложнее (какой шок). Несмотря на это, перекраска может быть полезной нам и при вращениях в алгоритме операции удаления. Мы добавим перекраску в функцию одинарного поворота, а функция двойного поворота будет использовать перекраску не явно:

1 struct node *rot_single (struct node *root, int dir)
2 {
3         struct node *save = root->link [!dir];
4
5         root->link [!dir] = save->link [dir];
6         save->link [dir] = root;
7
8         root->red = 1;
9         save->red = 0;
10
11        return save;
12 }
13
14 struct node *rot_double (struct node *root, int dir)
15 {
16        root->link [!dir] = rot_single (root->link [!dir], !dir);
17        return rot_single (root, dir);
18 }

Не волнуйтесь, мы не будем заниматься вставкой прямо сейчас. Сбалансированные деревья нетривиальная структура данных, а красно-чёрные деревья на этом фоне выглядят исключительно хитро для правильного понимания, потому что даже небольшое изменение в одной части дерева может привести к нарушениям в дальних его частях. Т.о., есть смысл ввести небольшую функцию для верификации, которая будет проверять, не было ли нарушений. Зачем? Может так статься, что алгоритм работает на небольших деревьях, но ломается на крупных и вы не знаете, почему. Используя такую функцию, мы можем быть уверены, что алгоритм работает, если мы нагрузим его достаточным объёмом данных в достаточно большом дереве (слишком большом, чтобы тестировать его вручную). Т.к. эта функция будет использоваться только для отладки, мы можем применить рекурсию и допустить, чтобы наш тестер был медленным:

1 int rb_assert (struct node *root)
2 {
3        int lh, rh;
4
5        if (root == NULL)
6               return 1;
7        else {
8               struct node *ln = root->link [0];
9               struct node *rn = root->link [1];
10
11              /* Consecutive red links */
12              if (is_red (root)) {
13                     if (is_red (ln) || is_red (rn)) {
14                            puts ("Red violation");
15                            return 0;
16                     }
17              }
18
19              lh = rb_assert (ln);
20              rh = rb_assert (rn);
21
22              /* Invalid binary search tree */
23              if ((ln != NULL && ln->data >= root->data)
24                     || (rn != NULL && rn->data <= root->data))
25              {
26                     puts ("Binary tree violation");
27                     return 0;
28              }
29
30              /* Black height mismatch */
31              if (lh != 0 && rh != 0 && lh != rh) {
32                     puts ("Black violation");
33                     return 0;
34              }
35
36              /* Only count black links */
37              if (lh != 0 && rh != 0)
38                     return is_red (root) ? lh : lh + 1;
39              else
40                     return 0;
41       }
42 }

Этот алгоритм относительно прост. Он совершает обход каждого узла в дереве и проводит различные проверки на самом узле и его потомках. Первое - проверка, имеет ли красный узел красные дочерние узлы. Второе - проверка, что дерево является валидным двоичным деревом поиска. И последнее - подсчёт чёрных узлов в пути, а также проверка на предмет того, что все пути имеют такую же длину - чёрную высоту. В случае, если rb_assert() возвращает 0, наше дерево не является корректно построенным красно-чёрным деревом. В противном случае функция вернёт чёрную высоту всего дерева. Для удобства будет выведено сообщение, поясняющее, какое именно нарушение произошло. :-)

Теперь мы готовы перейти к вставке! Засучите рукава и приготовьтесь повозиться.

Вставка снизу вверх [наверх]

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

Но подождите! Если новый узел красный и он будет добавлен, как дочерний узел чёрного узла, мы избежим нарушений вообще в то время, как при вставке чёрного узла в качестве дочернего узла по отношению к чёрному узлу нарушение будет происходить всегда. Т.о., логически наш выбор - окрашивать новый узел в красный цвет, потому что это даст нам возможность не нарушать правила формирования дерева. Нельзя сказать того же о вставке чёрного узла. Красные нарушения более локализованы и поэтому из проще устранять. По этой причине мы будет окрашивать новые узлы в красный цвет и исправлять красные нарушения во время операции вставки. Лень побеждает! Как насчёт вспомогательной функции, которая будет возвращать новый красный узел?

 1 struct node *make_node (int data)
 2 {
 3       struct node *rn = malloc (sizeof *rn);
 4 
 5       if (rn != NULL) {
 6             rn->data = data;
 7             rn->red = 1; /* 1 is red, 0 is black */
 8             rn->link [0] = NULL;
 9             rn->link [1] = NULL;
10       }
11 
12       return rn;
13 }

Ах, наконец и вставка. Добавление узла. Вместо того, чтобы красиво рассказывать о красно-чёрных деревьях мы можем уже поиграть с чем-то реальным. Хорошо, давайте вставим новый узел в базовое бинарное дерево поиска - это первое дело в нашей повестке. Затем мы можем пройти обратно вверх и перебалансировать дерево, если у нас возникло красное нарушение. Для простоты в коде вставки мы будем использовать рекурсию с запретом дубликатов. Не забудьте отметить последнюю часть кода, которая красит вершину в чёрный цвет. Это важный момент, потому что он гарантирует ненарушение последнего правила красно-чёрного дерева и позволяет избежать необходимости иметь дело с красными нарушениями на вершине. Код должен быть ясен. Если нет, вам стоит познакомиться с бинарными деревьями поиска.

 1 struct node *insert_r (struct node *root, int data)
 2 {
 3       if (root == NULL)
 4             root = make_node (data);
 5       else if (data != root->data) {
 6             int dir = root->data < data;
 7 
 8             root->link [dir] = insert_r (root->link [dir], data);
 9 
10             /* Hey, let's rebalance here! */
11       }
12 
13       return root;
14 }
15 
16 int insert (struct tree *tree, int data)
17 {
18       tree->root = insert_r (tree->root, data);
19       tree->root->red = 0;
20       return 1;
21 }

Этот код настолько прост, насколько это вообще возможно в случае бинарных деревьев, но мы знаем, что вставка может потребовать перебалансировки дерева снизу вверх, естественно, после рекурсивного вызова должен идти код перебалансировки. Помните те занятия по программированию, где надо было вывести введённую последовательность чисел в обратном порядке, используя рекурсию? Тот же принцип применим и здесь. Мы рекурсивно вызываем функцию, вниз, вниз, вниз (вниз! сесть! встать!), а затем вставляем новый узел, присоединяя его к первому листу, до кторого добираемся (потому что второй лист, до которого мы доберёмся, вероятно вызовет ошибку сегментации (SEGFAULT)). Затем рекурсия раскучивается вспять и мы можем извлечь из этого пользу для себя.

Итак, как нам провести проверку на красное нарушение? Очень просто: если какой-то из узлов на пути красный, проверим есть ли у него красные дочерние узлы - первый и второй. Если это так, исправляем. Обратите внимание, что только один дочерний узел будет красным. Если иначе, что-то ещё не так с нашим деревом, потому что таким образом красное нарушение будет присутствовать всегда и дерево не будет правильным красно-чёрным деревом. Однако, мы предположим, что дерево построено правильно, потому что так проще.

Хорошо, как нам устранить красное нарушение? Это тоже просто! Здесь возможны лишь три случая и все они просты. В первом случае мы проверяем оба дочерних узла (запомните, мы не проверяем новые узлы). Если оба дочерних узла красные, родительский узел должен быть чёрным, так что нам достаточно просто перевернуть цвета. Родительский узел становится красным, а дочерние узлы - чёрными:

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

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

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

Да, хорошая догадка, это дерево не является валидным красно-чёрным деревом. Почему? Потому что значения чёрной высоты в двух поддеревьях не одинаковы. То, с чем мы здесь столкнулись - чёрное нарушение! Хорошая новость - это никогда не произойдёт. Данный пример был призван лишь продемонстрировать, как работает поворот дерева, не рисуя большого дерева, но именно в точности такое дерево никогда не будет существовать в реальных условиях. Почему? Потому что было чёрное нарушение до вставки узла 0! На самом деле, первое вращение красно-чёрного дерева, состоящего из убывающей последовательности чисел произошло бы только после седьмого числа. Давайте посмотрим на этот случай после вставки 7:

На данном этапе будет проделано переворачивание цвета, потому что 5, 4 и 6 попадают под упомянутый выше первый случай. Переворачивание цветов может вызвать красное нарушение выше, поэтому мы поднимаемся до узла 3 и видим, что на узле 3 у нас действительно красное нарушение. Теперь применим случай с одиночным поворотом. Посмотрим, что произошло с нашим деревом перед вращением:

Самое важное, что стоит сейчас отметить, это то, что НЕТ чёрного нарушения! Каждый путь имеет по два чёрных узла и единственное нарушение - красное нарушение на узле 3. Когда мы делаем поворот вокруг узла 1, узел 3 становится новым чёрным корнем, а узел 1 становится красным. Дерево выглядит, как показано ниже. Заметьте, нет красных нарушений и все чёрные высоты одинаковы. Так работает случай с одним поворотом:

Теперь довольно легко понять, почему функция rot_single() устанавливает цвет именно так, как она это делает. Наконец случай, когда вместо левого красного дочернего узла красным является правый дочерний узел. Если правый дочерний узел красный, то одинарный поворот здесь не поможет. Это тот случай, когда нужен двойной поворот:

Стойте, стойте, стойте! Средний шаг верен, так? Так почему бы нам просто не сделать единичный поворот? Это ещё один пример, который не будет существовать в реальных условиях, как показано. Заметьте, что первый поворот увеличивает чёрную высоту поддерева левого по отношению к узлу 3. Это могло привести к чёрному нарушению, так что мы продолжаем двойное вращение, чтобы избежать этого. Попробуйте смоделировать такое правильно построенное красно-чёрное дерево, где этот случай имел бы место и убедитесь, что вращение работает так, как мы проделали выше.

Мы рассмотрели три случая, а теперь дополним наш код, чтобы он выявлял описанные случаи и мог исправлять подобные ситуации. Запомните, что новые узлы никогда не перебалансируют дерево; алгоритм просто возвращает новый узел, когда достигается лист и листья перебалансируются до уровня верхних узлов. Мы убеждаемся, что если имеет место нарушение, то оно локализовано в поддереве. Т.о., мы можем провести вращения не устанавливая флаг статуса, который предписывает алгоритму продолжать вращения далее по восходящей. На самом деле флаг статуса не нужен вовсе! Возможно переворачивать цвета на обратном пути вверх по дереву даже если может быть сделан одинарный или двойной поворот:

 1 struct node *insert_r (struct node *root, int data)
 2 {
 3       if (root == NULL)
 4             root = make_node (data);
 5       else if (data != root->data) {
 6             int dir = root->data < data;
 7
 8             root->link [dir] = insert_r (root->link [dir], data);
 9
10             if (is_red (root->link [dir])) {
11                   if (is_red (root->link [!dir])) {
12                         /* Case 1 */
13                         root->red = 1;
14                         root->link [0]->red = 0;
15                         root->link [1]->red = 0;
16                   }
17                   else {
18                         /* Cases 2 & 3 */
19                         if (is_red (root->link [dir]->link [dir]))
20                               root = rot_single (root, !dir );
21                         else if (is_red (root->link [dir]->link [!dir]))
22                               root = rot_double (root, !dir);
23                   }
24             }
25       }
26
27       return root;
28 }
29
30 int insert (struct tree *tree, int data)
31 {
32       tree->root = insert_r (tree->root, data);
33       tree->root->red = 0;
34       return 1;
35 }

Просто, элегантно, это и есть вставка снизу вверх в красно-чёрном дереве! Я советую вам пройтись по примеру, который покрывает все описанные случаи, чтобы убедиться, что это работает. Конечно, у вас есть вспомогательная функция для тестирования, но ведь вы не знаете, вдруг я просто дурачу ваc? Вы узнаете об этом, когда поэкспериментируете на приблизительно 30 случайных числах и оттрассируете вашу программу!

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

Удаление снизу вверх [наверх]

Удаление узла из красно-чёрного дерева может послужить причиной сильной боли ниже спины. Это и моё официальное мнение. Я ненавижу эту операцию и научу вас ненавидеть её. В особенности, алгоритм удаления снизу вверх. В особенности, первый способ, который я собираюсь описать :-)

При вставке у нас была возможность выбирать цвет нового узла, чтобы сделать жизнь проще. Мы могли спровоцировать красное нарушение и тут же исправить его. Красные нарушения легко исправить и мы пользовались этим обстоятельством себе на пользу, чтобы создать элегантный рекурсивный алгоритм. Когда вы удаляете узел, у вас нет выбора и вы не можете манипулировать цветами. Если цвет узла красный - превосходно! Красные узлы удаляются без каких-либо нарушений. Почему? Ну, по крайней мере, я не вижу способа внести красное нарушение удалением красного узла из верно построенного дерева, но вы можете попытаться найти такой способ. Т.к. красные узлы не участвуют в формировании чёрной высоты, удаление красного узла не влияет на чёрную высоту. Следовательно, удаление красного узла не нарушает правила формирования красно-чёрного дерева.

Если узел чёрный, у нас проблема. Удаление чёрного узла наверняка спровоцирует чёрное нарушение, равно как и вставка чёрного узла. Это то обстоятельство, которого мы и пытаемся избежать при вставке, кроме того, весьма вероятно, что это послужит причиной и красного нарушения! Хорошо, давайте сначала удалим узел, а потом подумаем, как устранить нарушения. Ниже показан простой алгоритм рекурсивного удаления узла из чёрно-красного дерева. Если у узла, которой мы собираемся удалить меньше двух дочерних узлов, мы просто заменяем этот узел тем его потомком, который не равен NULL, или просто NULL-указателем, если у этого узла нет дочерних узлов.

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

Если у узла два потомка, мы находим такой узел, значение которого предшествуют значению данного узла - младший узел, (т.е., для узла 3 на диаграмме ниже таким узлом будет 2 - перев.) и копируем его данные в наш узел. Затем мы рекурсивно удаляем младший узел, т.к. у него гарантированно по меньшей мере будет один дочерний узел. В целом, наш алгоритм выглядит довольно неплохо, даже с добавлением кода для перебалансировки (простая перекраска после удаления, флаг статуса и загадочная функция remove_balance ()). Заметьте, что корень окрашивается в чёрный цвет под конец, если дерево не пустое:

 1 struct node *remove_r (struct node *root, int data, int *done)
 2 {
 3       if (root == NULL)
 4             *done = 1;
 5       else {
 6             int dir;
 7
 8             if (root->data == data) {
 9                   if (root->link [0] == NULL || root->link [1] == NULL) {
10                         struct node *save =
11                               root->link [root->link [0] == NULL];
12
13                         /* Case 0 */
14                         if (is_red (root))
15                               *done = 1;
16                         else if (is_red (save)) {
17                               save->red = 0;
18                               *done = 1;
19                         }
20
21                         free (root);
22
23                         return save;
24                   }
25                   else {
26                         struct node *heir = root->link [0];
27
28                         while (heir->link [1] != NULL)
29                               heir = heir->link [1];
30
31                         root->data = heir->data;
32                         data = heir->data;
33                   }
34             }
35
36             dir = root->data < data;
37             root->link [dir] = remove_r (root->link [dir], data, done);
38
39             if (!*done)
40                   root = remove_balance (root, dir, done);
41       }
42
43       return root;
44 }
45 
46 int remove (struct tree *tree, int data)
47 {
48       int done = 0;
49
50       tree->root = remove_r (tree->root, data, &done);
51       if (tree->root != NULL)
52             tree->root->red = 0;
53
54       return 1;
55 }

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

Ясно, что реальная работа выполняется функцией remove_balance(), но что именно делает эта вспомогательная функция? Конечно же, она обрабатывает все те случаи, возникновение которых может стать результатом удаление чёрного узла! И эта функция почти такая же по объёму кода, как remove_r(). :-( Давайте сначала рассмотрим простые случаи. Если мы удаляем узел и его сосед - чёрный, а его дочерние узлы также оба чёрные, мы имеем дело с простым случаем, который распространяется (на схеме * = удалённое место):

В этом случае мы можем просто перекрасить узел 1 (соседний узел) в красный цвет без внесения красного нарушения, но всё ещё существует вероятность чёрного нарушения, потому что мы уменьшили чёрную высоту левого поддерева узла 3. Это приводит к тому, что оба поддерева узла 3 будут иметь одну и ту же чёрную высоту, но если узел 3 сам является частью поддерева, то с точки зрения родительского узла возникнет чёрное нарушение, потому что чёрная высота соседнего поддерева не уменьшилась. Однако, если родительский узел (3 в нашем случае) изначально был красным, мы можем перекрасить соседний узел в красный цвет, родителя - в чёрный и дело сделано, потому что теперь чёрные высоты сбалансированы на всём восходящем по дереву пути. Для этого мы можем взвести флаг:

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

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

И всего-то! Но у меня плохие новости для вас. Это были только те случаи, когда соседний узел чёрный. Если сосед красный, всё гораздо хуже. Однако есть и хорошие новости. Дальнейшие рассуждения представляют собой больше теоретический интерес. Вскоре мы научимся полностью избегать случая с красным соседом. Сделайте глубокий вдох и приготовьтесь ко второй половине повествования о случаях перебалансировки при удалении.

Готовы? Каждый случай с красным соседом требует по меньшей мере одного поворота, но не более трёх. Но сначала простые случаи. Если сосед красный и оба его дочерних узла чёрные, для восстановления баланса нам нужно сделать один поворот, перекрасить нового родителя в чёрный цвет, правый дочерний узел соседа - в красный. Запомните, при том, что описание и диаграммы иллюстрируют удаление из правого поддерева, случаи симметричны и при применении трюка с индексами направления мы обрабатываем один из таких симметричных случаев (где dir будет равен 1). Это должно быть ясно при взгляде на код:

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

Это позволяет восстановить чёрную высоту правого поддерева без изменения чёрной высоты левого поддерева. Когда у нас два красных узла, легко один из них сделать чёрным после поворота, а второй оставить, как есть, чтобы избежать нарушения чёрной высоты поддерева, из которого мы и взяли узел. Последний случай, когда правый дочерний узел узла 3 - красный. Хорошие новости в том, что мы можем свести этот случай к предыдущему одиночным поворотом на узле 2, а затем - двойной поворот на узле 5 (предыдущий случай) даст нам ту структуру, которая нам и нужна с такими же цветами, как выше.

Прежде, чем вы начнёте размышлять, что за мешанина должна быть в коде remove_balance(), давайте посмотрим на неё и убедимся, что всё не так уж и плохо. Да, функция длинная, но ни один из случаев не усложняет её до предела. Экономия получена из сходства разных случаев и назначения цветов вне кода их обработки, с целью избежать повторов кода, но мы можем сделать ещё лучше, как вы скоро увидите. Сравните случаи, описанные выше с их обработкой в исходном коде. Все ли случаи здесь обрабатываются?

 1 struct node *remove_balance (struct node *root, int dir, int *done)
 2 {
 3       struct node *p = root;
 4       struct node *s = root->link [!dir];
 5
 6       if (s != NULL && !is_red (s)) {
 7             /* Black sibling cases */
 8             if (!is_red (s->link [0]) && !is_red (s->link [1])) {
 9                   if (is_red (p))
10                         *done = 1;
11                   p->red = 0;
12                   s->red = 1;
13             }
14             else {
15                   int save = root->red;
16
17                   if (is_red (s->link [!dir]))
18                         p = rot_single (p, dir);
19                   else
20                         p = rot_double (p, dir);
21
22                   p->red = save;
23                   p->link [0]->red = 0;
24                   p->link [1]->red = 0;
25                   *done = 1;
26             }
27       }
28       else if (s->link [dir] != NULL) {
29             /* Red sibling cases */
30             struct node *r = s->link [dir];
31
32             if (!is_red (r->link [0]) && !is_red (r->link [1])) {
33                   p = rot_single (p, dir);
34                   p->link [dir]->link [!dir]->red = 1;
35             }
36             else {
37                   if (is_red (r->link [dir]))
38                         s->link [dir] = rot_single (r, !dir);
39                   p = rot_double (p, dir);
40                   s->link [dir]->red = 0;
41                   p->link [!dir]->red = 1;
42             }
43
44             p->red = 0;
45             p->link [dir]->red = 0;
46             *done = 1;
47       }
48
49       return p;
50 }

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

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

 1 struct node *remove_balance (struct node *root, int dir, int *done)
 2 {
 3       struct node *p = root;
 4       struct node *s = root->link [!dir];
 5
 6       /* Case reduction, remove red sibling */
 7       if (is_red (s)) {
 8             root = rot_single (root, dir);
 9             s = p->link [!dir];
10       }
11
12       if (s != NULL) {
13             if (!is_red (s->link [0]) && !is_red (s->link [1])) {
14                   if (is_red (p))
15                         *done = 1;
16                   p->red = 0;
17                   s->red = 1;
18             }
19             else {
20                   int save = p->red;
21                   int new_root = (root == p);
22
23                   if (is_red (s->link [!dir]))
24                         p = rot_single (p, dir);
25                   else
26                         p = rot_double (p, dir);
27
28                   p->red = save;
29                   p->link [0]->red = 0;
30                   p->link [1]->red = 0;
31
32                   if (new_root)
33                         root = p;
34                   else
35                         root->link [dir] = p;
36
37                   *done = 1;
38             }
39       }
40
41       return root;
42 }

Перемещения root и p могут запутать, но единственно, чем здесь можно помочь - трассировка выполнения кода, чтобы быть уверенным в понимании почему root и p используются там, где они используются. Помните, я говорил, что сокращение случая запутано (возможно потому, что никто не берёт на себя труд объяснить это), но такое сокращение значительно упрощает код, потому что половину кода, выполняющего нужную нам работу по перебалансировке, можно выкинуть.

Вставка сверху вниз [наверх]

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

Ключевая идея, которую вы должны извлечь из этой статьи - то, что правила одинаковы, вне зависимости, как вы их реализуете. Мы по прежнему имеем дело с тремя случаями при вставке узла в красно-чёрное дерево: отражение цветов, одинарный и двойной поворот. Всё остальное - это каркас и детали. Для вставки сверху вниз рекурсия не даёт выигрыша. Чтобы обойтись без неё, нам необходимо аккуратно сохранять различные указатели, которые выведут нас обратно вверх по дереву. По крайней мере, у нас есть текущий узел в пути (в конце пути - указатель на NULL), его родительский узел и родитель родителя.

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

В случае с заменой цветов (color flip) мы проверяем дочерние узлы текущего узла. Если они красные, то текущий узел должен быть чёрным и мы проводим замену цвета. Это может вызвать красное нарушение далее вверх по дереву (вот почему мы сохранили указатель на родителя текущего узла). Теперь учитывая то, что замена цветов сразу приведёт к нарушению, мы прямиком приступаем к проверке нарушений между родительским узлом и текущим. Если оба красные, мы совершаем одинарный или двойной поворот вокруг дедовского узла:

Обратите внимание, как происходит вращение вокруг дедовского узла. Исходя из этих особенностей мы и сохраняем указатель на родителя дедовского узла. В противном случае было бы куда сложнее "оповестить" дерево о тех изменениях, которые мы вносим. Код, который творит всё волшебство короче, чем вы могли бы ожидать, но он не следует обычным методикам. Вся работа проделывается в цикле при нисхождении, включая также операцию вставки, т.к. вставка нового красного узла может вызвать красное нарушение. Цикл разрывается, если найдены данные или вставлен новый узел или в случае, если в дереве уже был узел с такими данными. Т.о., алгоритм, представленный ниже не допускает дубликаты и не предупреждает о них:

 1 int insert (struct tree *tree, int data)
 2 {
 3       if (tree->root == NULL) {
 4             /* Empty tree case */
 5             tree->root = make_node (data);
 6             if (tree->root == NULL)
 7                   return 0;
 8       }
 9       else {
10             struct node head = { 0 }; /* False tree root */
11
12             struct node *g, *t;     /* Grandparent & parent */
13             struct node *p, *q;     /* Iterator & parent */
14             int dir = 0, last;
15
16             /* Set up helpers */
17             t = &head;
18             g = p = NULL;
19             q = t->link [1] = tree->root;
20
21             /* Search down the tree */
22             for ( ; ; ) {
23                   if (q == NULL) {
24                         /* Insert new node at the bottom */
25                         p->link [dir] = q = make_node (data);
26                         if (q == NULL)
27                               return 0;
28                   }
29                   else if (is_red (q-> link [0]) && is_red (q->link [1])) {
30                         /* Color flip */
31                         q->red = 1;
32                         q->link [0]->red = 0;
33                         q->link [1]->red = 0;
34                   }
35
36                   /* Fix red violation */
37                   if (is_red (q) && is_red (p)) {
38                         int dir2 = t->link [1] == g;
39
40                         if (q == p->link [last])
41                               t->link [dir2] = rot_single (g, !last);
42                         else
43                               t->link [dir2] = rot_double (g, !last);
44                   }
45
46                   /* Stop if found */
47                   if (q->data == data)
48                         break;
49
50                   last = dir;
51                   dir = q->data < data;
52
53                   /* Update helpers */
54                   if (g != NULL)
55                         t = g;
56                   g = p, p = q;
57                   q = q->link [dir];
58             }
59
60             /* Update root */
61             tree->root = head.link [1];
62       }
63
64       /* Make root black */
65       tree->root->red = 0;
66
67       return 1;
68 }

Такая вставка сверху вниз не столь красива, как рекурсивная вставка снизу вверх, однако алгоритм использует все преимущества, предоставляемые свойствами красно-чёрных деревьев и избегает потенциальных проблем рекурсивного алгоритма. Теоретически этот алгоритм более эффективен. :-) Хорошая новость: удаление сверху вниз проще, чем снизу вверх, и мы можем использовать уроки, извлечённые из изучения алгоритма вставки, чтобы сделать нашу реализацию проще. Давайте посмотрим.

Удаление сверху вниз [наверх]

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

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

В принципе, это обратное отражение цветов (reverse color flip), которое мы делали во время вставки. Это сдвигает красные узлы вниз без изменения чёрной высоты дерева, вместо того, чтобы удерживать их наверху. Здорово. :-) Следующий случай - случай с красным соседом, который мы быстро сократим спомощью одинарного поворота, используя трюки, которые мы изучили на примере удаления снизу вверх. Этот случай довольно интуитивен теперь, когда нам не нужно менять направление, чтобы всё работало. Заметьте, что ни чёрная высота, ни цвет родительского узла не изменяются. Т.к. мы двигаемся вниз, сдвигание и соседних узлов вниз - то, что нужно:

И наконец, как вы наверно догадались, два случая - одиночный и двойной поровот в зависимости от цвета дочерних узлов соседа. Эти случаи вам уже знакомы (должны быть!), поэтому мы лишь вкратце по ним пройдёмся, прежде чем перейдём к коду. Если правый дочерний узел красный, мы делаем двойной поворот. Однако, в этом случае изменением цвета в rot_single() дело не ограничивается. Для пущей аккуратности мы форсируем правильный цвет во всех затронутых узлах:

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

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

 1 int remove (struct tree *tree, int data)
 2 {
 3       if (tree->root != NULL) {
 4             struct node head = { 0 }; /* False tree root */
 5             struct node *q, *p, *g; /* Helpers */
 6             struct node *f = NULL;  /* Found item */
 7             int dir = 1;
 8
 9             /* Set up helpers */
10             q = &head;
11             g = p = NULL;
12             q->link [1] = tree->root;
13
14             /* Search and push a red down */
15             while (q->link [dir] != NULL) {
16                   int last = dir;
17
18                   /* Update helpers */
19                   g = p, p = q;
20                   q = q->link [dir];
21                   dir = q->data < data;
22
23                   /* Save found node */
24                   if (q->data == data)
25                         f = q;
26
27                   /* Push the red node down */
28                   if (!is_red (q) && !is_red (q->link [dir])) {
29                         if (is_red (q->link [!dir]))
30                               p = p->link [last] = rot_single (q, dir);
31                         else if (!is_red (q->link [!dir])) {
32                               struct node *s = p->link [!last];
33
34                               if (s != NULL) {
35                                     if (!is_red (s->link [!last]) && !is_red (s->link [last])) {
36                                           /* Color flip */
37                                           p->red = 0;
38                                           s->red = 1;
39                                           q->red = 1;
40                                     }
41                                     else {
42                                           int dir2 = g->link [1] == p;
43
44                                           if (is_red (s->link [last]))
45                                                 g->link [dir2] = rot_double (p, last);
46                                           else if (is_red (s->link [!last]))
47                                                 g->link [dir2] = rot_single (p, last);
48
49                                           /* Ensure correct coloring */
50                                           q->red = g->link [dir2]->red = 1;
51                                           g->link [dir2]->link [0]->red = 0;
52                                           g->link [dir2]->link [1]->red = 0;
53                                     }
54                               }
55                         }
56                   }
57             }
58
59             /* Replace and remove if found */
60             if (f != NULL) {
61                   f->data = q->data;
62                   p->link [p->link [1] == q] =
63                         q->link [q->link [0] == NULL];
64                   free (q);
65             }
66
67             /* Update root and make it black */
68             tree->root = head.link [1];
69             if (tree->root != NULL)
70                   tree->root->red = 0;
71       }
72
73       return 1;
74 }

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

Это и есть удаление сверху вниз и его можно сравнить с удалением снизу вверх, так же, как и вставку, но теперь мы можем судить о том, что код операции удаления сверху вниз короче и (я думаю) проще. Красно-чёрные деревья проще поддаются пониманию при использовании алгоритмов, работающих сверху вниз, но к сожалению на фоне того, что единственный широко известный источник, который даёт код для операции удаления - это CLR, большая часть реализаций использует алгоритмы, работающие снизу вверх. Ну, ладно.

Заключение [наверх]

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

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

Красно-чёрные деревья популярны, как и большинство структур данных с причудливыми названиями. Например в Java и C++ библиотечные структуры отображения (map) обычно реализуются, как красно-чёрные деревья. По скорости красно-чёрные деревья сравнимы с AVL-деревьями. Хотя, сбалансированность их не так высока, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Есть определённые неправильные представления о красно-чёрных деревьях, но в целом, их слава оправдана.

В этой статье описана красно-чёрная абстракция, используемая для балансировки бинарного дерева поиска. Рассмотрены обе операции - вставка и удаление, работающие как сверху вниз, так и снизу вверх, приведены реализации каждой из них. Чтобы получить больше информации по красно-чёрным деревьям, поищите описание библиотеки libavl в превосходной онлайн-книге Бена Пфаффа (если бы она была у меня, когда я ломал голову над тем, что описано выше!) или обзаведитесь книгой “Введение в алгоритмы” Кормена, Лейзерсона и Ривеста.

1 comment:

Anonymous said...

ошибка в функции не рекурсивного удаления, dir = q->data < data; тут нужно направление инвертировать

ПОСЕТИТЕЛИ

free counters