Новосибирский государственный технический университет
Кафедра вычислительной техники
 |
Лабораторная работа №2
по дисциплине «Структуры и алгоритмы обработки данных»
"Нелинейные коллекции данных - сбалансированные деревья поиска"
Вариант:3
Группа: АМ-015
Бригада:1
Студенты: С.
Новосибирск 2002
Цель лабораторной работы
Реализация типовых коллекций данных в виде Абстрактных Типов Данных (АТД) на языке высокого уровня С++. Оценка и анализ эффективности алгоритмов реализации АТД. Формирование библиотеки разработанных АТД.
Задание
Спроектировать, реализовать и провести тестовые испытания АТД для нелинейной коллекции - "Сбалансированное дерево поиска". АТД " RB - дерево" - модификация АТД «Рекурсивное дерево двоичного поиска».
Описание иерархии классов
Классы «Дерво двоичного поиска» («BinTree») и «RB - дерево»(RBTree) cхожи по своей внутренней организации, но RBTree сбалансированное дерево 2-го поиска. Соответственно, необходима балансировка после операций вставки и удаления. Так же у RBTree есть своя особенность: каждый узел имеет цвет либо черный, либо красный.
RBTree обладает свойствами:
· Каждый узел покрашен либо в черный, либо в красный цвет.
· Листьями объявляются NIL-узлы (т. е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет.
· Если узел красный, то оба его потомка черны.
· На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Ну и соответственно, все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.
Операция «Включение»
Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL-узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.
Операция «Удаления» аналогична.
Формат АТД
Структура данных – «Рекурсивное дерево двоичного поиска». Модификация АТД – «RB - дерево».
АТД «Рекурсивное дерево двоичного поиска»
Данные:
Четыре указателя на объекты данного класса (правый, левый потомки; родитель, корень). Объект данных, которые хранятся в узле.
Три целых числа, указывающие на число рекурсивных вызовов трёх операций (включение, удаление, поиск по значению).
Операции:
Конструктор:
Начальные значения: значение данных (по умолчанию 15).
Процесс: установление всех счётчиков эл. действий в 0, все укзатели устанавливаются в NULL, кроме корня (он указывает на этот узел).
Size:
Вход: нет.
Предусловие: нет.
Процесс: вызывает рекурсивню функцию подсчета узлов, которая и возвращает значение количества узлов.
Выход: количество узлов
Постусловие: нет.
HighTree:
Вход: нет.
Предусловие: нет.
Процесс: вызывает рекурсивню функцию подсчета высоты, которая и возвращает значение высоты дерева.
Выход: высота дерева.
Постусловие: нет.
Empty:
Вход: нет
Предусловие: нет
Процесс: проверка на пустоту дерева
Выход: Перепенная типа boolean. True – дерево пусто. False – в дереве есть эл-ты.
Постусловие: нет.
PrintTree:
Вход: нет.
Предусловие: нет.
Процесс: вызывает рекурсивную функцию вывода дерева, которая и выводит его.
Выход: нет.
Постусловие: нет.
Clear:
Вход: нет.
Предусловие: нет.
Процесс: очистка дерева.
Выход: нет.
Постусловие: дерево пустое( корень не удаляется).
Include:
Вход: элемент для вставки в дерево.
Предусловие: нет.
Процесс: вызывает рекурсивную функцию вставки значения в дерево и она включает значение.
Выход: нет
Постусловие: дерево имеет новый элемент, если выполнены все условия; его размер увеличен на 1.
Delete:
Вход: значение по которому д. б. удалён элемент.
Предусловие: производим поиск в дереве и если такого элемента нет, то выбрасываем исключение.
Процесс: удаление элемента по значению.
Выход: сообщение исключения в случае неудачи.
Постусловие: дерево уменьшается на 1 элемент.
FindNod:
Вход: значение по которому будет производится поиск.
Предусловие: нет.
Процесс: вызов рекурсивной функции поиска, которая и ищет узел содерж. данный элемент.
Выход: возвращает узел содержащий данное значение в случае удачи или NULL в случае неудачи.
Постусловие: нет.
FindDat:
Вход: значение по которому будет производится поиск.
Предусловие: нет.
Процесс: вызывает рекурсивную функцию поиска, которая и ищет узел содерж. данный элемент.
Выход: возвращает 1 в случае удачи или -1 в случае неудачи.
Постусловие: нет.
GetStat:
Вход: три значения. Число операций вставки, удаления, поиска.
Предусловие: нет
Процесс: подсчитывается трудоемкость данных операций.
Выход: указатель на значения трудоёмкостей.
Постусловие: нет.
NullStat:
Вход: нет.
Предусловие: нет.
Процесс: очищает счётчики эл. операций.
Выход: нет.
Постусловие: нет.
SubInclude:
Вход: узел на данном шагу рекурсии, значение, которое включается.
Предусловие: нет.
Процесс: включение значение в дерево.
Выход: нет.
Постусловие: увеличивается число узлов в дереве, увеличивается счетчик «вставки».
SubDelete:
Вход: узел, который удаляется и его правый потомок.
Предусловие: нет.
Процесс: перестраивает узлы от удаляемого, присваевает значение крайнего левого узла к удаляемому узлу и удаляет крайний левый узел.
Выход: обновленный, уже неудаляемый, узел.
Постусловие: количество узлов уменьшается на 1, увеличивается счетчик «удаления».
SubFindNod:
Вход: узел на данном шаге рекурсии, искомое значение для поиска.
Предусловие: если искомое значение совпадает со значением узла на данном шаге, то возвращается узел.
Процесс: рекурсивная функция поиска по значению.
Выход: указатель на узел с данным значением - удача, NULL - в случае неудачи.
Постусловие: увеличение счетчика «поиска».
SubFindDat:
Вход: узел на данном шаге рекурсии, искомое значение для поиска.
Предусловие: если искомое значение совпадает со значением узла на данном шаге, то возвращается 1.
Процесс: рекурсивная функция поиска по значению.
Выход: 1- в случае удачи, -1 неудачи.
Постусловие: нет.
SizeSub:
Вход: узел на данном шаге рекурсии.
Предусловие: пока узел не равен NULL.
Процесс: рекурсивная функция подсчета кол-ва узлов в дереве.
Выход: кол-во узлов.
Постусловие: нет.
HighTreeSub:
Вход: узел на данном шаге рекурсии.
Предусловие: пока узел не равен NULL.
Процесс: рекурсивная функция подсчета высоты дерева.
Выход: высота дерева.
Постусловие: нет.
PrintTreeSub:
Вход: узел на данном шаге рекурсии, число пробелов на данном шаге рекурсии.
Предусловие: пока узел не равен NULL.
Процесс: рекурсивная функция вывода узлов дерева.
Выход: нет.
Постусловие: нет.
ClearSub:
Вход: узел на данном шаге рекурсии.
Предусловие: пока узел не равен NULL.
Процесс: рекурсивная функция удаления узлов дерева.
Выход: нет.
Постусловие: все узлы, кроме корня, удалены.
АТД «Рекурсивное дерево двоичного поиска»
АТД «RB - дерево»
Данные:
Положительное целое число, указывающее на цвет узла.
Объект данного класса указывающего на корень.
Операции:
Конструктор:
Начальные значения: размер массива (по умолчанию 10).
Процесс: установление всех счётчиков эл. действий в 0, все укзатели устанавливаются в NULL, кроме корня (он указывает на этот узел), цвет устанавливается в черный.
Clear:
Вход: нет.
Предусловие: нет.
Процесс: очистка дерева.
Выход: нет.
Постусловие: дерево пустое( корень не удаляется).
Include:
Вход: элемент для вставки в дерево.
Предусловие: нет.
Процесс: вызывает рекурсивную функцию вставки значения в дерево и она включает значение, этот элемент окрашивается в черный цвет.
Выход: нет
Постусловие: дерево имеет новый элемент, если выполнены все условия; его размер увеличен на 1.
PrintTree:
Вход: нет.
Предусловие: нет.
Процесс: вызывает рекурсивную функцию вывода дерева, которая и выводит его.
Выход: нет.
Постусловие: нет.
RBFindNod:
Вход: значение по которому будет производится поиск.
Предусловие: нет.
Процесс: вызов рекурсивной функции поиска, которая и ищет узел содерж. данный элемент.
Выход: возвращает узел содержащий данное значение в случае удачи или NULL в случае неудачи.
Постусловие: нет.
Delete:
Вход: значение по которому д. б. удалён элемент.
Предусловие: производим поиск в дереве и если такого элемента нет, то выбрасываем исключение.
Процесс: удаление элемента по значению, балансировка и перекраска дерева.
Выход: сообщение исключения в случае неудачи.
Постусловие: дерево уменьшается на 1 элемент, увеличение счетчика «удаления».
DelRB:
Вход: удаляемый узел.
Предусловие: нет.
Процесс: функция менеджер. Делает «подготовительный этап» до функции перекраски и балансировки. Удаляет узел.
Выход: нет.
Постусловие: дерево уменьшается на 1 элемент, увеличение счетчика «удаления».
DelFix:
Вход: 2-а узла на данном этапе рекурсии(1- потомок удаляемого, 2-предок удяляемого).
Предусловие: нет.
Процесс: перекраска узлов и балансировка дерева.
Выход: нет.
Постусловие: изменение окраски узлов и взаимное расположение, увеличение счетчика «удаления».
SubInclude:
Вход: узел на данном этапе рекурсии и включаемое значение.
Предусловие: нет.
Процесс: включение нового узла в дерево и вызов функции перекраски и балансировки.
Выход: нет.
Постусловие: увеличение размера дерева, увеличение счетчика «вставки».
InsertFixUp:
Вход: включаемый узел.
Предусловие: выход из функции, если на данном этапе рекурсии узел является корнем или цвет предка черный.
Процесс: перекараска и балансировка дерева.
Выход: нет.
Постусловие: изменение окраски узлов и взаимное расположение, увеличение счетчика «вставки».
rotateRight:
Вход: узел относительно, которого производится вращение.
Предусловие: нет.
Процесс: вращение узлов вправо т. е. балансировка.
Выход: нет.
Постусловие: изменение взаиморасположения узлов.
rotateLeft:
Вход: узел относительно, которого производится вращение.
Предусловие: нет.
Процесс: вращение узлов влево т. е. балансировка.
Выход: нет.
Постусловие: изменение взаиморасположения узлов.
PrintTreeSub:
Вход: узел на данном шаге рекурсии, число пробелов на данном шаге рекурсии.
Предусловие: пока узел не равен NULL.
Процесс: рекурсивная функция вывода узлов дерева.
Выход: нет.
Постусловие: нет.
Конец АТД«RB - дерево».
Графики и таблицы с полученными оценками эффективности алгоритмов операций для наихудшего, наилучшего и среднего случаев функционирования АТД
N OldSize | BinTree | RBTree | N NewSize | ||||||
Find | Inc | Del | Med | Find | Inc | Del | Med | ||
100 | 6 | 6 | 9 | 7 | 5 | 6 | 6 | 5 | 102 |
300 | 7 | 8 | 12 | 9 | 6 | 7 | 7 | 6 | 299 |
500 | 8 | 10 | 14 | 10 | 7 | 8 | 9 | 8 | 499 |
1000 | 10 | 12 | 16 | 12 | 7 | 9 | 12 | 9 | 1002 |
2500 | 11 | 12 | 19 | 14 | 9 | 10 | 14 | 11 | 2501 |
5000 | 13 | 14 | 22 | 16 | 10 | 11 | 15 | 11 | 4998 |
Количество операций =100 | |||||||||
Find, Include, Delete – это количество попаданий в узел (рекурсивный вызов)/ кол-во операций соответственно. Mediana=(Find+Include+Delete)/3.
Сравнение операций RB и Bin деревьев
Из графиков видно, что наиболее трудоемкая СД является «BinTree», т. к. она несбалансированная. Соответственно, увеличивается число рекурсивных вызовов для того что бы попасть в вершину дерева.
Наиболее трудоемкая операция – удаление, т. к. функции удаления использует функцию поиска, то соответственно она зависит от реализации ф-ции поиска. Трудоемкости вставки и поиска приблизительно равны.
Текст программы:
template <class T> class BinTree
{
protected:
BinTree<T> *left;//левый потомок
BinTree<T> *right;//правый -\\-
BinTree<T> *parent;//родитель
BinTree<T> *broot;//корень
T dat; //данные
//счетчики рекурсивных вызовов
long del;//удаление
long ins;//вставка
long find;//поиск
public:
BinTree(T _dat=15)//конструктор. По умолчанию значение корня=15
{
dat=_dat;right=left=parent=NULL;
broot=this;//корень
del=ins=find=0;count=0;//обнуление
}
~BinTree()
{
del=ins=dat=0;
}
virtual int Size()//опрос количества узлов в дереве
{
return SizeSub(broot);
}
int HighTree()//высота дерева
{
return HighTreeSub(broot);
}
bool Empty()//проверка пустого дерева
{
if(broot->left==NULL && broot->right==NULL) return true;
return false;
}
virtual void PrintTree() //распичатка дерева
{
cout<<"This BST Struct\n\n";
PrintTreeSub(broot,1);
}
virtual void Clear()//очистка дерева
{
ClearSub(broot);
broot->left=NULL;//у корня нет потомков
broot->right=NULL;
}
virtual void Include(T _dat)//включение значения в дерево
{
SubInclude(broot,_dat);
}
virtual void Delete(T _dat)//удаление узла с этим значением
{
long oldfind=find;//запоминаем счетчик поиска
BinTree<T> *temp=FindNod(_dat);//получаем этот узел
del=del+(find-oldfind);//записываем разность в сч. удалений
find=oldfind;//восстанавливаем сч."поиска"
if(temp==NULL)throw " Ошибка! Узла с таким значением нет.";
//если значения нет, то ошибка
if(temp->left==NULL && temp->right==NULL)//если у него нет потомков
{
del++;
if(temp->parent->left==temp)//если это левый потомок
temp->parent->left=NULL;
else //если это правый потомок
temp->parent->right=NULL;
}
else
if(temp->left==NULL)//если нет левого потомка
{
del++;
if(temp->parent!=NULL)//если удаляем не root
{
temp->right->parent=temp->parent;
temp->parent->left=temp->right;
}
else//если удаляем root
{
temp->right->parent=NULL;
broot=temp->right;
}
}
else
if(temp->right==NULL)//если нет правого потомка
{
del++;
if(temp->parent!=NULL)//если удаляем не root
{
temp->left->parent=temp->parent;
temp->parent->left=temp->left;
}
else//если удаляем root
{
temp->left->parent=NULL;
broot=temp->left;
}
}
else
if(temp->right!=NULL && temp->left!=NULL)//если есть потомки
{
temp->right=SubDelete(temp->right, temp);
return;
}
if(this!=temp)delete temp;//удаляем этот узел
//мы же не можем удалить самого себя
}
BinTree<T>* FindNod(T _dat) //поиск по значению.
{//Удача - укзатель на узел содержащий данное значение
//не найден - -1
return SubFindNod(broot,_dat);
}
int FindDat(T _dat)//поиск по значению в дереве. 1- удача. -1- не найден.
{
return SubFindDat(broot,_dat);
}
virtual long * GetStat(long _del, long _ins, long _find)//получение статистики
{
//пользователь после тестирования должен удалить
//данные, иначе "лики памяти"
long *st=new long[4];
st[0]=del/_del;
st[1]=ins/_ins;
st[2]=find/_find;
st[3]=(del/_del+ins/_ins+find/_find)/3;
return st;
}
virtual void NullStat()//очищаем статистику
{
ins=del=find=0;
}
protected:// служебные рекурсивные функции
void SubInclude(BinTree<T> *temp, T _dat)//включение
{//вспомогательная рекурсивная функция
//включение в дерево
ins++;
if(temp->dat>_dat && temp->left==NULL)//если меньше и у него
{ //нет левого потомка
temp->left=new BinTree<T>(_dat);
temp->left->parent=temp;
return;
}
if(temp->dat<_dat && temp->right==NULL)//если больше и у него
{ //нет правого потомка
temp->right=new BinTree<T>(_dat);
temp->right->parent=temp;
return;
}
if(temp->dat>_dat)//если меньше, то влево
{
SubInclude(temp->left,_dat);
}
if(temp->dat<_dat)//если больше, то вправо
{
SubInclude(temp->right,_dat);
}
}
virtual BinTree<T>* SubDelete(BinTree<T> *temp, BinTree<T> *t0)
{ //вспомогательная рекурсивная функция
//перестройка потомков от удаляемого узла
del++;
if(temp->left!=NULL)
{
temp->left=SubDelete(temp->left, t0);
return temp;
}
t0->dat=temp->dat;
BinTree<T> * x=temp->right;
if(this!=temp)delete temp;//нельзя же удалить самого себя
return x;
}
virtual BinTree<T>* SubFindNod(BinTree<T> *temp, T _dat)//поиск по значению
{
//вспомогательная рекурсивная функция
//NULL - неудача. Узел - при удаче
if(temp->dat==_dat) return temp;//найден
if(temp->dat>_dat)//если меньше, то влево
{
if(temp->left==NULL)return NULL;//если до конца,
//и такого значения нет, то неудача
SubFindNod(temp->left,_dat);
}
else//если больше, то вправо
{
if(temp->right==NULL)return NULL;//если до конца,
//и такого значения нет, то неудача
SubFindNod(temp->right,_dat);
}
find++;
}
int SubFindDat(BinTree<T> *temp, T _dat)//поиск по значению
{ //вспомогательная рекурсивная функция
//1- удача -1- неудача
//аналогично функции SubFindNod
if(temp->dat==_dat) return 1;
if(temp->dat>_dat)
{
if(temp->left==NULL)return -1;
SubFindDat(temp->left,_dat);
}
else
{
if(temp->right==NULL)return NULL;
SubFindDat(temp->right,_dat);
}
}
int SizeSub(BinTree<T> *p)//подсчет числа вершин д. дерева
{
//вспомогательная рекурсивная функция
if (p==NULL) return 0;
return (1 + SizeSub(p->right) + SizeSub(p->left));
}
int HighTreeSub(BinTree<T> *p)//подсчет максимальной длины ветви.
{//вспомогательная рекурсивная функция
if (p==NULL) return 0;
int nr=HighTreeSub(p->right)+1;//вправо
int nl=HighTreeSub(p->left)+1;//потом влево
return nr>nl? nr : nl;//если nr>nl -->возвратить nr, иначе nl
}
void ClearSub(BinTree<T> *p)//очистка дерева
{//вспомогательная рекурсивная функция
if(p==NULL) return ;
ClearSub(p->left);//левые ветки
ClearSub(p->right);//правые ветки
if(this!=p)delete p;//не можем удалить сами себя
}
virtual void PrintTreeSub(BinTree<T> *p, int lvl)//распечатка ф-ии
{//вспомогательная рекурсивная функция
if(p==NULL) return ;
PrintTreeSub(p->right, lvl+1);
for(int i=0;i<lvl*2;i++)
{
cout<<" ";
}
cout<<p->dat<<'\n';
PrintTreeSub(p->left, lvl+1);
}};
typedef enum { BLACK, RED } RBTreeColor;//Задание цветов
template <class T> class RBTree: public BinTree<T>
{
int color;//цвет
RBTree<T> *root;//корень RB-дерева
public:
RBTree(T _dat=15)//конструктор доопределен.
{
dat=_dat;ins=del=find=0;
color=BLACK;//черный при сождании
root=this;
}
void Clear()
{ //Аналогично функции Clear()
ClearSub(root);
root->left=NULL;
root->right=NULL;
}
void Include(T _dat)//включение нового значения в RB-дерево
{
SubInclude(root,_dat);
root->color = BLACK;
}
void PrintTree()//вывод RB - дерева
{
cout<<"This RBTree Struct\n\n";
PrintTreeSub(root,1);
}
RBTree<T>* RBFindNod(T _dat)
{
return (RBTree<T>*)SubFindNod(root,_dat);//получаем этот узел
}
void Delete(T _dat)//удаляем RBT - Node по значению.
{ // в случае если такого значения нет, то выбрасываем исключение
long oldfind=find;//манипуляция со счетчиками
RBTree<T> *temp=(RBTree<T>*)SubFindNod(root,_dat);
del=del+(find-oldfind);
find=oldfind;
if(temp==NULL)throw " Ошибка! Узла с таким значением нет";
DelRB(temp);//если узел найден, то удаляем его
}
int Size()//размер RBTree
{
return SizeSub(root);
}
protected:
/******
* Находим удаляемый узел *
* Делаем балансировку и перекраску если это *
* необходимо. *
* Удаляем его *
*******/
void DelRB(BinTree<T> *d)
{
BinTree <T>*x, *y,*prev;
int g=1;
if (d==root) g=0;
if (d->left==NULL||d->right==NULL)
{
y = d;
}
else
{
y=d->right;
while (y->left!=NULL)
{
del++;
y=y->left;
}
}
if (y->left!=NULL)
x=y->left;
else
x=y->right;
prev=y->parent;
if(x)x->parent=y->parent;
if (y->parent)
if (y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
else
root=(RBTree<T>*)x;
if (y!=d)d->dat=y->dat;
if (x&&y!=root && ((RBTree<T>*)y)->color==BLACK&&g)
{
DelFix((RBTree<T>*)x,(RBTree<T>*)prev);
if(x)((RBTree<T>*)x)->color=BLACK;
prev=prev->parent;
}
if(y!=this)delete ((RBTree<T>*)y);//не можем удалить сами себя
}
void DelFix(RBTree<T> *x, RBTree<T> *prev)
{
//функция балансировки и перекраски
del++;
if(x == root) return;
if(x&&((RBTree<T>*)x)->color==BLACK)return;
if (x==prev->left)
{
BinTree<T> *w=prev->right;
if(!w)return;
if (w&&((RBTree<T>*)w)->color==RED)
{
((RBTree<T>*)w)->color=BLACK;
((RBTree<T>*)prev)->color=RED;
if(w)rotateLeft((RBTree<T>*)prev);
if(prev!=NULL)w=prev->right;
}
if (w&&w->right && w->left&&((RBTree<T>*)w->left)->color==BLACK&&((RBTree<T>*)w->right)->color==BLACK)
{
((RBTree<T>*)w)->color=RED;
x=prev;
}
else
{
if(w&&w->right&&((RBTree<T>*)w->right)->color==BLACK)
{
if(w->left)((RBTree<T>*)w->left)->color=BLACK;
((RBTree<T>*)w)->color=RED;
rotateRight((RBTree<T>*)w);
if(prev!=NULL)w=prev->right;
}
if(w)((RBTree<T>*)w)->color=((RBTree<T>*)prev)->color;
((RBTree<T>*)prev)->color=BLACK;
if(w&&w->right)((RBTree<T>*)w->right)->color=BLACK;
if(w)rotateLeft((RBTree<T>*)prev);
x=root;
}
DelFix(x, prev);
}
else
{
BinTree <T>*w = prev->left;
if(!w)return;
if (w&&((RBTree<T>*)w)->color==RED)
{
((RBTree<T>*)w)->color=BLACK;
((RBTree<T>*)prev)->color=RED;
rotateRight((RBTree<T>*)prev);
if(prev!=NULL)w=prev->left;
}
if (w&&w->left&&w->right&&((RBTree<T>*)w->right)->color==BLACK&&((RBTree<T>*)w->left)->color==BLACK)
{
((RBTree<T>*)w)->color=RED;
x=prev;
}
else
{
if (w&&w->left&&((RBTree<T>*)w->left)->color==BLACK)
{
if(w->right)((RBTree<T>*)w->right)->color=BLACK;
((RBTree<T>*)w)->color=RED;
rotateLeft((RBTree<T>*)w);
if(prev!=NULL)w=prev->left;
}
if(w)((RBTree<T>*)w)->color=((RBTree<T>*)prev)->color;
((RBTree<T>*)prev)->color=BLACK;
if(w&&w->left)((RBTree<T>*)w->left)->color=BLACK;
rotateRight((RBTree<T>*)prev);
x=root;
}
DelFix(x, prev);
}
}
/******
* Находим место для узла и вставляем в дерево *
* Делаем балансировку и перекраску если это *
* необходимо *
*******/
void SubInclude(RBTree<T> *temp, T _dat)//включение значения
{
if(temp->dat>_dat && temp->left==NULL)
{
RBTree<T> *New=new RBTree<T>(_dat);//новый объект
temp->left=New;//установка связей с предком
temp->left->parent=temp;
New->color=RED;//красим в красный(по правилу RBTree)
InsertFixUp(New);//балансируем и красим, если необходимо
return ;
}
if(temp->dat<_dat && temp->right==NULL)
{
RBTree<T> *New=new RBTree<T>(_dat);
temp->right=New;//установка связей с предком
temp->right->parent=temp;
New->color=RED;//красим в красный(по правилу RBTree)
InsertFixUp(New);//балансируем и красим, если необходимо
return ;
}
if(temp->dat>_dat)//елси меньше, то влево
{
SubInclude((RBTree<T>*)temp->left,_dat);
}
if(temp->dat<_dat)//если больше, то вправо
{
SubInclude((RBTree<T>*)temp->right,_dat);
}
ins++;
}
//Рекурсивная ф-я перекраски и балансировки
void InsertFixUp(RBTree<T> *x)
{
ins++;
//условие выхода
if(!(x!= root && ((RBTree<T>*)x->parent)->color==RED)) return ;
if(x->parent == x->parent->parent->left)//левая ветвь
{
RBTree<T> *y = ((RBTree<T>*)x->parent->parent->right);
if(y!=NULL && y->color == RED)// "Дядя" - RED
{
((RBTree<T>*)x->parent)->color = BLACK;//цвет предка ЧЕРН.
y->color = BLACK;//Дядин цвет ЧЕРН.
((RBTree<T>*)x->parent->parent)->color = RED;
x=((RBTree<T>*)x->parent->parent);
InsertFixUp(x);//на 2-а узла выше
}
else // Дядя - BLACK
{
if (x == x->parent->right)
{
//делаем правым потомком
x = (RBTree<T>*)x->parent;
rotateLeft(x);
}
// перекраска и вращение
((RBTree<T>*)x->parent)->color = BLACK;
((RBTree<T>*)x->parent->parent)->color = RED;
rotateRight((RBTree<T>*)x->parent->parent);
InsertFixUp(x);
}
}
else // правая ветвь
{
// "зеркальный" код
RBTree<T> *y = (RBTree<T>*)x->parent->parent->left;
if (y!=NULL && y->color == RED)
{
// Дядя - RED
((RBTree<T>*)x->parent)->color = BLACK;
y->color = BLACK;
((RBTree<T>*)x->parent->parent)->color = RED;
x =(RBTree<T>*)x->parent->parent;
InsertFixUp(x);
}
else
{
// Дядя - BLACK
if (x == x->parent->left)
{
x =(RBTree<T>*) x->parent;
rotateRight(x);
}
((RBTree<T>*)x->parent)->color = BLACK;
((RBTree<T>*)x->parent->parent)->color = RED;
rotateLeft((RBTree<T>*)x->parent->parent);
InsertFixUp(x);
}
}
}
/*******
* Функции поворотов узлов *
/
void rotateLeft(RBTree <T>*t)//поворот влево
{
RBTree <T>*y=(RBTree<T>*)t->right;
if(y)t->right=y->left;
else t->right=NULL;
if(y&&y->left!=NULL)y->left->parent=t;
if(y!=NULL)y->parent=t->parent;
if(t->parent)
{
if (t==t->parent->left)
t->parent->left=y;
else
t->parent->right=y;
} else
{
root=y;
root->parent=0;
}
if(y)y->left = t;
if (t)t->parent=y;
}
void rotateRight(RBTree <T>*t)//поворот вправо
{
RBTree <T>*y=(RBTree<T>*)t->left;
if(y)t->left=y->right;
else t->left=NULL;
if (y&&y->right!=NULL)y->right->parent=t;
if (y!=NULL)y->parent=t->parent;
if (t->parent)
{
if (t==t->parent->right) t->parent->right=y;
else t->parent->left=y;
}
else
{
root=y;
root->parent=0;
}
if(y)y->right=t;
if(t!=NULL)t->parent=y;
}
void PrintTreeSub(RBTree<T> *t, int tmp)//Рекурсивная функция
{ //вывода RB - дерева
if(!t)return;
if(t->right)PrintTreeSub((RBTree<T>*)t->right, tmp+2);
if(t->color)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED);
else SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_BLUE|FOREGROUND_INTENSITY);
for(int i=0;i<2*tmp;i++) cout<<' ';
cout<<t->dat<<" "<<endl;
if(t->left)PrintTreeSub((RBTree<T>*)t->left, tmp+2); SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
}};
