#include <stdio.h>
#include <stdlib.h>

typedef struct avlTreeNode avlTreeNode;
struct avlTreeNode {
	int data;
	int height;
	avlTreeNode *left, *right;
};


int altura(avlTreeNode *n) {
    if (n == NULL) return -1;
	int esq = (n->left != NULL ? n->left->height : -1);
	int dir = (n->right != NULL ? n->right->height : -1);
	return (esq > dir ? esq + 1 : dir + 1);
}

int fatorBalanceamento(avlTreeNode *raiz) {
	int esq = altura(raiz->left);
	int dir = altura(raiz->right);
	return (esq - dir);
}

avlTreeNode *rotaciona_esquerda(avlTreeNode *raiz) {
	avlTreeNode *arvDireita = raiz->right;

	raiz->right = arvDireita->left;
	arvDireita->left = raiz;

	raiz->height = altura(raiz);
	arvDireita->height = altura(arvDireita);
	return arvDireita;
}

avlTreeNode *rotaciona_direita(avlTreeNode *raiz) {
	avlTreeNode *arvEsquerda = raiz->left;

	raiz->left = arvEsquerda->right;
	arvEsquerda->right = raiz;

	raiz->height = altura(raiz);
	arvEsquerda->height = altura(arvEsquerda);
	return arvEsquerda;
}

avlTreeNode *balancear(avlTreeNode *raiz) {
	int fb = fatorBalanceamento(raiz);
	if (fb > 1) {
		int fb_esq = fatorBalanceamento(raiz->left);
		if (fb_esq >= 0) {
			printf("Rotacao simples direita\n");
		} else {
			raiz->left = rotaciona_esquerda(raiz->left);
			printf("Rotacao dupla direita\n");
		}
		raiz = rotaciona_direita(raiz);
	} else if (fb < -1) {
		int fb_dir = fatorBalanceamento(raiz->right);
		if (fb_dir <= 0) {
			printf("Rotacao simples esquerda\n");
		} else {
			raiz->right = rotaciona_direita(raiz->right);
			printf("Rotacao dupla esquerda\n");
		}
		raiz = rotaciona_esquerda(raiz);
	}
	return raiz;
}

avlTreeNode *inserir(avlTreeNode *raiz, int valor) {
	if (raiz == NULL) {
		raiz = malloc(sizeof(avlTreeNode));
		raiz->data = valor;
		raiz->left = NULL;
		raiz->right = NULL;
		raiz->height = 0;
		return raiz;
	}
	if (valor < raiz->data)
		raiz->left = inserir(raiz->left, valor);
	else if (valor > raiz->data)
		raiz->right = inserir(raiz->right, valor);

	raiz->height = altura(raiz);

	raiz = balancear(raiz);
	
	return raiz;
}

void liberaArvore(avlTreeNode *raiz) {
	if (raiz == NULL) return;
	liberaArvore(raiz->left);
	liberaArvore(raiz->right);
	printf("%d ", raiz->data);
	free(raiz);
}

int main() {
	avlTreeNode *raiz = NULL;

	raiz = inserir(raiz, 10);
	raiz = inserir(raiz, 20);
	raiz = inserir(raiz, 30);
	
	liberaArvore(raiz);

	return 0;
}