Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующихлогарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная)[источник не указан 576 дней] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.
Терминология
Красно-чёрное дерево является особым видом двоичного дерева, используемым в компьютерной науке для организации сравнимых данных, таких как фрагменты текста или числа.Листовые узлы красно-черных деревьев не содержат данных. Такие листья не нуждаются в явном выделении памяти — нулевой указатель на потомка может фактически означать, что этот потомок — листовой узел, но в некоторых случаях работы с красно-черными деревьями использование явных листовых узлов может послужить упрощением алгоритма.
[править]Свойства
Пример красно-чёрного дерева
Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или черный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:
1. Узел либо красный, либо чёрный.
2. Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
3. Все листья(NIL) — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
Эти ограничения реализуют критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа (если дальний лист расположен на 3-м уровне). Результатом является то, что дерево примерно сбалансировано. Так как такие операции как вставка, удаление и поиск значений требуют в худшем случае времени, пропорционального длине дерева, эта теоретическая верхняя граница высоты позволяет красно-чёрным деревьям быть более эффективными в худшем случае, чем обычные двоичные деревья поиска.
Чтобы понять, почему это гарантируется, достаточно рассмотреть эффект свойств 4 и 5 вместе. Пусть для красно-чёрного дерева T число черных узлов в свойстве 5 равно B. Тогда кратчайший возможный путь от корня дерева T до любого листового узла содержит B черных узлов. Более длинный возможный путь может быть построен путем включения красных узлов. Однако, свойство 4 не позволяет вставить несколько красных узлов подряд. Поэтому самый длинный возможный путь состоит из 2B узлов, попеременно красных и черных. Любой максимальный путь имеет одинаковое число черных узлов (по свойству 5), следовательно, не существует пути, более чем вдвое длинного, чем любой другой путь.
Во многих реализациях структуры дерева возможно, чтобы узел имел только одного потомка и листовой узел содержал данные. В этих предположениях реализовать красно-чёрное дерево возможно, но изменятся несколько свойств и алгоритм усложнится. По этой причине данная статья использует «фиктивные листовые узлы», которые не содержат данных и просто служат для указания, где дерево заканчивается. Эти узлы часто опускаются при графическом изображении, в результате дерево выглядит противоречиво с вышеизложенными принципами, но на самом деле противоречия нет. Следствием этого является то, что все внутренние (не являющиеся листовыми) узлы имеют два потомка, хотя один из них может быть нулевым листом. Свойство 5 гарантирует, что красный узел обязан иметь в качестве потомков либо два черных нулевых листа, либо два черных внутренних узла. Для чёрного узла с одним потомком нулевым листовым узлом и другим потомком, не являющимся таковым, свойства 3, 4 и 5 гарантируют, что последний должен быть красным узлом с двумя черными нулевыми листьями в качестве потомков.
Иногда красно-чёрное дерево трактуют как бинарное дерево поиска, у которого вместо узлов в красный и чёрный цвета раскрашены ребра, но это не имеет какого-либо значения. Цвет узла в терминах данной статьи соответствует цвету ребра, соединяющего узел со своим предком, за исключением того, что корневой узел всегда чёрный (свойство 2), в то время как соответствующее ребро не существует.
[править]Аналогия с B-деревом порядка 4
То же самое красно-чёрное дерево, что и в примере выше, представленное как B-дерево.
Красно-чёрное дерево схоже по структуре с B-деревом порядка 4, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. В таком В-дереве каждый узел будет содержать только одно значение, соответствующее значению чёрного узла красно-чёрного дерева с необязательным значениями до и/или после него в том же узле, оба из которых соответствуют эквивалентным красным узлам красно-чёрного дерева.
Один из способов увидеть эту эквивалентность — «поднять» красные узлы в графическом представлении красно-чёрного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками черными узлами, образуя страницу. В В-дереве, или в модифицированном графическом представлении красно-чёрного дерева, у всех листовых узлов глубина одинаковая.
Этот тип В-дерева является более общим, чем красно-чёрное дерево, хотя, как видно, из одного такого В-дерева порядка 4 могут быть получены несколько красно-черных деревьев. Если страница В-дерева содержит только одно значение, данный узел чёрный и имеет двух потомков. Если страница содержит три значения, то центральный узел является чёрным, а каждый его сосед — красным. Однако, если страница содержит два значения, любой узел может стать чёрным в красно-чёрном дереве (и тогда второй будет красным).
[править]Работа с красно-чёрными деревьями
Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++[1], класс TreeMap языка Java[2], так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.
Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности. В частности, при сравнении с идеально сбалансированными деревьями часто обнаруживается, что последние имеют слишком жесткое условие сбалансированности и при выполнении операций удаления из дерева много времени тратится на поддержание необходимой сбалансированности.
Правила для красно-черных:
1. Узел либо красный, либо черный.
2. Корень — черный.
3. Все листья — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
Создадим на C# класс узла дерева
{
public NodeRB left; //левый потомок
public NodeRB right;//правый потомок
public NodeRB parent;//родитель
public bool isRed = true;//красный? по умолчанию черный
public int data;//значение
public int count; //количество элементов с таким значением
//конструктор принимает значение узла
public NodeRB(int data)
{
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
this.count = 1;
}
//конструктор, в котором можно указать родителя
public NodeRB(int key, NodeRB parent) : this(key)
{
this.parent = parent;
}
}
И класс дерева (из узлов)
class redBlack
{
public NodeRB root; //корневой элемент
public redBlack(int data)
{//создание дерева начинается с корня
this.root = new NodeRB(data);
}
//вывод всего дерева
public void printTree()
{
this.print(this.root);
}
//вывод поддерева в консоль
protected void print(NodeRB node)
{
if (node == null)
return;
print(node.left);
string line = node.data.ToString();
line += (node.isRed) ? " red" : " black";
if (node.parent != null)
line += " parent: " + node.parent.data.ToString();
Console.WriteLine(line);//вывод
print(node.right);
}
//...
}
У нас есть вывод дерева, но нужно сделать хотя бы добавление узлов в него. Мы можем добавить для начала метод добавления как в обычных бинарных деревьях поиска:
//добавление элемента в дерево после элемента "to" с ключем "key" //как в обычных бинарных деревьях поиска
protected NodeRB addNode(NodeRB to, int key)
{
if (key == to.data)//если такой элемент уже есть, увеличиваем счетчик
{
to.count++;
return to;
}
if (key < to.data) //нужно добавлять влево
{
if (to.left != null) //там уже есть элемент
return this.addNode(to.left, key);
return to.left = new NodeRB(key, to);
}
else //добавление вправо
{
if (to.right != null) //там уже есть элемент
return this.addNode(to.right, key);
return to.right = new NodeRB(key, to);
}
}
Как видно, наши деревья даже поддерживают добавление одинаковых элементов (см. счетчик count). Но этот метод не соблюдает правил красно-черных деревьев!
Смотрим в Википедию
У нас есть методы для 5 случаев, которые могут возникнуть при добавлении.
На C# я их переписал так и добавил публичный метод добавления:
//добавление элемента с соблюдением правил красно-черных деревьев
public NodeRB add(int key)
{
//добавим в дерево элемент n как в обычное бинарное дерево
NodeRB n = this.addNode(this.root, key);
//необходимо нормализовать правила красно-черных деревьев
this.case1(ref n);
//возвращаем добавленный элемент
return n;
}
protected void case1(ref NodeRB n)
{//Текущий узел N в корне дерева.
if (n.parent == null)
{
n.isRed = false;
return;
}
this.case2(ref n);
}
protected void case2(ref NodeRB n)
{
if (n.parent.isRed == false) //Предок текущего узла черный, свойство 4 не нарушается.
{
n.isRed = true;
//Console.WriteLine(n.data + n.isRed.ToString());
/**
* Свойство 5 не нарушается, потому что текущий узел N имеет двух черных листовых потомков,
* но так как N является красным, пути до каждого из этих потомков содержит
* такое же число черных узлов, что и путь до черного листа, который был
* заменен текущим узлом, который был черный.
* */
return;
}
else
this.case3(ref n);
}
protected void case3(ref NodeRB n)
{
NodeRB u = this.uncle(n);//дядя
NodeRB g = this.grandparent(n); //дедушка
if ((u != null) && (u.isRed == true)) //Если и родитель и дядя красные
{ //то они оба могут быть перекрашены в черный
n.parent.isRed = false;
u.isRed = false;
//и дедушка станет красным для сохранения свойства 5
g.isRed = true;
//дедушка G теперь может нарушить свойства 2 (Корень — черный) или 4 (Оба потомка каждого красного узла — черные)
this.case1(ref g);//Чтобы это исправить, вся рекурсивно выполняется case1 для дедушки
}
else
this.case4(ref n);//Родитель P является красным, но дядя U — черный.
}
protected void case4(ref NodeRB n)
{ //тут два случая (4 и 5) объеденены в 1 метод, но возможно неправильно!
NodeRB g = this.grandparent(n); //дедушка
if (g == null)
return;
if ((n == n.parent.right) && (n.parent == g.left))
{
this.rotate_left(ref n);//поворот дерева влево
//n = n.left;
}
else if ((n == n.parent.left) && (n.parent == g.right))
{
rotate_right(ref n);//поворот вправо
//n = n.right;
}
// Родитель P является красным, но дядя U — черный, текущий узел N — левый\правый потомок P
// и P — левый\правый потомок G.
//цвета P и G меняются и в результате дерево удовлетворяет Свойству 4 (Оба потомка любого красного узла — черные).
n.parent.isRed = false;
g.isRed = true;
//поворачиваем дедушку
if ((n == n.parent.left) && (n.parent == g.left)) {
this.rotate_right(ref g);
} else { // зеркальная ситуация
this.rotate_left(ref g);
}
}
Не хватает еще методов для поворота дерева, я реализовал их следующим образом:
//повоторот вправо
protected void rotate_right(ref NodeRB n)
{
if (n.parent == null)
return;
//правый потомок узла ставим в левый родительского
if (n.left != null)
{
n.parent.left = n.right;
n.parent.left.parent = n.parent;
}
else
n.parent.left = null;
n.right = n.parent;//родительский ставим на его место
n.parent = n.parent.parent;//ссылку на нового родителя берем у бывшего родителя
n.right.parent = n;//бывшему родителю ставим ссылку на текущий узел
if (n.parent != null)//если нужно поправить ссылку у дедушки
{
if (n.parent.left == n.left)
n.parent.left = n;
if (n.parent.right == n.left)
n.parent.right = n;
}
else //корень дерева поменялся
this.root = n;
}
//поворот влево
protected void rotate_left(ref NodeRB n)
{
if (n.parent == null)
return;
//левый потомок узла ставим в правый родительского
if (n.left != null)
{
n.parent.right = n.left;
n.parent.right.parent = n.parent;
}
else
n.parent.right = null;
n.left = n.parent;//родительский ставим на его место
n.parent = n.parent.parent;//ссылку на нового родителя берем у бывшего родителя
n.left.parent = n;//бывшему родителю ставим ссылку на текущий узел
if (n.parent != null)//если нужно поправить ссылку у дедушки
{
if (n.parent.left == n.left)
n.parent.left = n;
if (n.parent.right == n.left)
n.parent.right = n;
}
else //корень дерева поменялся
this.root = n;
}
Небольшие вспомогательные методы для нахождения “дяди” и “дедушки” узла:
//найти дедушку
protected NodeRB grandparent(NodeRB n)
{
if ((n != null) && (n.parent != null))
return n.parent.parent;
else
return null;
}
//найти дядю
protected NodeRB uncle(NodeRB n)
{
NodeRB g = grandparent(n);
if (g == null)
return null;
if (n.parent == g.left)
return g.right;
else
return g.left;
}
Можно проверить работу нашего класса в главной функции Main
(консольное приложение)
redBlack rb = new redBlack(8);
rb.add(5);
rb.add(9);
rb.add(10);
rb.printTree();
//задержка экрана
Console.ReadKey();
По выводу программы можно нарисовать схему дерева:
которая не нарушает правил красно-черных деревьев.
