#include <iostream>
#include <ctime>
#include <iomanip>

using namespace std;

int maximum(int a, int b)
{
	if (a > b) return a;
	else return b;
}

int minimum(int a, int b)
{
	if (a > b) return b;
	else return a;
}

struct Node
{
	int key;
	struct Node* left;
	struct Node* right;
};

typedef struct Node N;

N* treeInit(int _key)
{
	N* newNode = new N;
	newNode->key = _key;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

N* searchInsert(N* Root, int _key)
{
	N* tmp = Root;
	N* prev = NULL;
	bool found = false;

	while ((tmp != NULL) && (found == false))
	{
		prev = tmp;
		if (_key == tmp->key)
			found = true;
		else
		{
			if (_key < tmp->key) tmp = tmp->left;
			else  tmp = tmp->right;
		}
	}
	if (found)
		return tmp;

	N* newNode = new N;
	newNode->key = _key;
	newNode->left = NULL;
	newNode->right = NULL;
	if (_key < prev->key)
		prev->left = newNode;
	else
		prev->right = newNode;
	return newNode;
}

int MaxTreeH(N* Root) {
	if (Root == NULL)
		return 0;
	return 1 + maximum(MaxTreeH(Root->left), MaxTreeH(Root->right));
}

int MinTreeH(N* Root) {
	if (Root == NULL)
		return 0;
	return 1 + minimum(MinTreeH(Root->left), MinTreeH(Root->right));
}

void printTree(N* Root, int level)
{
	if (Root != NULL)
	{
		printTree(Root->right, level + 1);
		for (int i = 0; i < level; i++) cout << "   ";
		cout << Root->key << endl;
		printTree(Root->left, level + 1);
	}
}

void deleteTree(N* Root)
{
	if (Root == NULL) return;

	deleteTree(Root->left);
	deleteTree(Root->right);
	delete Root;
}

struct RNode
{
	int key;
	int size;
	RNode* left;
	RNode* right;
};

typedef RNode* RN;

RN RTreeInit(int _key)
{
	RN newNode = new RNode;
	newNode->key = _key;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

void printRTree(RN Root, int level)
{
	if (Root != NULL)
	{
		printRTree(Root->right, level + 1);
		for (int i = 0; i < level; i++) cout << "   ";
		cout << Root->key << endl;
		printRTree(Root->left, level + 1);
	}
}

int SizeRTree(RN _node)
{
	if (_node == NULL) return 0;
	return _node->size;
}

void fixRTreeSize(RN _node)
{
	_node->size = SizeRTree(_node->left) + SizeRTree(_node->right) + 1;
}

RN rotateRight(RN _node)
{
	RN tmp = _node->left;
	if (!tmp) return _node;
	_node->left = tmp->right;
	tmp->right = _node;
	tmp->size = _node->size;
	fixRTreeSize(_node);
	return tmp;
}

RN rotateLeft(RN _node)
{
	RN tmp = _node->right;
	if (!tmp) return _node;
	_node->right = tmp->left;
	tmp->left = _node;
	tmp->size = _node->size;
	fixRTreeSize(_node);
	return tmp;
}

RN insertToRTreeRoot(RN* _node, int _key)
{
	if (!(*_node))
	{
		RN newNode = new RNode;
		newNode->size = 1;
		newNode->left = NULL;
		newNode->right = NULL;
		newNode->key = _key;
		return newNode;
	}

	if (_key < (*_node)->key)
	{
		(*_node)->left = insertToRTreeRoot(&((*_node)->left), _key);
		return rotateRight((*_node));
	}
	else
	{
		(*_node)->right = insertToRTreeRoot(&((*_node)->right), _key);
		return rotateLeft((*_node));
	}
}

RN insertRand(RN* _node, int _key)
{
	if (!(*_node))
	{
		RN newNode = new RNode;
		newNode->size = 1;
		newNode->left = NULL;
		newNode->right = NULL;
		newNode->key = _key;
		return newNode;
	}
	if (rand() % ((*_node)->size + 1) == 0) return (*_node) = insertToRTreeRoot(_node, _key);
	if ((*_node)->key > _key) 	(*_node)->left = insertRand(&((*_node)->left), _key);
	else (*_node)->right = insertRand(&((*_node)->right), _key);
	fixRTreeSize((*_node));
	return (*_node);
}

int getMaxRTreeHeight(RN Root) {
	if (Root == NULL)
		return 0;
	return 1 + maximum(getMaxRTreeHeight(Root->left), getMaxRTreeHeight(Root->right));
}

int getMinRTreeHeight(RN Root) {
	if (Root == NULL)
		return 0;
	return 1 + minimum(getMinRTreeHeight(Root->left), getMinRTreeHeight(Root->right));
}

void deleteRTree(RN Root)
{
	if (Root == NULL) return;

	deleteRTree(Root->left);
	deleteRTree(Root->right);
	delete Root;
}

struct DATA
{
	int* mas;
	int min;
	int max;
	int size;
};

typedef struct DATA Data;


int random(int N)
{
	int result = rand() % N;
	return result;
}


int formRArray(Data* data)
{
	int tmp;
	bool inArray;
	int i = 0;
	if ((data->max - data->min) < data->size) return -1;
	while (i < data->size)
	{
		inArray = false;
		tmp = data->min + random(data->max - data->min);
		for (int j = 0; j < i; j++)
		{
			if (data->mas[j] == tmp)
			{
				inArray = true;
				break;
			}
		}
		if (inArray == false)
		{
			data->mas[i] = tmp;
			i++;
		}
	}
	return 0;
}

int copyArray(Data dataFrom, Data* dataTo)
{
	for (int i = 0; i < dataFrom.size; i++)
	{
		dataTo->mas[i] = dataFrom.mas[i];
	}
	return 0;
}


void printMas(Data& data)
{
	for (int i = 0; i < data.size; i++)
		cout << data.mas[i] << ' ';
	cout << '\n';
}

void ShellSort(Data& data)
{
	int h = 0;

	while (h < data.size / 3)
	{
		h = 3 * h + 1;
	}

	for (h; h > 0; h = (h - 1) / 3)
	{
		for (int i = h; i < data.size; i++)
		{
			int j = i;
			int tmp = data.mas[i];

			for (j = i; j >= h && data.mas[j - h] > tmp; j -= h)
			{
				data.mas[j] = data.mas[j - h];

			}
			data.mas[j] = tmp;
		}
	}

	return;
}

int main()
{
	system("color F0");
	setlocale(LC_ALL, "RUS");

	srand(time(NULL));

	N* Tree1 = NULL;
	N* Tree2 = NULL;

	RN RandTree1 = NULL;
	RN RandTree2 = NULL;

	Data unsortedArray{ NULL, 0, 1000, 10 };
	Data sortedArray{ NULL, 0, 1000, 10 };

	unsortedArray.mas = new int[unsortedArray.size];

	formRArray(&unsortedArray);

	sortedArray.mas = new int[sortedArray.size];

	copyArray(unsortedArray, &sortedArray);

	ShellSort(sortedArray);

	cout << "Несортированная последовательность: "; printMas(unsortedArray);
	cout << "\nСортированная последовательность: "; printMas(sortedArray);

	Tree1 = treeInit(unsortedArray.mas[0]);
	Tree2 = treeInit(sortedArray.mas[0]);

	for (int i = 1; i < unsortedArray.size; i++)
	{
		searchInsert(Tree1, unsortedArray.mas[i]);
	}

	for (int i = 0; i < unsortedArray.size; i++)
	{
		RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
	}

	for (int i = 1; i < sortedArray.size; i++)
	{
		searchInsert(Tree2, sortedArray.mas[i]);
	}

	for (int i = 0; i < sortedArray.size; i++)
	{
		RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
	}


	cout << "\nДеревья для несортированной последовательности: \n\n";

	cout << "\nОбычное дерево:\n";
	printTree(Tree1, 0);
	cout << "\nМаксимальная высота: " << MaxTreeH(Tree1) << endl;
	cout << "Минимальная высота: " << MinTreeH(Tree1) << endl;
	cout << "\nРандомизированное дерево:\n";
	printRTree(RandTree1, 0);
	cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree1) << endl;
	cout << "Минимальная высота: " << getMinRTreeHeight(RandTree1) << endl;

	cout << "\n\nДеревья для сортированной последовательности: \n\n";

	cout << "\nОбычное дерево:\n";
	printTree(Tree2, 0);
	cout << "\nМаксимальная высота: " << MaxTreeH(Tree2) << endl;
	cout << "Минимальная высота: " << MinTreeH(Tree2) << endl;;
	cout << "\nРандомизированное дерево:\n";
	printRTree(RandTree2, 0);
	cout << "\nМаксимальная высота: " << getMaxRTreeHeight(RandTree2) << endl;
	cout << "Минимальная высота: " << getMinRTreeHeight(RandTree2) << endl;



	deleteTree(Tree1);
	deleteTree(Tree2);
	deleteRTree(RandTree1);
	deleteRTree(RandTree2);

	delete[] unsortedArray.mas;
	delete[] sortedArray.mas;

	cout << endl;

	for (int keyCount = 25; keyCount <= 300; keyCount = keyCount + 25)
	{
		Tree1 = NULL;
		Tree2 = NULL;

		RandTree1 = NULL;
		RandTree2 = NULL;

		unsortedArray.size = keyCount;
		sortedArray.size = keyCount;

		unsortedArray.mas = new int[keyCount];
		formRArray(&unsortedArray);
		sortedArray.mas = new int[keyCount];
		copyArray(unsortedArray, &sortedArray);
		ShellSort(sortedArray);

		Tree1 = treeInit(unsortedArray.mas[0]);
		Tree2 = treeInit(sortedArray.mas[0]);
		RandTree1 = insertRand(&RandTree1, unsortedArray.mas[0]);
		RandTree2 = insertRand(&RandTree2, unsortedArray.mas[0]);

		for (int i = 1; i < keyCount; i++)
		{
			searchInsert(Tree1, unsortedArray.mas[i]);
			RandTree1 = insertRand(&RandTree1, unsortedArray.mas[i]);
			searchInsert(Tree2, sortedArray.mas[i]);
			RandTree2 = insertRand(&RandTree2, sortedArray.mas[i]);
		}

		cout << " n = " << keyCount << endl;
		cout << " Случайная последовательность максимум:" << endl;
		cout << "   Обычное дерево: высота " << MaxTreeH(Tree1) << endl;
		cout << "   Рандом. дерево: высота " << MaxTreeH(Tree2) << endl;
		cout << "\n Упорядоченная последовательность максимум:" << endl;
		cout << "   Обычное дерево: высота " << getMaxRTreeHeight(RandTree1) << endl;
		cout << "   Рандом. дерево: высота " << getMaxRTreeHeight(RandTree2) << endl;
		cout << "\n Случайная последовательность минимум:" << endl;
		cout << "   Обычное дерево: высота " << MinTreeH(Tree1) << endl;
		cout << "   Рандом. дерево: высота " << MinTreeH(Tree2) << endl;
		cout << "\n Упорядоченная последовательность минимум:" << endl;
		cout << "   Обычное дерево: высота " << getMinRTreeHeight(RandTree1) << endl;
		cout << "   Рандом. дерево: высота " << getMinRTreeHeight(RandTree2) << "\n\n\n";

		deleteTree(Tree1);
		deleteTree(Tree2);
		deleteRTree(RandTree1);
		deleteRTree(RandTree2);

		delete unsortedArray.mas;
		delete sortedArray.mas;
	}
}