Karol

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <random>

using namespace std;

struct Element {

	Element *left;
	Element* right;
	int key;
	char tab[10];
	Element(int k);
};

Element::Element(int k) {

	key = k;
	left = NULL;
	right = NULL;
	sprintf(tab, "%d", key);
}


bool insert(Element *&root, int k) {

	Element *previous = NULL;
	Element *p = root;

	while (p != NULL) {
		if (p->key == k) {
			return false;
		}

		previous = p;
		if (p->key < k) {
			p = p->right;
		}
		else {
			p = p->left;
		}
	}

	Element *nowy = new Element(k);
	nowy->key = k;
	nowy->left = NULL;
	nowy->right = NULL;

	if (previous == NULL) {
		root = nowy;
		return true;
	}

	if (previous->key < k) {
		previous->right = nowy;
	}
	else {
		previous->left = nowy;
	}
	return true;
}


void insert_x(Element *&root, int X) {

	int k;

	for (int i = 0; i < X; i++) {

		k = (rand() % 20000) + (-10000);

		while (insert(root, k) == false) {

			k = (rand() % 20000) + (-10000);
		}
	}
}




void rotate_right(Element* root,Element *grandfather, Element* parent, Element *child) {



	if (grandfather != NULL) {

		if (grandfather->right = parent)
			grandfather->right = child;
		else
			grandfather->left = child;
	}
	else
		root = child;

	Element* tmp = child->right;
	child->right = parent;
	parent->left = tmp;
	return;
}





void make_backbone(Element* root) {

	Element* grandfather = NULL;
	Element *tmp = root;


	while (tmp != NULL) {
		if ((tmp->left) != NULL) {
			Element *tmp2 = tmp->left;
			rotate_right(root,grandfather, tmp, tmp->left);
			tmp = tmp2;
		}
		else {
			grandfather = tmp;
			tmp = tmp->right;
		}
	}
}

int maxDepth(Element* root)
{
	if (root == NULL)
		return 0;
	else
	{
		/* compute the depth of each subtree */
		int lDepth = maxDepth(root->left);
		int rDepth = maxDepth(root->right);

		/* use the larger one */
		if (lDepth > rDepth)
			return(lDepth + 1);
		else return(rDepth + 1);
	}
}


void rotate_left(Element*& root, Element*& grandfather, Element*& parent, Element*& child) {


	if (grandfather != NULL) {

		if (grandfather->left == parent)
			grandfather->left = child;
		else
			grandfather->right = child;
	}
	else
		root = child;
	Element* tmp = child->left;
	child->left = parent;
	parent->right = tmp;
	return;
}


void make_perfect_tree(Element* root,int X) {

	Element* grandfather = NULL;
	Element *tmp = root;
	int m = 1;

	while (m <= X) {
		m = 2*m + 1;
	}

	m = m / 2;

		for (int i = 0; i < (X - m); i++) {

			Element *tmp2 = tmp->right;

			if (tmp2 != NULL) {
					rotate_left(root, grandfather, tmp, tmp->right);
					grandfather = tmp2;
					tmp = tmp2->right;
			}
		}
	while (m > 1) {
		m = m / 2;
		Element* grandfather = NULL;
		Element *tmp = root;
		for (int i = 0; i < m; i++) {

				Element *tmp2 = tmp->right;
				rotate_left(root, grandfather, tmp, tmp->right);
				grandfather = tmp2;
				tmp = tmp2->right;
		}
	}
}



int preorder(Element *root) {

	int l = 0;

	if (root == NULL)
		return l;
	l += preorder(root->left);
	l += preorder(root->right);
	l++;
	return l;
}

void DSW(Element* root,int X) {
	if (root != NULL) {
		make_backbone(root);
		make_perfect_tree(root,X);
	}
}



int main()
{

	srand(time(NULL));

	int X1,X2;

	Element *root = NULL;

	clock_t start, stop;

	start = clock();

	double czas;

	FILE* fp = fopen("inlab05.txt", "r");
	if (fp == NULL)
		return -1;
	fscanf(fp, "%d %d", &X1, &X2);
	fclose(fp);

	insert_x(root, X1);
	insert(root, 9);
	int z = preorder(root);
	/*
	insert(root, 13);
	insert(root, 11);
	insert(root, 16);
	insert(root, 14);
	insert(root, 6);
	insert(root, 3);
	insert(root, 4);*/
	cout << maxDepth(root) << endl;
	make_backbone(root);
	make_perfect_tree(root, z);
	cout << maxDepth(root) << endl;
	//make_perfect_tree(root,X1);


	stop = clock();

	czas = (double)(stop - start) / CLOCKS_PER_SEC;

	cout << "Czas wykonania programu: " << czas << endl;
}