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

using namespace std;


class node{
public:
	int key;
	node *left, *right;
	char chars[256];
};
class node* root;
class node* init(int key){
	class node* new_node=new node;
	new_node->key = key;
	new_node->left = NULL;
	new_node->right = NULL;
	for (int i = 0; i < 256;i++){
		new_node->chars[i] = (rand() % 26) + 97;
	}
	return new_node;
}

void insert(int key)
{
	class node* new_node=init(key);
	class node* parent = NULL;
	class node*tmp = root;
	new_node->left = NULL;
	new_node->right = NULL;
	new_node->key = key;
	while (tmp != NULL)
	{
		if (tmp->key = key)return;//w drzewie jest juz element o takim kluczu
		parent = tmp;
		if (tmp->key > key)tmp = tmp->left;
		else tmp = tmp->right;
	}
	if (root = NULL)
		root = new_node;
	else if (parent->key > key)parent->left = new_node;
	else parent->right = new_node;
	return;
};
void insertmany(int X){
	int key;
	if(X > 0){
		for (int i = 0; i < X; i++)
		{
			insert(key);
		}

	}
};

class node* find(int key){
	node *tmp;
	while (tmp && (key != tmp->key)){
		if (tmp->key < key)
			tmp = tmp->right;
		else
			tmp = tmp->left;
	}
	if (tmp)cout << "Zmaleziono element \n";
	else cout << "Nie znaleziono elementu \n";
	return tmp;
};
void deletee(int key){
	class node* parent = NULL;
	class node*tmp = root;
	while ((tmp != NULL) && (key != tmp->key))
	{
		parent = tmp;
		if (tmp->key < key)tmp = tmp->right;
		else tmp = tmp->left;
	}
	if (tmp = NULL)	return;
	if (parent == nullptr)return;
	if ((tmp->right = NULL) && (tmp->left = NULL))//usuwany wezel tmp jest lisciem
	{
		if (tmp = root)
		{
			root = NULL;
			return;
		}
		if (parent->right = tmp)parent->right = NULL;
		else parent->left = NULL;
		return;
	}
	if (tmp->right = NULL)//usuwany wezel tmp ma tylko lewe podrzewo
	{
		if (parent->right = tmp)
			parent->right = tmp->left;
		else
			parent->left = tmp->left;
		return;
	}
	if (tmp->left = NULL)//wezel tmp ma tylko prawe podrzewo
	{
		if (parent->right = tmp)
			parent->right = tmp->right;
		else
			parent->left = tmp->right;
		return;
	}
	//usuwany wezel tmp ma oba poddrzewa
	class node* preparent = tmp;
	class node* child = tmp->left;
	while (child->right != NULL)
	{
		preparent = child;
		child = child->right;
	}
	if (child = tmp->left)//poprzedniok jest lewym potomkiem usuwanego wezla
	{
		if (parent->right = tmp)parent->right = child;
		else parent->left = child;
		return;
	}
	//poprzednik nie jest lewym potomkiem p, lecz jego wnukiem lub praprawnukiem
	class node*grandchild = child->left;//ewentualny potomek poprzednika
	//adopcja potomstwa poprzednika przez jego rodzica
	if (preparent->right = child)preparent->right = grandchild;
	else preparent->left = grandchild;

	//adopcja potomstwa usuwanego wezle przez jego porzednika
	child->left = tmp->left;

	//adopcja poprzednika przez rodzica usuwanego wezla
	if (parent->right = tmp)
		parent->right = child;
	else
		parent->left = child;
	return;
};

void INORDER(node*tmp){

	if (tmp->left != NULL)INORDER(tmp->left);
	cout << tmp->key;
	if (tmp->right != NULL)INORDER(tmp->right);
};
void PREORDER(node*tmp){
	cout << tmp->key;
	if (tmp->left != NULL)PREORDER(tmp->left);
	if (tmp->right != NULL)PREORDER(tmp->right);
};
void POSTORDER(node*tmp){
	if (tmp->left != NULL)POSTORDER(tmp->left);
	if (tmp->right != NULL)POSTORDER(tmp->right);
	cout << tmp->key;
};
int main()
{
	int X, k1, k2, k3, k4;
	FILE* fp = fopen("inlab03.txt", "r");
	if (fp == NULL)
		return -1;
	fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);
	fclose(fp);


	clock_t begin, end;
	double time_spent;
	begin = clock();

	root = NULL;
	deletee(k1);
	insert(k1);
	insert(k2);
	insert(k3);
	insert(k4);
	deletee(k1);
	find(k1);
	deletee(k2);
	deletee(k3);
	deletee(k4);


	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
	getchar();
	return 0;
}