// avltree.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <cstdlib>

typedef struct AVLTree
{
	int data;
	struct AVLTree *left, *right;
	int ht;
}AVLTree;

AVLTree *insert(AVLTree *, int);
AVLTree *Delete(AVLTree *, int);
void preorder(AVLTree *);
void inorder(AVLTree *);
int height(AVLTree *);
AVLTree *rotateright(AVLTree *);
AVLTree *rotateleft(AVLTree *);
AVLTree *RR(AVLTree *);
AVLTree *LL(AVLTree *);
AVLTree *LR(AVLTree *);
AVLTree *RL(AVLTree *);
int BF(AVLTree *);



AVLTree * insert(AVLTree *T, int x)
{
	if (T == NULL)
	{
		T = (AVLTree*)malloc(sizeof(AVLTree));
		T->data = x;
		T->left = NULL;
		T->right = NULL;
	}
	else
		if (x > T->data)		// wstaw do prawego poddrzewa
		{
			T->right = insert(T->right, x);
			if (BF(T) == -2)
				if (x > T->right->data)
					T = RR(T);
				else
					T = RL(T);
		}
		else
			if (x < T->data)
			{
				T->left = insert(T->left, x);
				if (BF(T) == 2)
					if (x < T->left->data)
						T = LL(T);
					else
						T = LR(T);
			}

	T->ht = height(T);

	return(T);
}

AVLTree * Delete(AVLTree *T, int x)
{
	AVLTree *p;

	if (T == NULL)
	{
		return NULL;
	}
	else
		if (x > T->data)		// wstawianie do prawego poddrzewa
		{
			T->right = Delete(T->right, x);
			if (BF(T) == 2)
				if (BF(T->left) >= 0)
					T = LL(T);
				else
					T = LR(T);
		}
		else
			if (x < T->data)
			{
				T->left = Delete(T->left, x);
				if (BF(T) == -2)	//Ponowne zrównoważenie
					if (BF(T->right) <= 0)
						T = RR(T);
					else
						T = RL(T);
			}
			else
			{
				//znalezienie usuwanego elementu
				if (T->right != NULL)
				{	//usuwanie następcy procedury inorder
					p = T->right;

					while (p->left != NULL)
						p = p->left;

					T->data = p->data;
					T->right = Delete(T->right, p->data);

					if (BF(T) == 2)//Ponowne równoważenie
						if (BF(T->left) >= 0)
							T = LL(T);
						else
							T = LR(T); \
				}
				else
					return(T->left);
			}
	T->ht = height(T);
	return(T);
}

int height(AVLTree *T)
{
	int lh, rh;
	if (T == NULL)
		return(0);

	if (T->left == NULL)
		lh = 0;
	else
		lh = 1 + T->left->ht;

	if (T->right == NULL)
		rh = 0;
	else
		rh = 1 + T->right->ht;

	if (lh > rh)
		return(lh);

	return(rh);
}

AVLTree * rotateright(AVLTree *x)
{
	AVLTree *y;
	y = x->left;
	x->left = y->right;
	y->right = x;
	x->ht = height(x);
	y->ht = height(y);
	return(y);
}

AVLTree * rotateleft(AVLTree *x)
{
	AVLTree *y;
	y = x->right;
	x->right = y->left;
	y->left = x;
	x->ht = height(x);
	y->ht = height(y);

	return(y);
}

AVLTree * RR(AVLTree *T)
{
	T = rotateleft(T);
	return(T);
}

AVLTree * LL(AVLTree *T)
{
	T = rotateright(T);
	return(T);
}

AVLTree * LR(AVLTree *T)
{
	T->left = rotateleft(T->left);
	T = rotateright(T);

	return(T);
}

AVLTree * RL(AVLTree *T)
{
	T->right = rotateright(T->right);
	T = rotateleft(T);
	return(T);
}

int BF(AVLTree *T)
{
	int lh, rh;
	if (T == NULL)
		return(0);

	if (T->left == NULL)
		lh = 0;
	else
		lh = 1 + T->left->ht;

	if (T->right == NULL)
		rh = 0;
	else
		rh = 1 + T->right->ht;

	return(lh - rh);
}

void preorder(AVLTree *T)
{
	if (T != NULL)
	{
		printf("%d(bf=%d)", T->data, BF(T));
		preorder(T->left);
		preorder(T->right);
	}
}

void inorder(AVLTree *T)
{
	if (T != NULL)
	{
		inorder(T->left);
		printf("%d(bf=%d)", T->data, BF(T));
		inorder(T->right);
	}
}

int main()
{
	AVLTree *root = NULL;
	int x, n, i, op;
	printf("          DRZEWO AVL \n");
	do
	{
		printf("\n1)Utworz drzewo:");
		printf("\n2)Wstaw dane:");
		printf("\n3)Usun dane:");
		printf("\n4)Wyswietl drzewo:");
		printf("\n5)Zakoncz:");
		printf("\n\nPodaj opcje:");
		scanf_s("%d", &op);

		switch (op)
		{
		case 1: printf("\nPodaj liczbę elementow:");
			scanf_s("%d", &n);
			printf("\nPodaj dane do drzewa:");
			root = NULL;
			for (i = 0; i < n; i++)
			{
				scanf_s("%d", &x);
				root = insert(root, x);
			}
			break;

		case 2: printf("\nPodaj dane:");
			scanf_s("%d", &x);
			root = insert(root, x);
			break;

		case 3: printf("\nPodaj dane:");
			scanf_s("%d", &x);
			root = Delete(root, x);
			break;

		case 4: printf("\nSekwencja PREORDER:\n");
			preorder(root);
			printf("\n\nSekwencja INORDER:\n");
			inorder(root);
			printf("\n");
			break;
		}
	} while (op != 5);

	return 0;
}