#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;

const unsigned char KEY_MAX_LENGTH = 5;

struct node {
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

unsigned char height(node* p)
{
	return p?p->height:0;
}

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( k<p->key )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p
{
	return p->left?findmin(p->left):p;
}

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);
	else //  k == p->key
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}
	return balance(p);
}

bool search(node* p, int k) {
	bool res = false;
	if (p) {
		if (k == p->key)
			return true;
		if (k < p->key) {
			res = search(p->left, k);
		}
		if (k > p->key) {
			res = search(p->right, k);
		}
	}
	return res;
}

void printGL(node* p) {
	if (p) {
		if (p->left) {
			printGL(p->left);
		}
		for (int i = 0; i < p->height - 1; i++)
			cout << "\t";
		cout << p->key;
		cout << endl;
		if (p->right) {
			printGL(p->right);
		}
	}
}

void printSH(node* p) {
	if (p) {
		cout << p->key;
		for (int i = 0; i < p->height; i++) {
			cout << "*";
		}
		if (p->left)

		if (p->right)
			printGL(p->right);
	}
}

int main()
{
	char ch = 0;
	do {
		node* p = new node(10);
		system("cls");
		cout << "Choose your destiny!\n";
		cout << "[1] - add\n[2] - remove\n[3] - search\n[4] - print\n";
		ch = _getch();
		switch (ch) {
		case '1':
			int a;
			cout << "Enter key: ";
			cin >> a;
			insert(p, a);
			break;
		case '2':

			break;
		case '3':

			break;
		case '4':

			break;
		}
	} while (ch != 27);
}