// ConsoleApplication3.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"

#include <iostream>
#include <locale>

using namespace std;

int node_width = 0;

struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

void preorder(node *p) {
	if (p != NULL) {
		cout << p->key << "\t";
		preorder(p->left);
		preorder(p->right);
	}

}

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);
}


int main() {
	setlocale(LC_ALL, "RU");
	node *root, *root1;
	int choice = 0;
	root = NULL;
	root1 = NULL;
	do {
		cout << "1 Вставить новый узел" << endl;
		cout << "2 Удалить элемент" << endl;
		cout << "3 Вывести дерево" << endl;
		cout << "4 Ширина дерева" << endl;
		cout << "5 Стереть данные" << endl;
		cout << "0 Выход" << endl;
		cout << "Выберите действие: ";
		cin >> choice;
		switch (choice) {
		case 1: {
			cout << "\n\t\tДобавление нового узла" << endl;
			cout << "Введите элемент: ";
			int a;
			cin >> a;
			root = insert(root, a);
			cout << "\nНовый элемент добавлен успешно\n" << endl;
			break;
		}
		case 2: {
			cout << "\nВведите удаляемый узел: ";
			int delel;
			cin >> delel;
			root = remove(root, delel);
			break;
		}
		case 3: {
			preorder(root);
			cout << endl;
			break;
		}

		case 4: {

		}
		case 5: {

		}
		case 0: {
			cout << "\n\tВыход\n" << endl;
			break;
		}
		default: {
			cout << "Ошибка! Повторите ввод\n" << endl;
			break;
		}
		}
		system("pause");
		system("cls");
	} while (choice != 0);
	return 0;
}