Симметричный обход красно черного дерева

Красно-черные деревья

Дек (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон (рис. 3). Первый и последний элементы дека соответствуют входу и выходу дека.

Рис. 3. Дек и его организация

Частные случаи дека – это ограниченные деки:

· дек с ограниченным входом – из конца дека можно только извлекать элементы;

· дек с ограниченным выходом – в конец дека можно только добавлять элементы.

Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.

Однако применительно к деку целесообразно говорить не о начале и конце как в очереди, а о левом и правом конце.

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим дек через объявление линейного двунаправленного списка:

Double_List *Begin;//начало дека

Double_List *End; //конец дека

Основные операции, производимые с деком:

· добавление элемента в левый конец дека;

· добавление элемента в правый конец дека;

· извлечение элемента из левого конца дека;

· извлечение элемента из правого конца дека;

Реализацию этих операций приведем в виде соответствующих функций, которые, в свою очередь, используют функции операций с линейным двунаправленным списком.

void Make_Deque(int n, Deque* End_Deque)

Double_List *ptr; //вспомогательный указатель

void Print_Deque(Deque* Begin_Deque)

//добавление элемента в правый конец дека

void Add_Right_Item_Deque(int NewElem, Deque* End_Deque)

//добавление элемента в левый конец дека

void Add_Left_Item_Deque(int NewElem, Deque* Begin_Deque)

Insert_Item_Double_List(Begin_Deque->Begin, 1, NewElem);

//извлечение элемента из левого конца дека

int Extract_Left_Item_Deque(Deque* Begin_Deque)

//извлечение элемента из правого конца дека

int Extract_Right_Item_Deque(Deque* End_Deque)

bool Empty_Deque(Deque* Begin_Deque)

void Clear_Deque(Deque* Begin_Deque)

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

Красно-черное дерево (Red-Black-Tree, RB-Tree) – это бинарное дерево со следующими свойствами (рис. 4):

· каждая вершина должна быть окрашена либо в черный, либо в красный цвет;

· корень дерева должен быть черным;

· листья дерева должны быть черными и объявляться как NIL-вершины (NIL-узлы, то есть «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели);

· каждый красный узел должен иметь черного предка;

· на всех ветвях дерева, ведущих от его корня к листьям, число черных вершин одинаково.

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

Над красно-черными деревьями можно выполнять все те же основные операции, что и над бинарными деревьями.

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

//создание красно-черного дерева

void Make_RBTree(RBTree** Node, int n)

//добавление узла в красно-черное дерево

void Insert_Node(RBTree** Node,int Data)

RBTree **Curent, *Parent, *New_Node;

// Вставка элемента в дерево

if (Data < Parent->Data) Parent->Left = New_Node;

else Parent->Right = New_Node;

// Поддержка баланса дерева после вставки нового элемента

void Insert_Fixup(RBTree** Node,RBTree* New_Node)

while (Current!= *(Node) && Current->Parent->color == RED)

if (Current->Parent == Current->Parent->Parent->Left)

RBTree *ptr = Current->Parent->Parent->Right;

if (Current == Current->Parent->Right)

// сделать Current левым потомком

RBTree *ptr = Current->Parent->Parent->Left;

if (Current == Current->Parent->Left)

//поворот узла Current влево

void Rotate_Left(RBTree** Node,RBTree *Current)

if (ptr->Left!= NIL) ptr->Left->Parent = Current;

if (ptr!= NIL) ptr->Parent = Current->Parent;

if (Current == Current->Parent->Left)

if (Current!= NIL) Current->Parent = ptr;

//поворот узла Current вправо

void Rotate_Right(RBTree** Node,RBTree *Current)

if (ptr->Right!= NIL) ptr->Right->Parent = Current;

if (ptr!= NIL) ptr->Parent = Current->Parent;

if (Current == Current->Parent->Right)

if (Current!= NIL) Current->Parent = ptr;

//печать красно-черного дерева

void Print_RBTree(RBTree* Node, int l)

//прямой обход красно-черного дерева

void PreOrder_RBTree(RBTree* Node)

//обратный обход красно-черного дерева

void PostOrder_RBTree(RBTree* Node)

//симметричный обход красно-черного дерева

void SymmetricOrder_RBTree(RBTree* Node)

//проверка пустоты красно-черного дерева

bool Empty_RBTree(RBTree* Node)

return (Node == NIL? true: false);

//освобождение памяти, выделенной под красно-черное дерево

void Delete_RBTree(RBTree* Node)

Источник

Красно-черные деревья: коротко и ясно

Итак, сегодня хочу немного рассказать о красно-черных деревьях. Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.

Красно-черные деревья относятся к сбалансированным бинарным деревьям поиска.

Как бинарное дерево, красно-черное обладает свойствами:

1) Оба поддерева являются бинарными деревьями поиска.

2) Для каждого узла с ключом выполняется критерий упорядочения:

ключи всех левых потомков

(в других определениях дубликаты должны располагаться с правой стороны либо вообще отсутствовать).
Это неравенство должно быть истинным для всех потомков узла, а не только его дочерних узлов.

Свойства красно-черных деревьев:

1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).

2) Корень окрашен в черный цвет.

3) Листья(так называемые NULL-узлы) окрашены в черный цвет.

4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.

5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

Ну и почему такое дерево является сбалансированным?

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

Пусть у нас есть красно-черное дерево. Черная высота равна (black height).

Если путь от корневого узла до листового содержит минимальное количество красных узлов (т.е. ноль), значит этот путь равен .

Если же путь содержит максимальное количество красных узлов ( в соответствии со свойством ), то этот путь будет равен .

То есть, пути из корня к листьям могут различаться не более, чем вдвое (, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было

Как производится вставка?

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

Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.

Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет.

Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы.

В основном встречаются 2 других нарушения:

1) Красный узел имеет красный дочерний узел (нарушено свойство ).

2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ).

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

Это вообще где-то используется?

Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и крестный красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

Это все, что я хотела рассказать.

Источник