Красно-чёрное дерево

Красно-чёрное дерево (англ. red-black tree, RB tree) — один из видов самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».

Красно-чёрное дерево
Тип	дерево поиска
Год изобретения	1972
Автор	Рудольф Байер
Сложность в О-символике
В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n)
Медиафайлы на Викискладе

Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимбаса и Р. Седжвика (1978). По словам Гимбаса, они использовали ручки двух цветов^[1]. По словам Седжвика, красный цвет лучше всех смотрелся на лазерном принтере^[1][2].

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

Принцип организации

Пример красно-чёрного дерева

Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвета. При этом:

1. Узел может быть либо красным, либо чёрным и имеет двух потомков;
2. Корень — как правило чёрный. Это правило слабо влияет на работоспособность модели, так как цвет корня всегда можно изменить с чёрного на красный;
3. Все листья, не содержащие данных — чёрные.
4. Оба потомка каждого красного узла — чёрные.
5. Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов.

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

Чтобы понять, как это работает, достаточно рассмотреть эффект свойств 4 и 5 вместе. Пусть для красно-чёрного дерева T число чёрных узлов от корня до листа равно B. Тогда кратчайший возможный путь до любого листа содержит B узлов и все они чёрные. Более длинный возможный путь может быть построен путём включения красных узлов. Однако, благодаря пункту 4 в дереве не может быть двух красных узлов подряд, а согласно пунктам 2 и 3, путь начинается и кончается чёрным узлом. Поэтому самый длинный возможный путь состоит из 2B-1 узлов, попеременно красных и чёрных.

Если разрешить нелистовому узлу иметь меньше двух потомков, а листовым — содержать данные, дерево сохраняет основные свойства, но алгоритмы работы с ним усложнятся. Поэтому в статье рассматриваются только «фиктивные листовые узлы», которые не содержат данных и просто служат для указания, где дерево заканчивается. Эти узлы могут быть опущены в некоторых иллюстрациях. Из пункта 5, также следует, что потомками красного узла могут быть либо два чёрных промежуточных узла, либо два чёрных листа, а с учётом пунктов 3 и 4 — что если у чёрного узла один из потомков — листовой узел, то вторым должен быть либо тоже листовой, либо вышеописанная конструкция из одного красного и двух листовых.

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

Аналогия с B-деревом с параметром 4

То же самое красно-чёрное дерево, что и в примере выше, представленное как B-дерево.

Красно-чёрное дерево схоже по структуре с B-деревом с параметром 4, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. В таком В-дереве каждый узел будет содержать только одно значение, соответствующее значению чёрного узла красно-чёрного дерева с необязательным значениями до и/или после него в том же узле, оба из которых соответствуют эквивалентным красным узлам красно-чёрного дерева.

Один из способов увидеть эту эквивалентность — «поднять» красные узлы в графическом представлении красно-чёрного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками чёрными узлами, образуя страницу. В В-дереве, или в модифицированном графическом представлении красно-чёрного дерева, у всех листовых узлов глубина одинаковая.

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

Работа с красно-чёрными деревьями

Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++^[3], класс TreeMap языка Java^[4], так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.

Красно-чёрные деревья более популярны, чем идеально сбалансированные деревья, т.к. в последних может тратиться слишком много ресурсов на операции удаления из дерева и поддержание необходимой сбалансированности. После вставки или удаления требуется операция перекраски, требующая (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 Случай 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 является левым потомком своего предка. Если это не так, необходимо поменять лево и право. Примеры кода позаботятся об этом.

Схема случая 4 Случай 4: Родитель P является красным, но дядя U — чёрный. Также, текущий узел N — правый потомок P, а P в свою очередь — левый потомок своего предка G. В этом случае может быть произведен поворот дерева, который меняет роли текущего узла N и его предка P. Тогда, для бывшего родительского узла P в обновленной структуре используем случай 5, потому что Свойство 4 (Оба потомка любого красного узла — чёрные) все ещё нарушено. Вращение приводит к тому, что некоторые пути (в поддереве, обозначенном «1» на схеме) проходят через узел N, чего не было до этого. Это также приводит к тому, что некоторые пути (в поддереве, обозначенном «3») не проходят через узел P. Однако, оба эти узла являются красными, так что Свойство 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число чёрных узлов) не нарушается при вращении. Однако Свойство 4 всё ещё нарушается, но теперь задача сводится к Случаю 5.

void
insert_case4(struct node *n)
{
	struct node *g = grandparent(n);

	if ((n == n->parent->right) && (n->parent == g->left)) {
		rotate_left(n->parent);
		n = n->left;

		/*
		 * rotate_left может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
		 *
		 * struct node *saved_p=g->left, *saved_left_n=n->left;
		 * g->left=n; 
		 * n->left=saved_p;
		 * saved_p->right=saved_left_n;
		 * 
		 */
	} else if ((n == n->parent->left) && (n->parent == g->right)) {
		rotate_right(n->parent);
		n = n->right;

		/*
		 * rotate_right может быть выполнен следующим образом, учитывая что уже есть *g =  grandparent(n) 
		 *
		 * struct node *saved_p=g->right, *saved_right_n=n->right;
		 * g->right=n; 
		 * n->right=saved_p;
		 * saved_p->left=saved_right_n;
		 * 
		 */
	}
	insert_case5(n);
}

Схема случая 5 Случай 5: Родитель P является красным, но дядя U — чёрный, текущий узел N — левый потомок P и P — левый потомок G. В этом случае выполняется поворот дерева на G. В результате получается дерево, в котором бывший родитель P теперь является родителем и текущего узла N и бывшего дедушки G. Известно, что G — чёрный, так как его бывший потомок P не мог бы в противном случае быть красным (без нарушения Свойства 4). Тогда цвета P и G меняются и в результате дерево удовлетворяет Свойству 4 (Оба потомка любого красного узла — чёрные). Свойство 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число чёрных узлов) также остается верным, так как все пути, которые проходят через любой из этих трех узлов, ранее проходили через G, поэтому теперь они все проходят через P. В каждом случае, из этих трёх узлов только один окрашен в чёрный.

void
insert_case5(struct node *n)
{
	struct node *g = grandparent(n);

	n->parent->color = BLACK;
	g->color = RED;
	if ((n == n->parent->left) && (n->parent == g->left)) {
		rotate_right(g);
	} else {
		rotate_left(g);
	}
}

Удаление

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

Будем использовать обозначение M для удаляемого узла; через C обозначим потомка M, который также будем называть просто «его потомок». Если M имеет нелистового потомка, возьмем его за C. В противном случае за C возьмем любой из листовых потомков.

Если M является красным узлом, заменим его своим потомком C, который по определению должен быть чёрным. (Это может произойти только тогда, когда M имеет двух листовых потомков, потому что если красный узел M имеет чёрного нелистового потомка с одной стороны, а с другой стороны — листового, то число чёрных узлов на обеих сторонах будет различным, таким образом дерево станет недействительным красно-чёрным деревом из-за нарушения Свойства 5.) Все пути через удаляемый узел просто будут содержать на один красный узел меньше, предок и потомок удаляемого узла должны быть чёрными, так что Свойство 3 («Все листья — чёрные») и Свойство 4 («Оба потомка красного узла — чёрные») все ещё сохраняется.

Другим простым является случай, когда M — чёрный и C — красный. Простое удаление чёрного узла нарушит Свойство 4 («Оба потомка красного узла — чёрные») и Свойство 5 («Всякий простой путь от данного узла до любого листового узла, содержит одинаковое число чёрных узлов»), но если мы перекрасим С в чёрный, оба эти свойства сохранятся.

Сложным является случай, когда и M и C — чёрные. (Это может произойти только тогда, когда удаляется чёрный узел, который имеет два листовых потомка, потому что если чёрный узел M имеет чёрного нелистового потомка с одной стороны, а с другой — листового, то число чёрных узлов на обеих сторонах будет различным и дерево станет недействительным красно-чёрным деревом из-за нарушения Свойства 5.) Мы начнём с замены узла M своим потомком C. Будем называть этого потомка (в своем новом положении) N, а его «брата» (другого потомка его нового предка) — S. (До этого S был «братом» M.) На рисунках ниже мы также будем использовать обозначение P для нового предка N (старого предка M), S_L для левого потомка S и S_R для правого потомка S (S не может быть листовым узлом, так как если N по нашему предположению является чёрным, то поддерево P, которое содержит N, чёрной высоты два и поэтому другое поддерево P, которое содержит S должно быть также чёрной высоты два, что не может быть в случае, когда S — лист).

Примечание: В некоторых случаях мы меняем роли и обозначения узлов, но в каждом случае любое обозначение продолжает означать тот же узел, что и в начале случая. Любые цвета, изображенные на рисунке либо предполагаются случаем, либо получается из других предположений. Белый означает неизвестный цвет (либо красный, либо чёрный).

Будем искать «брата», используя эту функцию:

struct node *
sibling(struct node *n)
{
	if (n == n->parent->left)
		return n->parent->right;
	else
		return n->parent->left;
}

Примечание: Для того, чтобы дерево оставалось верно определенным, нам нужно, чтобы каждый лист оставался листом после всех преобразований (чтобы у него не было потомков). Если удаляемый нами узел имеет нелистового потомка N, легко видеть, что свойство выполняется. С другой стороны, если N — лист, то, как можно увидеть из рисунков или кода, свойство также выполняется.

Мы можем выполнить действия, описанные выше, используя следующий код, где функция replace_node ставит child на место узла n в дереве. Для удобства, код в этом разделе предполагает, что нулевые листья представлены реальными объектами узла, а не NULL (код вставки должен работать с таким же представлением).

void 
replace_node(node* n, node* child) {
    child->parent = n->parent;
    if (n == n->parent->left) {
        n->parent->left = child;
    } else {
        n->parent->right = child;
    }
}

void
delete_one_child(struct node *n)
{
	/*
	 * Условие: n имеет не более одного ненулевого потомка.
	 */
	struct node *child = is_leaf(n->right) ? n->left : n->right;
    
	replace_node(n, child);
	if (n->color == BLACK) {
		if (child->color == RED)
			child->color = BLACK;
		else
			delete_case1(child);
	}
	free(n);
}

Примечание: Если N является нулевым листом и мы не хотим представлять нулевые листы как реальные объекты, мы можем изменить алгоритм сначала вызывая delete_case1() на его отца (узел, который мы удалили, n в коде выше) и удаляя его после этого. Мы можем сделать это потому, что отец чёрный, и поэтому ведет себя так же как нулевой лист (и иногда называется 'phantom' лист). Мы можем безопасно удалить его так как n останется листом после всех операций, как показано выше.

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

Случай 1: N — новый корень. В этом случае, все сделано. Мы удалили один чёрный узел из каждого пути и новый корень является чёрным узлом, так что свойства сохранены.

void
delete_case1(struct node *n)
{
	if (n->parent != NULL)
		delete_case2(n);
}

Примечание: В случаях 2, 5, и 6 мы предполагаем, что N является левым потомком своего предка P. Если он — правый потомок, left и right нужно поменять местами во всех трех случаях. Опять-таки, примеры кода принимают это во внимание.

Диаграмма случая 2 Случай 2: S — красный. В этом случае мы меняем цвета P и S, и затем делаем вращение влево вокруг P, ставя S дедушкой N. Нужно заметить, что P должен быть чёрным, если он имеет красного потомка. Результирующее поддерево всё равно имеет черных узлов на единицу меньше, поэтому на этом мы ещё не закончили. Теперь N имеет чёрного брата и красного отца, поэтому мы можем перейти к шагу 4, 5 или 6. (Его новый брат является чёрным потому, что он был потомком красного S.) Далее через S будет обозначен новый брат N.

void delete_case2(struct node *n)
{
	struct node *s = sibling(n);

	if (s->color == RED) {
		n->parent->color = RED;
		s->color = BLACK;
		if (n == n->parent->left)
			rotate_left(n->parent);
		else
			rotate_right(n->parent);
	} 
	delete_case3(n);
}

Диаграмма случая 3 Случай 3: P, S, и дети S' — чёрные. В этом случае мы просто перекрашиваем S в красный. В результате все пути, проходящие через S, но не проходящие через N, имеют на один чёрный узел меньше. Так как удаление отца N приводит к тому, что все пути, проходящие через N, содержат на один чёрный узел меньше, то такие действия выравнивают баланс. Тем не менее, все проходящие через P пути теперь содержат на один чёрный узел меньше, чем пути, которые через P не проходят, поэтому свойство 5 (все пути из любой вершины к её листовым узлам содержат одинаковое количество чёрных узлов) все ещё нарушено. Чтобы это исправить, мы применяем процедуру перебалансировки к P, начиная со случая 1.

void delete_case3(struct node *n)
{
	struct node *s = sibling(n);

	if (
            (n->parent->color == BLACK) &&
	        (s->color == BLACK) &&
	        (s->left->color == BLACK) &&
	        (s->right->color == BLACK)
        )
    {
		s->color = RED;
		delete_case1(n->parent);
	} else
		delete_case4(n);
}

Диаграмма случая 4 Случай 4: S и его дети — чёрные, но P — красный. В этом случае мы просто меняем цвета S и P. Это не влияет на количество чёрных узлов на путях, проходящих через S, но добавит один к числу чёрных узлов на путях, проходящих через N, восстанавливая тем самым влияние удаленного чёрного узла.

void delete_case4(struct node *n)
{
	struct node *s = sibling(n);

	if (
            (n->parent->color == RED) &&
	        (s->color == BLACK) &&
	        (s->left->color == BLACK) &&
	        (s->right->color == BLACK)
        )
    {
		s->color = RED;
		n->parent->color = BLACK;
	} else
		delete_case5(n);
}

Диаграмма случая 5 Случай 5: S — чёрный, левый потомок S — красный, правый потомок S — чёрный, и N является левым потомков своего отца. В этом случае мы вращаем дерево вправо вокруг S. Таким образом левый потомок S становится его отцом и новым братом N. После этого мы меняем цвета у S и его нового отца. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у N есть чёрный брат с красным правым потомком, и мы переходим к случаю 6. Ни N, ни его отец не влияют на эту трансформацию. (Для случая 6 мы обозначим через S нового брата N.)

void delete_case5(struct node *n)
{
	struct node *s = sibling(n);

	if  (s->color == BLACK) { /* this if statement is trivial, 
due to case 2 (even though case 2 changed the sibling to a sibling's child, 
the sibling's child can't be red, since no red parent can have a red child). */
/* the following statements just force the red to be on the left of the left of the parent, 
   or right of the right, so case six will rotate correctly. */
		if (
                (n == n->parent->left) &&
		        (s->right->color == BLACK) &&
		        (s->left->color == RED)
           )
        {
            /* this last test is trivial too due to cases 2-4. */
			s->color = RED;
			s->left->color = BLACK;
			rotate_right(s);
		} else if (
                (n == n->parent->right) &&
		        (s->left->color == BLACK) &&
		        (s->right->color == RED)
            ) 
        {
            /* this last test is trivial too due to cases 2-4. */
			s->color = RED;
			s->right->color = BLACK;
			rotate_left(s);
		}
	}
	delete_case6(n);
}

Диаграмма случая 6 Случай 6: S — чёрный, правый потомок S — красный, и N является левым потомком своего отца P. В этом случае мы вращаем дерево влево вокруг P, после чего S становится отцом P и своего правого потомка. Далее мы меняем местами цвета у P и S (P принимает цвет S, S принимает цвет P), и делаем правого потомка S чёрным. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойства 4 (Оба потомка каждого красного узла — чёрные) и 5 (все пути из любой вершины к её листовым узлам содержат одинаковое количество чёрных узлов) не нарушаются. Тем не менее, у N теперь появился дополнительный чёрный предок: либо P стал чёрным, или он был чёрным и S был добавлен в качестве чёрного дедушки. Таким образом, проходящие через N пути проходят через один дополнительный чёрный узел. Между тем, если путь не проходит через N, то есть 2 возможных варианта: Он проходит через нового брата N. Тогда, он должен проходить через S и P, которые просто поменяли цвета и места. Поэтому путь содержит то же количество чёрных узлов. Он проходит через нового дядю N, правого потомка S. Когда-то он проходил через S, отца S и правого потомка S (который был красным), но теперь он проходит только через S, который принял на себя цвет своего прежнего родителя, и правого потомка S, который был перекрашен из красного в чёрный (Предполагаем, что цвет S: чёрный). Эффект заключается в том, что этот путь проходит через такое же количество чёрных узлов. В любом случае, число чёрных узлов на этих путях не изменится. Поэтому, мы восстановили свойства 4 (Оба потомка каждого красного узла — чёрные) и 5 (все пути из любой вершины к её листовым узлам содержат одинаковое количество чёрных узлов). Белый узел на диаграмме может быть как красным так и чёрным, но должен указывать на тот же цвет как в начале, так и в конце трансформации.

void delete_case6(struct node *n)
{
	struct node *s = sibling(n);

	s->color = n->parent->color;
    n->parent->color = BLACK;

	if (n == n->parent->left) {
        s->right->color = BLACK;
		rotate_left(n->parent);
	} else {
		s->left->color = BLACK;
		rotate_right(n->parent);
	}
}

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

Так же, хвостовая рекурсия никогда не происходит на дочерних узлах, поэтому цикл хвостовой рекурсии может двигаться только от дочерних узлов к их последовательным родителям. Произойдет не более, чем O(log n) циклических возвратов к случаю 1 (где n — общее количество узлов в дереве до удаления). Если в случае 2 произойдет вращение (единственно возможное в цикле случаев 1-3), тогда отец узла N становится красным после вращения и мы выходим из цикла. Таким образом будет произведено не более одного вращения в течение этого цикла. После выхода из цикла произойдет не более двух дополнительных поворотов. А в целом произойдет не более трех поворотов дерева.

Сравнение со сбалансированным АВЛ-деревом

Высота дерева

Пусть высота дерева h, минимальное количество вершин N. Тогда:

• для АВЛ-дерева ${\displaystyle N(h)=N(h-1)+N(h-2)+1}$. Поскольку ${\displaystyle N(0)=0}$, ${\displaystyle N(1)=1}$, N(h) растёт как последовательность Фибоначчи, следовательно ${\displaystyle N(h)=\Theta (\lambda ^{h})}$, где ${\displaystyle \lambda =({\sqrt {5}}+1)/2\approx 1,62}$
• для красно-чёрного дерева ${\displaystyle N(h)\geq 2^{(h-1)/2}=\Theta ({\sqrt {2}}^{h})}$

Следовательно, при том же количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем в ${\displaystyle \log \lambda /\log {\sqrt {2}}\approx 1,388}$ раз.^[5]

Поиск

Поскольку красно-чёрное дерево, в худшем случае, выше, поиск в нём медленнее, но проигрыш по времени не превышает 39 %.

Вставка

Вставка требует до 2 поворотов в обоих видах деревьев. Однако из-за большей высоты красно-чёрного дерева вставка может занимать больше времени.

Удаление

Удаление из красно-чёрного дерева требует до 3 поворотов, в АВЛ-дереве оно может потребовать числа поворотов до глубины дерева (до корня). Поэтому удаление из красно-чёрного дерева быстрее, чем из АВЛ-дерева. Тем не менее, тесты показывают, что АВЛ-деревья быстрее красно-чёрных во всех операциях^[6][7], автор последнего теста предполагает, что красно-чёрные деревья, возможно, производительнее при больших объёмах памяти^[8].

Память

АВЛ-дерево в каждом узле хранит разницу высот (целое число от −1 до +1, для кодирования нужно 2 бита). Красно-чёрное дерево в каждом узле хранит цвет (1 бит). Таким образом, красно-чёрное дерево может быть экономичнее. (Правда если учитывать, что в современных вычислительных системах память выделяется кратно байтам, то деревья абсолютно одинаковы)

Однако, на практике в обоих типах деревьев используются целые числа, так как работа с битами требует дополнительных процессорных вычислений (одной команды ассемблера and %al 0x10000000). Но тем не менее есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример — Boost Multiindex. Цель хранения цвета в бите — уменьшение потребления памяти красно-чёрным деревом (Ordered indices node compression). Бит цвета в такой реализации хранится не в отдельной переменной, а в одном из указателей узла дерева с превращением его в меченый указатель.

Доказательство асимптотических границ

Красно-чёрное дерево, которое содержит n внутренних узлов, имеет высоту ${\displaystyle O(log(n))}$.

Обозначения:

• ${\displaystyle h(v)}$ — высота поддерева с корнем в ${\displaystyle v}$
• ${\displaystyle bh(v)}$ — число чёрных узлов (не считая ${\displaystyle v}$, если он чёрный) от ${\displaystyle v}$ до любого листа в поддереве (называемое чёрной высотой)

Лемма: Поддерево с корнем в узле ${\displaystyle v}$ имеет не менее ${\displaystyle 2^{bh(v)}-1}$ внутренних узлов.

Доказательство леммы (индукцией по высоте):

Основание индукции: ${\displaystyle h(v)=0}$.

Если поддерево имеет нулевую высоту, то ${\displaystyle v}$ должен быть null, поэтому ${\displaystyle bh(''v'')=0}$.

Итак:

${\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0}$

Индукционный шаг: пусть узел ${\displaystyle v}$ такой, что ${\displaystyle h(v)=k}$ и поддерево имеет не менее ${\displaystyle 2^{bh(v)}-1}$ внутренних узлов.
Покажем, что тогда ${\displaystyle v'}$, для которого ${\displaystyle h(v')=k+1}$, имеет не менее ${\displaystyle 2^{bh(v')}-1}$ внутренних узлов.

Так как ${\displaystyle v'}$ имеет ${\displaystyle h(v')>0}$, это внутренний узел. Как таковой он имеет два потомка, оба из которых имеют чёрную высоту ${\displaystyle bh(v')}$, либо ${\displaystyle bh(v')-1}$ (зависит от того, является ${\displaystyle v'}$ красным, или чёрным).
По индукционному предположению каждый потомок имеет не менее ${\displaystyle 2^{bh(v')-1}-1}$ внутренних узлов, поэтому ${\displaystyle v'}$ имеет не менее

${\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1}$

внутренних узлов.

Используя эту лемму, мы можем показать, что дерево имеет логарифмическую высоту. Так как по крайней мере половина узлов в любом пути от корня до листа — чёрные (свойство 4 красно-чёрного дерева), чёрная высота корня не менее ${\displaystyle h(root)/2}$. По лемме имеем:

${\displaystyle n\geq 2^{h({\text{root}}) \over 2}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\text{root}}) \over 2}\leftrightarrow \;h({\text{root}})\leq 2\log _{2}{(n+1)}.}$

Поэтому высота корня ${\displaystyle O(log(n))}$.

См. также

• Поиск в глубину
• Поиск в ширину
• Сбалансированные (самобалансирующиеся) деревья:
  • АВЛ-дерево
  • Матричное дерево
  • Идеально сбалансированное дерево
  • Расширяющееся дерево
  • B+-деревья
  • 2-3-дерево
  • R-дерево
  • B*-дерево
• Список структур данных (деревья)

Ссылки

• Томас Ниман Сортировка и поиск: Рецептурный справочник
• Эффективная реализация красно-чёрных деревьев (ENG)
• Красно-чёрные деревья (теория и реализация)

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Introduction to algorithms. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 336-364. — ISBN 978-5-8459-0857-5.

Примечания

1. data structures - Where does the term "Red/Black Tree" come from? - Software Engineering Stack Exchange  (неопр.). Дата обращения: 4 января 2019. Архивировано 5 января 2019 года.
2. Курс «Algorithms: Design and Analysis, Part 1», лекция «Red-Black Trees» Архивная копия от 25 августа 2014 на Wayback Machine (Видео 5:07) (англ.)
3. Dr Dobbs — STL’s Red-Black Trees
4. Класс TreeMap  (неопр.). Дата обращения: 13 марта 2015. Архивировано 18 марта 2015 года.
5. в пределе для большого числа листьев
6. AVL vs RB Архивная копия от 11 июля 2016 на Wayback Machine (англ.)
7. Red-Black versus AVL: benchmarks Архивная копия от 10 февраля 2015 на Wayback Machine (англ.)
8. AVL vs. Red-Black: the conclusion Архивная копия от 10 февраля 2015 на Wayback Machine (англ.)