RBT

#include <iostream>
#include <string>

using namespace std;

struct tree
{
	int inf;
	string color;
	tree *right ;
	tree *left ;
	tree *parent;
};

void RotateLeft(tree *tr);
void RotateRight(tree *tr);

tree *node(int x) //начальный узел
{
	tree *n = new tree;
	n->color = "red";
	n->inf = x;
	n->left = n->right = NULL;
	n->parent = NULL;
	return n;
}

void insert(tree *&tr, int x) //вставка
{
	tree *n = node(x);
	if (!tr )
		tr = n; //если дерево пустое - корень
	else
	{
		tree *y = tr;
		while(y)
		{ //ищем куда вставлять
			if (n->inf > y->inf) //правая ветка
				if (y->right)
					y = y->right;
				else
				{
					n->parent = y; //узел становится правым ребенком
					y->right = n;
					break;
				}
				else
					if (n->inf < y->inf)//левая ветка
						if (y->left)
							y = y->left;
						else
						{
							n->parent = y;//узел становится левым ребенком
							y->left = n;
							break;
						}
		}
	}

	while((tr->parent != NULL) && (tr->parent->color == "red"))
	{
		tree *y = tr;
		if (tr->parent = tr->parent->parent->left)
		{
			y = tr->parent->parent->right;
			if (y->color == "red")
			{
				tr->parent->color = "black";
				y->color = "black";
				tr->parent->parent->color = "red";
				tr = tr->parent->parent;
			}
			else
			{
				if (tr = tr->parent->right)
				{
					tr = tr->parent;
					RotateLeft(tr);
				}
				tr->parent->color = "black";
				tr->parent->parent->color = "red";
				RotateRight(tr->parent->parent);
			}
		}
		else
		{
			y = tr->parent->parent->left;
			if (y->color == "red")
			{
				tr->parent->color = "black";
				y->color = "black";
				tr->parent->parent->color = "red";
				tr = tr->parent->parent;
			}
			else
			{
				if (tr = tr->parent->left)
				{
					tr = tr->parent;
					RotateLeft(tr);
				}
				tr->parent->color = "black";
				tr->parent->parent->color = "red";
				RotateRight(tr->parent->parent);
			}
		}
	}
	tr->color = "black";
}

void RotateLeft(tree *tr)
{
	tree *y = tr->right;
	tr->right = tr->left;

	if (y->left != NULL)
		tr->parent->left = tr;
	y->parent = tr->parent;
	if (tr->parent == NULL)
		tr = y;
	else
	{
		if(tr == tr->parent->left)
			tr->parent->left = y;
		else
			tr->parent->right = y;
	}
	y->left = tr;
	tr->parent = y;
}

void RotateRight(tree *tr)
{
	tree *y = tr->left;
	tr->left = tr->right;

	if (y->left != NULL)
		tr->parent->left = tr;
	y->parent = tr->parent;
	if (tr->parent == NULL)
		tr = y;
	else
	{
		if(tr == tr->parent->left)
			tr->parent->left = y;
		else
			tr->parent->right = y;
	}
	y->right = tr;
	tr->parent = y;
}

void preorder (tree *tr)
{ // прямой обход (К-Л-П)
	if (tr)
	{
		cout << tr->inf << " " << tr->color << endl; //корень
		preorder( tr->left); //левое
		preorder( tr->right); //правое
	}
}

void postorder (tree *tr)
{ // обратный обход (Л-П-К)
	if (tr)
	{
		postorder( tr->left); //левое
		postorder( tr->right); //правое
		cout << tr->inf << " " << tr->color << endl; //корень
	}
}


void inorder(tree *tr)
{// симметричный обход (Л-К-П)
	if(tr)
	{
		inorder ( tr->left); //левое
		cout << tr->inf << " " << tr->color << endl; //корень
		inorder ( tr->right); //правое
	}
}

tree *find( tree *tr, int x)
{//поиск
	if (! tr || x == tr->inf)//нашли или дошли до конца ветки
		return tr;
	if (x < tr->inf)
		return find(tr->left, x);//ищем по левой ветке
	else
		return find(tr->right, x);//ищем по правой ветке
}

tree *Min(tree *tr)
{//поиск min
	if (! tr->left)
		return tr;//нет левого ребенка
	else
		return Min(tr->left);//идем по левой ветке до конца
}

tree *Max(tree *tr)
{//поиск max
	if (! tr->right)
		return tr;//нет правого ребенка
	else
		return Max(tr->right);//идем по правой ветке до конца
}

tree *Next(tree*tr, int x)
{//поиск следующего
	tree* n = find( tr , x);
	if (n->right)//если есть правый ребенок
		return Min(n->right);//min по правой ветке
	tree *y = n->parent; //родитель
	while (y && n == y->right)
	{//пока не дошли до корня или узел - правый ребенок
		n = y;//идем вверх по дереву
		y = y->parent;
	}
	return y;//возвращаем родителя
}

tree *Prev(tree *tr, int x)
{//поиск предыдущего
	tree *n = find(tr , x);
	if (n->left)//если есть левый ребенок
		return Max(n->left);//max по левой ветке
	tree *y = n->parent;//родитель
	while(y && n == y->left)
	{//пока не дошли до корня или узел - левый ребенок
		n = y;//идем вверх по дереву
		y = y->parent;
	}
	return y;//возвращаем родителя
}


void Delete(tree *&tr, tree *v)
{//удаление узла
	tree *p = v->parent;
	if (!p)
		tr = NULL; //дерево содержит один узел
	else if (!v->left && !v->right)
	{//если нет детей
		if (p->left == v) //указатель у родителя меняем на NULL
			p->left = NULL;
		if (p->right == v)
			p->right = NULL;
		delete v;
	}
	else if (!v->left || !v->right)
	{//если только один ребенок
		if (!p)
		{ //если удаляем корень, у которого 1 ребенок
			if (!v->left)
			{ //если есть правый ребенок
				tr = v->right; //он становится корнем
				v->parent = NULL;
			}
			else
			{ //аналогично для левого
				tr = v->left;
				v->parent = NULL;
			}
		}
		else
		{
			if (!v->left)
			{//если есть правый ребенок
				if (p->left == v) //если удаляемый узел явл. левым ребенком
					p->left = v->right; //ребенок удаляемого узла становится левым ребенком своего "деда"
				else
					p->right = v->right; ////ребенок удаляемого узла становится правым ребенком своего "деда"
				v->right->parent = p; //родителем ребенка становится его "дед"
			}
			else
			{//аналогично для левого ребенка
				if (p->left == v)
					p->left = v->left;
				else
					p->right = v->left;
					v->left->parent = p;
			}
	delete v;
		}
	}
	else
	{//есть оба ребенка
		tree *succ = Next(tr, v->inf);//следующий за удаляемым узлом
		v->inf = succ->inf; //присваиваем значение
		if (succ->parent->left ==succ)
		{//если succ левый ребенок
			succ->parent->left = succ->right; //его правый ребенок становится левым ребенком своего "деда"
			if (succ->right) //если этот ребенок существует
			succ->right->parent = succ->parent; //его родителем становится "дед"
		}
		else
		{//аналогично если succ - правый ребенок
			succ->parent->right = succ->right;
			if (succ->right)
				succ->right->parent = succ->parent;
		}
		delete succ;
	}
}


int main()
{
	setlocale(LC_ALL,"RUS");
	int n, x;
	cout << "n=";
	cin >> n;
	tree *tr = NULL;
	for(int i = 0; i < n; i++) // 10: 65 74 32 1 45 78 69 12 85 36
	{
		cout << i <<": ";
		cin >> x;
		if(find(tr, x))
		{
			cout << "Такой элемент уже есть" << endl;
			i--;
		}
		else
		{
			insert (tr, x);
		}
	}
	cout <<	"Прямой обход" << endl;
	preorder(tr);
	cout << endl;

	cout << "Обратный обход" << endl;
	postorder(tr);
	cout << endl;

	cout << "Симметричный обход" << endl;
	inorder(tr);
	cout << endl;

	cout << "min = " << Min(tr)->inf << endl;
	cout << "max = " << Max(tr)->inf << endl;
	cout << "x = ";
	cin >> x;
	if (find(tr, x))
	{
		cout << "Следующий = " << Next(tr, x)->inf << endl;
		cout << "Предыдущий = " << Prev(tr, x)->inf << endl;
		Delete(tr, find(tr, x));

		cout <<	"Прямой обход" << endl;
		preorder(tr);
		cout << endl;

		cout << "Обратный обход" << endl;
		postorder(tr);
		cout << endl;

		cout << "Симметричный обход" << endl;
		inorder(tr);
		cout << endl;
	}
	else
		cout << "Такого элемента нет" << endl;
	system("pause");
	return 0;
}