SDiZO, lab5 Drzewo AVL (dodawanie)

gistfile1.c

#include<iostream>
#include<time.h>
#include<vector>

using namespace std;

int n;

struct drzewo{
	int key,balance;
	drzewo *left, *right, *parent;
};

drzewo *korzen = NULL;

void ini()
{
	korzen = NULL;
}

drzewo* find(int key)
{
	drzewo *tmp;
	tmp = korzen;
	while(tmp)
	{
		if(key == tmp->key)
		{
			return tmp;
		}
		if(tmp->key < key)
		{
			tmp = tmp->right;
		}
		else tmp = tmp->left;
	}
	cout << "Nie ma takiego elementu" << endl;;
	return(0);
}

drzewo* find_r(int key, drzewo *&grand, drzewo *&parent, drzewo *&child)
{
	drzewo *tmp;
	tmp = korzen;
	grand = parent = NULL;
	int i = 0;
	while(tmp)
	{
		i++;
		if(key == tmp->key)
		{
			child = tmp;
			return tmp;
		}
		if(i >= 2 && parent != NULL)
		grand = parent;
		parent = tmp;
		if(tmp->key < key)
		{
			tmp = tmp->right;
		}
		else tmp = tmp->left;
	}
	cout << "Nie ma takiego elementu" << endl;;
	return(0);
}

drzewo* find_min(drzewo *node)
{
	while(node->left != NULL)
	{
		node = node->left;
	}
	return node;
}

drzewo* find_max(drzewo *node)
{
	while(node->right != NULL)
	{
		node = node->right;
	}
	return node;
}

drzewo* find_suc(drzewo *node)
{
	drzewo *tmp, *tmp_par;
	if (node->right != NULL)
		return(find_min(node->right));
	drzewo *ptr = korzen;
	vector<drzewo*> stos;
	stos.push_back(korzen);
	while(ptr->key != node->key)
	{
		if(ptr->key < node->key)
		{
			ptr = ptr->right;
		}
		else ptr = ptr->left;
		stos.push_back(ptr);
	}
	stos.pop_back();
	tmp_par=stos.back();
	stos.pop_back();
	tmp=node;
	while((tmp_par!=NULL) && (tmp==(tmp_par->right)))
	{
		tmp=tmp_par;
		tmp_par=stos.back();
	}
	stos.clear();
	return tmp_par;
}

drzewo* find_pre(drzewo *node)
{
	drzewo *tmp, *tmp_par;
	if (node->left != NULL)
		return(find_max(node->left));
	drzewo *ptr = korzen;
	vector<drzewo*> stos;
	stos.push_back(korzen);
	while(ptr->key != node->key)
	{
		if(ptr->key < node->key)
		{
			ptr = ptr->right;
		}
		else ptr = ptr->left;
		stos.push_back(ptr);
	}
	stos.pop_back();
	tmp_par=stos.back();
	stos.pop_back();
	tmp=node;
	while((tmp_par!=NULL) && (tmp==(tmp_par->left)))
	{
		tmp=tmp_par;
		tmp_par=stos.back();
	}
	stos.clear();
	return tmp_par;
}

void walk(drzewo *node)
{
	cout << node->key << " : Left-> ";
	if(node->left) cout << node->left->key;
	else        cout << "NULL";
	cout << ", Right-> ";
	if(node->right) cout << node->right->key;
	else         cout << "NULL";
	cout << endl;
	if(node->left)  walk(node->left);
	if(node->right) walk(node->right);
}

void rot_r(drzewo *grand_father, drzewo *parent, drzewo *child)
{
	drzewo *tmp;
	if(child == korzen)
	{
		cout<<"Nie mozna rotowac korzenia";
		system("pause");
		return;
	}
	if(child == parent->right)
	{
		cout<<"Nie mozna rotowac w prawo";
		system("pause");
		return;
	}
	if(grand_father != NULL)
	{
		if(grand_father->right==parent)
			grand_father->right=child;
		else 
			grand_father->left=child;
	}
	else
		korzen = child;
	tmp=child->right;
	child->right=parent;
	parent->left=tmp;
}

void rot_l(drzewo *grand_father, drzewo *parent, drzewo *child)
{
	drzewo *tmp;
	if(child == korzen)
	{
		cout<<"Nie mozna rotowac korzenia";
		system("pause");
		return;
	}
	if(child == parent->left)
	{
		cout<<"Nie mozna rotowac w lewo";
		system("pause");
		return;
	}
	if(grand_father != NULL)
	{
		if(grand_father->left==parent)
			grand_father->left=child;
		else grand_father->right=child;
	}
	else
		korzen = child;
	tmp=child->left;
	child->left=parent;
	parent->right=tmp;
}

drzewo* rot_rr(drzewo *&korzen, drzewo *node)
{

	drzewo *B = node->right, *P = node->parent;

	node->right = B->left;
	if(node->right) node->right->parent = node;
	B->left = node;
	B->parent = P;
	node->parent = B;
	if(P)
	{
		if(P->left == node) P->left = B; else P->right = B;
	}
	else korzen = B;

	if(B->balance == -1)
	{
		node->balance = B->balance = 0;
	}
	else
	{
		node->balance = -1; B->balance = 1;
	}
	return B;
}

drzewo* rot_ll(drzewo *&korzen, drzewo *node)
{
	drzewo *B = node->left, *P = node->parent;

	node->left = B->right;
	if(node->left) node->left->parent = node;
	B->right = node;
	B->parent = P;
	node->parent = B;
	if(P)
	{
		if(P->left == node) P->left = B; else P->right = B;
	}
	else korzen = B;

	if(B->balance == 1)
	{
		node->balance = B->balance = 0;
	}
	else
	{
		node->balance = 1; B->balance = -1;
	}
	return B;
}

drzewo* rot_rl(drzewo *&korzen, drzewo *node)
{
	drzewo *B = node->right, *C = B->left, *P = node->parent;

	B->left = C->right;
	if(B->left) B->left->parent = B;
	node->right = C->left;
	if(node->right) node->right->parent = node;
	C->left = node;
	C->right = B;
	node->parent = B->parent = C;
	C->parent = P;
	if(P)
	{
		if(P->left == node) P->left = C; else P->right = C;
	}
	else korzen = C;

	node->balance = (C->balance == -1) ?  1 : 0;
	B->balance = (C->balance ==  1) ? -1 : 0;
	C->balance = 0;

	return C;
}

drzewo* rot_lr(drzewo *&korzen, drzewo *node)
{
	drzewo* B = node->left, * C = B->right, * P = node->parent;

	B->right = C->left;
	if(B->right) B->right->parent = B;
	node->left = C->right;
	if(node->left) node->left->parent = node;
	C->right = node;
	C->left = B;
	node->parent = B->parent = C;
	C->parent = P;
	if(P)
	{
		if(P->left == node) P->left = C; else P->right = C;
	}
	else korzen = C;

	node->balance = (C->balance ==  1) ? -1 : 0;
	B->balance = (C->balance == -1) ?  1 : 0;
	C->balance = 0;

	return C;
}

drzewo* new_node(int key)
{
	drzewo *node;
	node = new drzewo;
	node->key=key;
	return node;
}

drzewo* new_node_r()
{
	return new_node(rand()%100);
}

bool add(drzewo *&korzen, drzewo *node)
{
	drzewo *x = korzen, *y, *z;

	y = node->left = node->right = NULL;
	node->balance = 0;

	while(x)
	{
		if(x->key == node->key)
		{
			delete node;
			return false;
		}
	y = x;
	x = (node->key < x->key) ? x->left : x->right;
	}

	if(!(node->parent = y))
	{
		korzen = node;
		return true;
	}

	if(node->key < y->key) y->left = node; else y->right = node;
	if(y->balance)
	{
		y->balance = 0;
		return true;
	}
	y->balance = (y->left == node) ? 1 : -1;
	z = y->parent;
	while(z)
	{
		if(z->balance) break;
		z->balance = (z->left == y) ? 1 : -1;
		y = z; z = z->parent;
	}

	if(!z) return true;

	if(z->balance == 1)
	{
		if(z->right == y)
		{
			z->balance = 0;
			return true;
		}
		if(y->balance == -1) rot_lr(korzen,z); else rot_ll(korzen,z);
		return true;
	}
	else
	{
		if(z->left == y)
	{
		z->balance = 0;
		return true;
	}
		if(y->balance == 1) rot_rl(korzen,z); else rot_rr(korzen,z);
		return true;
	}
}

drzewo* del(drzewo *&korzen, drzewo *node)
{
	drzewo *t, *y, *z;
	bool nest;

	if((node->left) && (node->right))
	{
		y = del(korzen,find_pre(node));
		nest = false;
	}
	else
	{
		if(node->left)
		{
			y = node->left; node->left = NULL;
		}
		else
		{
			y = node->right; node->right = NULL;
		}
		node->balance = 0;
		nest = true;
	}

	if(y)
	{
		y->parent = node->parent;
		if(y->left  = node->left)  y->left->parent  = y;
		if(y->right = node->right) y->right->parent = y;
		y->balance = node->balance;
	}

	if(node->parent)
	{
		if(node->parent->left == node) node->parent->left = y; else node->parent->right = y;
	}
	else korzen = y;

	if(nest)
	{
		z = y;
		y = node->parent;
		while(y)
		{
			if(!(y->balance))
			{

				// bf(y) = 0, czyli węzeł y był w stanie równowagi przed usunięciem węzła x w jednym z jego poddrzew. 

				y->balance = (y->left == z) ? -1 : 1;
				break;
			}
			else
			{
				if(((y->balance ==  1) && (y->left  == z)) || ((y->balance == -1) && (y->right == z)))
				{

					// bf(y) ? 0 i skrócone zostało cięższe poddrzewo.

					y->balance = 0;
					z = y; y = y->parent;
				}
				else
				{
					t = (y->left == z) ? y->right : y->left;
					if(!(t->balance))
					{

						//współczynnik balance(t) dziecka węzła y w cięższym poddrzewie jest równy 0.

						if(y->balance == 1) rot_ll(korzen, y); else rot_rr(korzen, y);
						break;                      
					}
					else if(y->balance == t->balance)
					{

						// Współczynnik bf(y) jest taki sam jak współczynnik bf(t).

						if(y->balance == 1) rot_ll(korzen, y); else rot_rr(korzen, y);
						z = t; y = t->parent;            
					}
					else
					{

						// Współczynniki bf(y) i bf(t) są przeciwne.

						if(y->balance == 1) rot_lr(korzen, y); else rot_rl(korzen, y);
						z = y->parent; y = z->parent;              
					}
				}
			}
		}
	}
	return node;
}

int menu()
{
	system("CLS");
	int i,j,w;
	cout << "1.Dodaj element" << endl;
	cout << "2.Znajdz" << endl;
	cout << "3.Usun" << endl;
	cout << "4.Rotuj" << endl;
	cout << "5.Wyswetl" << endl;
	cout << "6.Wyjdz" << endl;
	cin >> i;
	switch(i)
	{
	case 1:
		system("CLS");
		cout << "1.Dodaj wartosc" << endl;
		cout << "2.Dodaj losowe wezly" << endl;
		cin >> j;
		switch(j)
		{
		case 1:
			system("CLS");
			cout << "Podaj wartosc: ";
			cin >> w;
			add(korzen,new_node(w));
			menu();
			break;
		case 2:
			system("CLS");
			cout << "Podaj ilosc wezlow: ";
			cin >> w;
			for (int k=0; k<w;k++)
			{
				add(korzen,new_node_r());
			}
			menu();
			break;
		}
		break;
	case 2:
		system("CLS");
		cout << "Podaj klucz: ";
		cin >> j;
		cout << find(j) << endl;
		system("pause");
		menu();
		break;
	case 3:
		system("CLS");
		cout << "Podaj klucz: ";
		cin >> j;
		del(korzen,find(j));
		menu();
		break;
	case 4:
		drzewo *gp, *p, *c;
		system("CLS");
		cout << "Podaj kierunek rotacji" << endl;
		cout << "1.Prawo" << endl;
		cout << "2.Lewo" << endl;
		cin >> j;
		switch(j)
		{
		case 1:
			system("CLS");
			cout << "Podaj klucz: ";
			cin >> w;
			find_r(w,*&gp,*&p, *&c);
			rot_r(gp,p,c);
			menu();
			break;
		case 2:
			system("CLS");
			cout << "Podaj klucz: ";
			cin >> w;
			find_r(w,*&gp,*&p,*&c);
			rot_l(gp,p,c);
			menu();
			break;
		}
		break;
	case 5:
		system("CLS");
		walk(korzen);
		system("pause");
		menu();
		break;
	case 6:
		exit(0);
	}
}

int main()
{
	srand(time(NULL));
	menu();
}