//struktury
#include<iostream>
using namespace std;

struct BstNode {
	int data;
	BstNode* left;
	BstNode* right;
	BstNode* stary;
};

BstNode* GetNewNode(int data) {
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}


BstNode* Insert(BstNode* root, int data) {
	if (root == NULL) { // empty tree
		root = GetNewNode(data);
	}
	// if data to be inserted is lesser, insert in left subtree.
	else if (data <= root->data) {
		root->left = Insert(root->left, data);
	}
	// else, insert in right subtree.
	else {
		root->right = Insert(root->right, data);
	}
	return root;
}
 
BstNode* Insertbst(BstNode* root, int data) {
	if (root == NULL) { // empty tree
		root = GetNewNode(data);
	}
	// if data to be inserted is lesser, insert in left subtree.
	else if (data <= root->data) {
		root->left = Insertbst(root->left, data);
		root->left->stary = root;
	}
	// else, insert in right subtree.
	else {
		root->right = Insert(root->right, data);
		root->right->stary = root;


	}
	return root;
}






bool Search(BstNode* root, int data) {
	if (root == NULL) {
		return false;
	}
	else if (root->data == data) {
		return true;
	}
	else if (data <= root->data) {
		return Search(root->left, data);
	}
	else {
		return Search(root->right, data);
	}
}
void Inorder(BstNode* root) {
	if (root == NULL) return;

	Inorder(root->left);       //Visit left subtree
	cout<<root->data<<"   ";  //Print data
	Inorder(root->right);      // Visit right subtree
}



BstNode* FindMin(BstNode* root)
{
	while (root->left != NULL) root = root->left;
	return root;
}


int max(BstNode* root)
{
	BstNode* temp = root;
	while (temp->right != NULL)
		temp = temp->right;
	return(temp->data);
}

int min(BstNode* root)
{
	BstNode* temp = root;
	while (temp->left != NULL)
		temp = temp->left;
	return(temp->data);
}

BstNode* usunliscie(BstNode* root) {
	if (root == NULL)
		return NULL;
	if (root->left == NULL && root->right == NULL)
	{
		delete root;
		return NULL;
	}

	root->left = usunliscie(root->left);
	root->right = usunliscie(root->right);

	return root;
}


BstNode* Delete(BstNode* root, int data) {
	if (root == NULL) return root;
	else if (data < root->data) root->left = Delete(root->left, data);
	else if (data > root->data) root->right = Delete(root->right, data);
	// znaleziono
	else {
		// Case 1:  nie ma dzieci
		if (root->left == NULL && root->right == NULL) {
			delete root;
			root = NULL;
		}
		//Case 2: jedno dziecko
		else if (root->left == NULL) {
			 BstNode* temp = root;
			root = root->right;
			delete temp;
		}
		else if (root->right == NULL) {
			BstNode* temp = root;
			root = root->left;
			delete temp;
		}
		// case 3: 2 dzieci -  sprowadzam do postaci zeby bylo jedno dziecko
		else {
			BstNode* temp = FindMin(root->right);
			root->data = temp->data;
			root->right = Delete(root->right, temp->data);
		}
	}
	return root;
}


BstNode* minn(BstNode* root)
{
	while (root->left)
		root = root->left;
	return root;

}

BstNode* maxx(BstNode* root)
{
	while (root->right)
		root = root->right;
	return root;
}
void nastepnik(BstNode* root, BstNode*& pop, int x)
{
	if (root == NULL)
	{
		pop = NULL;
		return;
	}
	if (root->data == x) {
		if (root->right)
			pop = minn(root->right);
	}
	else if (x < root->data)
	{
		pop = root;
		nastepnik(root->left, pop, x);
	}
	else {
		nastepnik(root->right,pop, x);
	}
}

void poprzednik(BstNode* root, BstNode*& pop, int x)
{
	if (root == NULL)
	{
		pop = NULL;
		return;
	}
	if (root->data == x) {
		if (root->left)
			pop = maxx(root->left);
	}
	else if (x < root->data)
		poprzednik(root->left, pop, x);
	else {
		pop = root;
		poprzednik(root->right, pop, x);
	}
}


// Rotacja w lewo
//---------------
void rot_L(BstNode*& root, BstNode* A)
{
	BstNode* B = A->right, *p = A->stary;

	if (B)
	{
		A->right = B->left;
		if (A->right) A->right->stary = A;

		B->left = A;
		B->stary = p;
		A->stary = B;

		if (p)
		{
			if (p->left == A) p->left = B; else p->right = B;
		}
		else root = B;
	}
}

// Rotacja w prawo
//----------------
void rot_R(BstNode*& root, BstNode* A)
{
	BstNode* B = A->left, *p = A->stary;

	if (B)
	{
		A->left = B->right;
		if (A->left) A->left->stary = A;

		B->right = A;
		B->stary = p;
		A->stary = B;

		if (p)
		{
			if (p->left == A) p->left = B; else p->right = B;
		}
		else root = B;
	}
}


int main() {
	BstNode* root = NULL;  
	BstNode* pop = NULL;

	root = Insertbst(root, 15);
	root = Insertbst(root, 10);
	root = Insertbst(root, 20);
	root = Insertbst(root, 25);
	root = Insertbst(root, 8);
	root = Insertbst(root, 12);

	Inorder(root);
	root=Delete(root, 10);
	cout << endl;
	Inorder(root);
	nastepnik(root, pop, 12);
	cout << endl << pop->data;

	rot_R(root, root->right);

	system("pause");
	return 0;

}
//klasy
#include<iostream>
using namespace std;

class BST {

	struct BstNode {
		int data;
		BstNode* left;
		BstNode* right;
		BstNode* stary;
	};

	BstNode* root;

	BstNode* GetNewNode(int data) {
		BstNode* newNode = new BstNode();
		newNode->data = data;
		newNode->left = newNode->right = NULL;
		return newNode;
	}


	BstNode* Insertbst(BstNode* root, int data) {
		if (root == NULL) { // empty tree
			root = GetNewNode(data);
		}
		// if data to be inserted is lesser, insert in left subtree.
		else if (data <= root->data) {
			root->left = Insertbst(root->left, data);
			root->left->stary = root;
		}
		// else, insert in right subtree.
		else {
			root->right = Insertbst(root->right, data);
			root->right->stary = root;


		}
		return root;
	}






	bool Search(BstNode* root, int data) {
		if (root == NULL) {
			return false;
		}
		else if (root->data == data) {
			return true;
		}
		else if (data <= root->data) {
			return Search(root->left, data);
		}
		else {
			return Search(root->right, data);
		}
	}
	void Inorder(BstNode* root) {
		if (root == NULL) return;

		Inorder(root->left);       //Visit left subtree
		cout << root->data << "   ";  //Print data
		Inorder(root->right);      // Visit right subtree
	}



	BstNode* FindMin(BstNode* root)
	{
		while (root->left != NULL) root = root->left;
		return root;
	}


	int max(BstNode* root)
	{
		BstNode* temp = root;
		while (temp->right != NULL)
			temp = temp->right;
		return(temp->data);
	}

	int min(BstNode* root)
	{
		BstNode* temp = root;
		while (temp->left != NULL)
			temp = temp->left;
		return(temp->data);
	}

	BstNode* usunliscie(BstNode* root) {
		if (root == NULL)
			return NULL;
		if (root->left == NULL && root->right == NULL)
		{
			delete root;
			return NULL;
		}

		root->left = usunliscie(root->left);
		root->right = usunliscie(root->right);

		return root;
	}


	BstNode* Delete(BstNode* root, int data) {
		if (root == NULL) return root;
		else if (data < root->data) root->left = Delete(root->left, data);
		else if (data > root->data) root->right = Delete(root->right, data);
		// znaleziono
		else {
			// Case 1:  nie ma dzieci
			if (root->left == NULL && root->right == NULL) {
				delete root;
				root = NULL;
			}
			//Case 2: jedno dziecko
			else if (root->left == NULL) {
				BstNode* temp = root;
				root = root->right;
				delete temp;
			}
			else if (root->right == NULL) {
				BstNode* temp = root;
				root = root->left;
				delete temp;
			}
			// case 3: 2 dzieci -  sprowadzam do postaci zeby bylo jedno dziecko
			else {
				BstNode* temp = FindMin(root->right);
				root->data = temp->data;
				root->right = Delete(root->right, temp->data);
			}
		}
		return root;
	}


	BstNode* minn(BstNode* root)
	{
		while (root->left)
			root = root->left;
		return root;

	}

	BstNode* maxx(BstNode* root)
	{
		while (root->right)
			root = root->right;
		return root;
	}
	void nastepnik(BstNode* root, BstNode*& pop, int x)
	{
		if (root == NULL)
		{
			pop = NULL;
			return;
		}
		if (root->data == x) {
			if (root->right)
				pop = minn(root->right);
		}
		else if (x < root->data)
		{
			pop = root;
			nastepnik(root->left, pop, x);
		}
		else {
			nastepnik(root->right, pop, x);
		}
	}

	void poprzednik(BstNode* root, BstNode*& pop, int x)
	{
		if (root == NULL)
		{
			pop = NULL;
			return;
		}
		if (root->data == x) {
			if (root->left)
				pop = maxx(root->left);
		}
		else if (x < root->data)
			poprzednik(root->left, pop, x);
		else {
			pop = root;
			poprzednik(root->right, pop, x);
		}
	}


	// Rotacja w lewo
	//---------------
	void rot_L(BstNode*& root, BstNode* A)
	{
		BstNode* B = A->right, * p = A->stary;

		if (B)
		{
			A->right = B->left;
			if (A->right) A->right->stary = A;

			B->left = A;
			B->stary = p;
			A->stary = B;

			if (p)
			{
				if (p->left == A) p->left = B; else p->right = B;
			}
			else root = B;
		}
	}

	// Rotacja w prawo
	//----------------
	void rot_R(BstNode*& root, BstNode* A)
	{
		BstNode* B = A->left, * p = A->stary;

		if (B)
		{
			A->left = B->right;
			if (A->left) A->left->stary = A;

			B->right = A;
			B->stary = p;
			A->stary = B;

			if (p)
			{
				if (p->left == A) p->left = B; else p->right = B;
			}
			else root = B;
		}
	}

	BstNode* makeEmpty(BstNode* t) {
		if (t == NULL)
			return NULL;
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		return NULL;
	}

	public:
		BST() {
			root = NULL;
		}
		~BST() {
			root = makeEmpty(root);

		}
		void insert(int x) {
			root = Insertbst(root ,x);
		}

		void zobacz() {
			Inorder(root);
		}

};

int main() {
	BST t;
	t.insert(20);
	t.insert(25);
	t.insert(15);
	t.insert(10);
	t.insert(30);
	t.zobacz();


	system("pause");
	return 0;


}