Содержание
Введение 3
Процедуры двоичного дерева 4
Красно-черные деревья 6
Вращения 7
Добавление вершины 9
Удаление вершины 12
Заключение 17
Введение
Деревья поиска(search trees) позволяют выполнять операции с динамическими множествами: Search(поиск), Minimum(минимум), Maximum(максимум), Predcessor(предыдущий), Successor(следующий), Insert(вставить) и Delete(удалить).Таким образом, дерево поиска может быть использовано и как словарь, и как очередь с приоритетами.
Время выполнения основных операций пропорционально высоте дерева. Если двоичное дерево ‘плотно заполнено’, то его высота пропорциональна логарифму числа вершин. Напротив, если дерево представляет собой линейную цепочку из n вершин, это время вырастет до 
.Высота случайного двоичного дерева поиска есть 
, так что в этом случае время выполнения основных операций есть 
.
Конечно, возникающие на практике двоичные поиска могут быть далеки от случайных. Однако, приняв специальные меры по балансировке деревьев, мы можем гарантировать, что высота с n вершинами будет . В данной курсовой работе рассмотрен один из таких подходов – красно-черные деревья.
Функции двоичного дерева поиска
В данном разделе описаны процедуры стандартных деревьев двоичного поиска, и приведены соответствующие части программы курсовой работы, выполненной на С++. Данные процедуры необходимы для процедур красно – черных деревьев.
Процедура InorderTreeWalk(x) x – корень дерева, которое необходимо напечатать если x=root, то процедура печатает все дерево.
void tree::InorderTreeWalk(int x){
if(x!=NIL){
cout <<"\n";
cout <<"Вершина:"<<x<<" Родитель:"<<p[x];
cout <<" Левый сын: "<<left[x]<<" Правый сын:"<<right[x];
InorderTreeWalk(left[x]);
InorderTreeWalk(right[x]);}}
Если корень не является пустым листом, то выдается информация о нем о его родителе, и его сыновьях.
Свойство упорядоченности деревьев двоичного поиска:
Процедура TreeMinimum возвращает значение наименьшего корня дерева. Процедура проходит по всем указателям left от корня пока не находит корень левым сыном которого является NIL.
int tree::TreeMinimum(int x){
while(left[x]!=NIL)
{x=left[x];}
return x;}
Процедура TreeSuccessor возвращает следующий за х элемент. Процедура TreeSuccessor отдельно рассматривает 2 случая. Если правое поддерево вершины х непусто, то следующий за х элемент – минимальный элемент в этом поддереве равен TreeMinimum(right[x]).
Пусть теперь правое поддерево вершины х пусто. Тогда мы идем от х вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель и будет искомым элементом
int tree::TreeSuccessor(int x){
int y;
//Если правое поддерево вершины х непусто.
if(right[x]!=NIL){
return TreeMinimum(right[x]);}
y=p[x];
//Если правое поддерево вершины х пусто.
while((y!=NIL)&(x=right[y])){
x=y;
y=p[y];}
return y;}
Процедура InsertTree(z) добавляет заданный элемент в подходящее место дерева. Параметром процедуры является указатель на новую вершину, в которую помещены значения left[z]=NIL и right[z]=NIL. В ходе работы процедура меняет дерево и некоторые поля вершины z, после чего новая вершина с данным значением оказывается вставленной в подходящее место дерева.
Процедура двигается вниз по дереву, начав с его корня. При этом в вершине y сохраняется указатель на родителя вершины х. Сравнивая z c x процедура решает куда идти – налево или направо. Процесс завершается когда x становится равным NIL.Этот NIL стоит как раз там, куда надо поместить z.
void tree::InsertTree(int z){
int y,x;
y=NIL;
x=root;
//Процедура двигается вниз по дереву начав с его корня
while(x!=NIL){
y=x;
if(z<x){x=left[x];}
else{x=right[x];}}
//Процедура помещает z в подходящее место дерева
p[z]=y;
if(y==NIL){
root=z;}
else{if(z<y){
left[y]=z;}
else{right[y]=z;}}}