Красно-чёрное дерево (, ) — один из видов самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимбаса и Р. Седжвика (1978). По словам Гимбаса, они использовали ручки двух цветов. По словам Седжвика, красный цвет лучше всех смотрелся на лазерном принтереКурс «Algorithms: Design and Analysis, Part 1», лекция «Red-Black Trees» (Видео 5:07).
Красно-чёрное дерево используется для организации сравнимых данных, таких как фрагменты текста или числа. Листовые узлы красно-чёрных деревьев не содержат данных, благодаря чему не требуют выделения памяти — достаточно записать в узле-предке в качестве указателя на потомка нулевой указатель. Однако в некоторых реализациях для упрощения алгоритма могут использоваться явные листовые узлы.
Принцип организации
Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвета. При этом:
Узел может быть либо красным, либо чёрным и имеет двух потомков; Корень — как правило чёрный. Это правило слабо влияет на работоспособность модели, так как цвет корня всегда можно изменить с чёрного на красный; Все листья, не содержащие данных — чёрные. Оба потомка каждого красного узла — чёрные. Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов.
Благодаря этим ограничениям путь от корня до самого дальнего листа не более чем вдвое длиннее, чем до самого ближнего, и дерево примерно сбалансировано. Операции вставки, удаления и поиска требуют в худшем случае времени, пропорционального длине дерева, что позволяет красно-чёрным деревьям в худшем случае быть более эффективными, чем обычные двоичные деревья поиска.
Чтобы понять, как это работает, достаточно рассмотреть эффект свойств 4 и 5 вместе. Пусть для красно-чёрного дерева T число чёрных узлов от корня до листа равно B. Тогда кратчайший возможный путь до любого листа содержит B узлов и все они чёрные. Более длинный возможный путь может быть построен путём включения красных узлов. Однако, благодаря пункту 4 в дереве не может быть двух красных узлов подряд, а согласно пунктам 2 и 3, путь начинается и кончается чёрным узлом. Поэтому самый длинный возможный путь состоит из 2B-1 узлов, попеременно красных и чёрных.
Если разрешить нелистовому узлу иметь меньше двух потомков, а листовым — содержать данные, дерево сохраняет основные свойства, но алгоритмы работы с ним усложнятся. Поэтому в статье рассматриваются только «фиктивные листовые узлы», которые не содержат данных и просто служат для указания, где дерево заканчивается. Эти узлы могут быть опущены в некоторых иллюстрациях. Из пункта 5, также следует, что потомками красного узла могут быть либо два чёрных промежуточных узла, либо два чёрных листа, а с учётом пунктов 3 и 4 — что если у чёрного узла один из потомков — листовой узел, то вторым должен быть либо тоже листовой, либо вышеописанная конструкция из одного красного и двух листовых.
Также в литературе встречается трактовка, в которой в красный/чёрный цвета раскрашивают не сами узлы, а ведущие к ним рёбра — но это не имеет большого значения для понимания принципа его работы.
Аналогия с B-деревом с параметром 4
Красно-чёрное дерево схоже по структуре с B-деревом с параметром 4, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. В таком В-дереве каждый узел будет содержать только одно значение, соответствующее значению чёрного узла красно-чёрного дерева с необязательным значениями до и/или после него в том же узле, оба из которых соответствуют эквивалентным красным узлам красно-чёрного дерева.
Один из способов увидеть эту эквивалентность — «поднять» красные узлы в графическом представлении красно-чёрного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками чёрными узлами, образуя страницу. В В-дереве, или в модифицированном графическом представлении красно-чёрного дерева, у всех листовых узлов глубина одинаковая.
Этот тип В-дерева является более общим, чем красно-чёрное дерево, хотя, как видно, из одного такого В-дерева с параметром 2 могут быть получены несколько красно-чёрных деревьев. Если страница В-дерева содержит только одно значение, данный узел чёрный и имеет двух потомков. Если страница содержит три значения, то центральный узел является чёрным, а каждый его сосед — красным. Однако, если страница содержит два значения, любой узел может стать чёрным в красно-чёрном дереве (и тогда второй будет красным).
Работа с красно-чёрными деревьями Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++Dr Dobbs — STL’s Red-Black Trees, класс TreeMap языка Java, так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.
Красно-чёрные деревья более популярны, чем идеально сбалансированные деревья, т.к. в последних может тратиться слишком много ресурсов на операции удаления из дерева и поддержание необходимой сбалансированности. После вставки или удаления требуется операция перекраски, требующая (O(log n) или O(1)) смен цветов (что на практике довольно быстро) и не более чем трёх поворотов дерева (для вставки — не более двух). Хотя вставка и удаление сложны, их трудоёмкость остается O(log n).
Вставка Новый узел в красно-чёрное дерево добавляется на место одного из листьев, окрашивается в красный цвет и к нему прикрепляется два листа (так как листья являются абстракцией, не содержащей данных, их добавление не требует дополнительной операции). Что происходит дальше, зависит от цвета близлежащих узлов. Заметим, что:
Свойство 3 (Все листья чёрные) выполняется всегда. Свойство 4 (Оба потомка любого красного узла — чёрные) может нарушиться только при добавлении красного узла, при перекрашивании чёрного узла в красный или при повороте. Свойство 5 (Все пути от любого узла до листовых узлов содержат одинаковое число чёрных узлов) может нарушиться только при добавлении чёрного узла, перекрашивании красного узла в чёрный (или наоборот), или при повороте.
Примечание: Буквой N будем обозначать текущий узел (окрашенный красным). Сначала это новый узел, который вставляется, но эта процедура может применяться рекурсивно к другим узлам (смотрите случай 3). P будем обозначать предка N, через G обозначим дедушку N, а U будем обозначать дядю (узел, имеющий общего родителя с узлом P). Отметим, что в некоторых случаях роли узлов могут меняться, но, в любом случае, каждое обозначение будет представлять тот же узел, что и в начале. Любой цвет, изображенный на рисунке, либо предполагается в данном случае, либо получается из других соображений. Каждый случай рассматривается с примерами кода на языке C. Определение структуры узла может выглядеть следующим образом:
enum node_colors { RED, BLACK };
struct node { struct node *parent, *left, *right; enum node_colors color; int key; };Дядя и дедушка текущего узла могут быть найдены с помощью функций:
struct node * grandparent(struct node *n) { if ((n != NULL) && (n->parent != NULL)) return n->parent->parent; else return NULL; }
struct node * uncle(struct node *n) { struct node *g = grandparent(n); if (g == NULL) return NULL; // No grandparent means no uncle if (n->parent == g->left) return g->right; else return g->left; }
Левый и правый поворот дерева может быть выполнен так:void rotate_left(struct node *n) { struct node *pivot = n->right;
pivot->parent = n->parent; /* при этом, возможно, pivot становится корнем дерева */ if (n->parent != NULL) { if (n->parent->left==n) n->parent->left = pivot; else n->parent->right = pivot;
n->right = pivot->left; if (pivot->left != NULL) pivot->left->parent = n;
n->parent = pivot; pivot->left = n; }
void rotate_right(struct node *n) { struct node *pivot = n->left;
pivot->parent = n->parent; /* при этом, возможно, pivot становится корнем дерева */ if (n->parent != NULL) { if (n->parent->left==n) n->parent->left = pivot; else n->parent->right = pivot;
n->left = pivot->right; if (pivot->right != NULL) pivot->right->parent = n;
n->parent = pivot; pivot->right = n; }Случай 1: Текущий узел N в корне дерева. В этом случае, он перекрашивается в чёрный цвет, чтобы оставить верным Свойство 2 (Корень — чёрный). Так как это действие добавляет один чёрный узел в каждый путь, Свойство 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число чёрных узлов) не нарушается.
void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n); }
Случай 2: Предок P текущего узла чёрный, то есть Свойство 4 (Оба потомка каждого красного узла — чёрные) не нарушается. В этом случае дерево остаётся корректным. Свойство 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число чёрных узлов) не нарушается, потому что текущий узел N имеет двух чёрных листовых потомков, но так как N является красным, путь до каждого из этих потомков содержит такое же число чёрных узлов, что и путь до чёрного листа, который был заменен текущим узлом, так что свойство остается верным.
void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n); }
Примечание: В следующих случаях предполагается, что у N есть дедушка G, так как его родитель P является красным, а если бы он был корнем, то был бы окрашен в чёрный цвет. Таким образом, N также имеет дядю U, хотя он может быть листовым узлом в случаях 4 и 5.
Случай 3: Если и родитель P, и дядя U — красные, то они оба могут быть перекрашены в чёрный, и дедушка G станет красным (для сохранения свойства 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число чёрных узлов)). Теперь у текущего красного узла N чёрный родитель. Так как любой путь через родителя или дядю должен проходить через дедушку, число чёрных узлов в этих путях не изменится. Однако, дедушка G теперь может нарушить свойства 2 (Корень — чёрный) или 4 (Оба потомка каждого красного узла — чёрные) (свойство 4 может быть нарушено, так как родитель G может быть красным). Чтобы это исправить, вся процедура рекурсивно выполняется на G из случая 1. void insert_case3(struct node *n) { struct node *u = uncle(n), *g;
if ((u != NULL) && (u->color == RED)) { // && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным. n->parent->color = BLACK; u->color = BLACK; g = grandparent(n); g->color = RED; insert_case1(g); } else { insert_case4(n);
Примечание: В оставшихся случаях предполагается, что родитель P является левым потомком своего предка. Если это не так, необходимо поменять лево и право. Примеры кода позаботятся об этом.