BST

//SDIZO I1 213A LAB05
//Mateusz Rynkiewicz
//rm39424@zut.edu.pl
#define _CRTDBG_MAP_ALLOC
#include "stdafx.h"
#include <string>
#include <iostream>
#include <ctype.h>
#include <time.h>
//mniejszy element, klucz, wiekszy element

struct Wezel {
	int a;
	Wezel* left;
	Wezel* right;
};


Wezel* Nowy() {
	Wezel* korzen = (Wezel*)malloc(sizeof(Wezel));
	korzen->a = NULL;
	korzen->left = NULL;
	korzen->right = NULL;
	return korzen;
}
Wezel* Nowy(int i) {
	Wezel* korzen = (Wezel*)malloc(sizeof(Wezel));
	korzen->a = i;
	korzen->left = NULL;
	korzen->right = NULL;
	return korzen;
}

Wezel* DodajElement(Wezel* korzen, int klucz, bool &check) {
	Wezel* kopia = korzen;
	check = true;
	if (korzen == NULL) {
		korzen = Nowy(klucz);
		return korzen;
	}
go:
	if (korzen->a == klucz) {
		//std::cout << "Element znajduje sie juz w drzewie" << std::endl;
		check = false;
		return kopia;
	}
	else {
		if (korzen->a > klucz) {
			if (korzen->left == NULL) {
				korzen->left = Nowy(klucz);
				return kopia;
			}korzen = korzen->left;
			goto go;
		}
		else {
			if (korzen->right == NULL) {
				korzen->right = Nowy(klucz);
				return kopia;
			}
			korzen = korzen->right;
			goto go;
		}
	}

}

bool SzukajElement(Wezel* korzen, int klucz) {
	for (;;) {
		if (korzen == NULL) {
			//std::cout << "Nie znaleziono elementu o kluczu: " << klucz << std::endl;
			return false;
		}
		if (korzen->a == klucz) {
			//std::cout << "Znaleziono element o kluczu: " << klucz << std::endl;
			return true;
		}
		if (korzen->a > klucz) {
			korzen = korzen->left;
		}
		else if (korzen->a < klucz) {
			korzen = korzen->right;
		}

	}
}
Wezel* WstawX(Wezel* korzen, int x, int &count) {
	int w;
	bool check = false;
	count = 0;
	for (int i = 0; i <x; i++) {
		//std::cout << "wstawiono: " << w << std::endl;

		w = (rand() % 25000) * 4 + (rand() % 4);


		korzen = DodajElement(korzen, w, check);
		if (check)count++;
		check = false;
	}
	return korzen;
}
Wezel* WstawX2(Wezel* korzen, int x, int &count) {
	int w;
	x = x / 2;
	bool check = false;
	count = 0;
	for (int i = 0; i < x; i++) {
		//std::cout << "wstawiono: " << w << std::endl;

		w = (rand() % 25000) * 4 + (rand() % 4);
		korzen = DodajElement(korzen, w, check);
		if (check)count++;
		check = false;
		korzen = DodajElement(korzen, i + 1, check);
		if (check)count++;
		check = false;
	}
	return korzen;
}


//nierekurencyjnie

Wezel* UsunElement(Wezel* korzen, int klucz, bool &check) {
	Wezel* kopia = korzen;
	check = true;
	////0 elementow
	if (korzen == NULL)return NULL;
	if (korzen->a == klucz && korzen->left == NULL && korzen->right == NULL) {
		free(korzen);
		check = false;
		return NULL;
	}
	////Usuwamy 1 element
go:
	if (korzen->a == klucz) {

		//2xNULL
		if (korzen->left == NULL && korzen->right == NULL) {
			free(korzen);
			return kopia;
		}
		//1xNULL
		if (korzen->left != NULL && korzen->right == NULL) {
			Wezel* temp = korzen->left;
			korzen->a = temp->a;
			korzen->left = temp->left;
			korzen->right = temp->right;
			free(temp);
			return kopia;
		}
		if (korzen->left == NULL && korzen->right != NULL) {
			Wezel* temp = korzen->right;
			korzen->a = temp->a;
			korzen->left = temp->left;
			korzen->right = temp->right;
			free(temp);
			return kopia;
		}
		//0xNULL
		if (korzen->left != NULL && korzen->right != NULL) {
			Wezel* temp = korzen;
			//od razu po lewej jest lisc
			if (temp->left->right == NULL) {
				temp = korzen->left;
				korzen->a = temp->a;
				korzen->left = temp->left;
				free(temp);
				return kopia;
			}
			temp = temp->left;
			for (;;) {
				if (temp->right->right == NULL)break;
				temp = temp->right;
			}
			korzen->a = temp->right->a;
			Wezel* temp2 = temp->right;
			temp->right = temp->right->left;
			free(temp2);
			return kopia;
		}
	}
	//kolejny element
	if (korzen->a > klucz) {
		if (korzen->left == NULL) {
			check = false;
			return kopia;
		}
		if (korzen->left->a == klucz && korzen->left->left == NULL && korzen->left->right == NULL) {
			Wezel* temp = korzen->left;
			korzen->left = NULL;
			korzen = temp;
			goto go;
		}
		korzen = korzen->left;
		goto go;
	}
	else {
		if (korzen->right == NULL) {
			check = false; return kopia;
		}
		if (korzen->right->a == klucz && korzen->right->left == NULL && korzen->right->right == NULL) {
			Wezel* temp = korzen->right;
			korzen->right = NULL;
			korzen = temp;
			goto go;
		}
		korzen = korzen->right;
		goto go;
	}
}

//pre-order




void main() {


	int ziarno = 2;
	bool losowe = false;
	int n = 10000;
	//for (int iterator = 0; iterator < 5; iterator++) {
		//n = n + 5000;
		std::cout << std::endl;
		std::cout << std::endl;
		srand(ziarno);
		double* wyniki = (double*)malloc(sizeof(double) * 6);
		srand(ziarno);
		clock_t begin, end;  double time_spent;
		Wezel* korzen = NULL;
		if (losowe) {
#pragma region losowe
			begin = clock();

			int x;
			korzen = WstawX(korzen, n, x);

			end = clock();  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
			wyniki[0] = x;
			wyniki[1] = time_spent;
#pragma endregion
		}
		else {
#pragma region nielosowo
			begin = clock();

			int x;
			korzen = WstawX2(korzen, n, x);

			end = clock();  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
			wyniki[0] = x;
			wyniki[1] = time_spent;
#pragma endregion
		}
#pragma region Szukaj
		begin = clock();
		int x = 0;
		for (int i = 0; i < n; i++) {
			if (SzukajElement(korzen, (rand() % 25000) * 4 + (rand() % 4))) {
				x++;
			}
		}
		end = clock();  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
		wyniki[2] = x;
		wyniki[3] = time_spent;
#pragma endregion
#pragma region Usun
		begin = clock();
		x = 0;
		bool check = false;
		for (int i = 0; i < n; i++) {
			korzen = UsunElement(korzen, (rand() % 25000) * 4 + (rand() % 4), check);
			if (check)x++;
			check = false;
		}

		end = clock();  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
		wyniki[4] = x;
		wyniki[5] = time_spent;
#pragma endregion
		std::cout << "Liczba elementow: " << n << std::endl;
		std::cout << "Wstawianie: " << wyniki[0] << " " << wyniki[1] << std::endl;
		std::cout << "Szukanie: " << wyniki[2] << " " << wyniki[3] << std::endl;
		std::cout << "Usuwanie: " << wyniki[4] << " " << wyniki[5] << std::endl;
	//}
	system("pause");
}