#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode
{
	int data;
	int lenght;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;
int getHeight(TreeNode* root)
{
	return root ? root->lenght : 0;
}
int Max(int a, int b)
{
	return a > b ? a : b;
}
//LL型
void llRotation(TreeNode* node, TreeNode** root)
{
	TreeNode* temp = node->lchild;
	node->lchild = temp->rchild;
	temp->rchild = node;
	//更新高度
	node->lenght = Max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	temp->lenght = Max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
	*root = temp;
}
//RR型
void rrRotation(TreeNode* node, TreeNode** root)
{
	TreeNode* temp = node->rchild;
	node->rchild = temp->lchild;
	temp->lchild = node;
	node->lenght = Max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	temp->lenght = Max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
	*root = temp;
}
//LR型
void lrRotation(TreeNode* node, TreeNode** root)
{
	//先RR 再LL
	rrRotation(node->lchild, &node->lchild);
	llRotation(node, root);
}
//RL型
void rlRotation(TreeNode* node, TreeNode** root)
{
	//先LL 在 RR
	llRotation(node->rchild, &node->rchild);
	rrRotation(*root, root);
}
void Insert(TreeNode** T, int data)
{
	if (*T == NULL)
	{
		(*T) = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = data;
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->lenght = 0;
	}
	else if (data < (*T)->data)
	{
		Insert(&(*T)->lchild, data);//解引用再取地址
		//判断高度
		int lheight = getHeight((*T)->lchild);
		int rheight = getHeight((*T)->rchild);
		if (lheight - rheight == 2)
		{
			if (data < (*T)->lchild->data)
			{
				//LL型
				llRotation(*T, T);
			}
			else
			{
				//LR
				//rrRotation((*T)->lchild, &(*T)->lchild);
				//llRotation(*T, T);
				lrRotation(*T, T);
			}
		}
	}
	else if (data > (*T)->data)
	{
		Insert(&(*T)->rchild, data);
		int lheigh = getHeight((*T)->lchild);
		int rheight = getHeight((*T)->rchild);
		if (rheight - lheigh == 2)
		{
			if (data > (*T)->rchild->data)
			{
				//RR
				rrRotation(*T, T);
			}
			else
			{
				//RL
				//llRotation((*T)->rchild, &(*T)->rchild);
				//rrRotation(*T, T);
				rlRotation(*T, T);
			}
		}
	}
	//根节点更新一下高度
	(*T)->lenght = Max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
}
//删除节点
TreeNode* minvalue(TreeNode* root)
{
	TreeNode* q = root;
	while (q && q->lchild != NULL)
	{
		q = q->lchild;
	}
	return q;
}
TreeNode* deleteNode(TreeNode* root, int key)
{
	if (root == NULL)
	{
		return root;
	}
	if (key < root->data)
	{
		root->lchild = deleteNode(root->lchild, key);
	}
	else if (key > root->data)
	{
		root->rchild = deleteNode(root->rchild, key);
	}
	else
	{
		//找到key
		if (root->lchild == NULL)
		{
			TreeNode* temp = root->rchild;
			free(root);
			return temp;
		}
		else if (root->rchild == NULL)
		{
			TreeNode* temp = root->lchild;
			free(root);
			return temp;
		}
		TreeNode* temp = minvalue(root->rchild);
		root->data = temp->data;
		root->rchild = deleteNode(root->rchild, temp->data);
	}

	if (root == NULL)
	{
		return root;
	}

	root->lenght = Max(getHeight(root->lchild), getHeight(root->rchild)) + 1;//删除后更新树的高度，看看有没有失衡

	//更新树的高度之后就计算一下平衡因子
	int balance = getHeight(root->lchild) - getHeight(root->rchild);

	if (balance > 1 && key < root->lchild->data)
	{
		//LL
		llRotation(root, &root);
	}
	if (balance < -1 && key > root->rchild->data)
	{
		//RR
		rrRotation(root, &root);
	}
	if (balance > 1 && key > root->lchild->data)
	{
		//LR
		lrRotation(root, &root);
	}
	if (balance < -1 && key < root->rchild->data)
	{
		rlRotation(root, &root);
	}
	return root;
}
TreeNode* Search(TreeNode* root,int key)
{
	if (root == NULL || root->data == key)
	{
		return root;
	}
	else if (key < root->data)
	{
		return Search(root->lchild, key);
	}
	else
	{
		return Search(root->rchild, key);
	}
}
void FreeNode(TreeNode* root)
{
	if (root)
	{
		FreeNode(root->lchild);
		FreeNode(root->rchild);
		free(root);
	}
}
void printNode(TreeNode* T)
{
	if (T)
	{
		printf("%d ", T->data);
		printNode(T->lchild);
		printNode(T->rchild);
	}
}
int main()
{
	TreeNode* root = NULL;
	int arr[6] = { 31,25,47,16,28,30};
	for (int i = 0; i < 6; i++)
	{
		Insert(&root, arr[i]);
	}
	printf("经过AVL调整后插入30的先序遍历为:\n");
	printNode(root);
	printf("\n");

	printf("删除一个元素后的先序遍历\n");
	root = deleteNode(root, 28);
	printNode(root);
	printf("\n");

	int num = 30;
	TreeNode* result = Search(root, num);
	if (result != NULL)
	{
		printf("找到key = %d 的值", result->data);
	}
	else 
	{
		printf("找不到key = %d 的值", num);
	}
	FreeNode(root);
	return 0;
}