#define Ty int  //以整型數(shù)據(jù)為例
typedef struct Node
{
	Ty data;             //數(shù)據(jù)
	int height;          //高度
	struct Node* LChild; //左子樹
	struct Node* RChild; //右子樹
}Node,AVLTree;

AVLTree* creatAVLTree(Ty data)
{
    AVLTree* tree = (AVLTree*)malloc(sizeof(AVLTree));
    assert(tree);
    tree->data = data;
    tree->height = 0;
    tree->LChild = NULL;
    tree->RChild = NULL;
    return tree;
}

//輔助函數(shù)
#define HEIGHT(x) ((x==NULL)?(-1):(x->height))
#define MAX(a,b)  ((a>b)?(a):(b))
//獲取樹的新高度
#define GET_NEW_HEIGHT(x) (MAX(HEIGHT(x->LChild),HEIGHT(x->RChild)) + 1)

//前序打印
void show_pre(AVLTree* root)
{
	if(root==NULL)
		return;
	printf("data:%d\theight:%d\n",root->data,root->height);
	show_pre(root->LChild);
	show_pre(root->RChild);
}

//出現(xiàn)不平衡的情況
//左左不平衡
Node *LL_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->LChild;
	curRoot->LChild = newRoot->RChild;
	newRoot->RChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}

//右右不平衡
Node *RR_Rotation(Node *curRoot)
{
	Node *newRoot = curRoot->RChild;
	curRoot->RChild = newRoot->LChild;
	newRoot->LChild = curRoot;

	curRoot->height = GET_NEW_HEIGHT(curRoot);
	newRoot->height = GET_NEW_HEIGHT(newRoot);
	return newRoot;
}
//左右不平衡
Node *LR_Rotation(Node *curRoot)
{
	curRoot->LChild = RR_Rotation(curRoot->LChild);
	return LL_Rotation(curRoot);
}
//右左不平衡
Node *RL_Rotation(Node *curRoot)
{
	curRoot->RChild = LL_Rotation(curRoot->RChild);
	return RR_Rotation(curRoot);
}

//插入數(shù)據(jù)
Node *insertNode(Node *curRoot, Ty data)
{
	//插入分有四個(gè)大情況
	if (curRoot == NULL)			  //當(dāng)前節(jié)點(diǎn)是空的
		curRoot = creatAVLTree(data); //如果是空就直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)
	else if (data < curRoot->data)	  //要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)小
	{
		//往左邊跑
		curRoot->LChild = insertNode(curRoot->LChild, data);
		//插入完成之后，判斷需不需要調(diào)整樹
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			//因?yàn)椴迦氲奈恢迷谧筮?，所以插入完成之后，左子樹的高度大于等于右子樹高?
			curRoot = data < curRoot->LChild->data ? LL_Rotation(curRoot) : LR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大
	{
		//往右邊跑
		curRoot->RChild = insertNode(curRoot->RChild, data);
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			//因?yàn)椴迦氲奈恢迷谟疫?，所以插入完成之后，右子樹的高度大于等于左子樹高?
			curRoot = data > curRoot->RChild->data ? RR_Rotation(curRoot) : RL_Rotation(curRoot);
	}
	else //要插入的數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)一樣大
		printf("無法插入數(shù)據(jù)\n");
	//獲取新高度
	curRoot->height = GET_NEW_HEIGHT(curRoot);
	return curRoot; //插入完成之后返回當(dāng)前節(jié)點(diǎn)的指針
}

//查找節(jié)點(diǎn)
//找最大節(jié)點(diǎn)
Node *maxNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	//往右邊找
	while (curRoot->RChild)
		curRoot = curRoot->RChild;
	return curRoot;
}

//找最小節(jié)點(diǎn)
Node *minNode(Node *curRoot)
{
	if (curRoot == NULL)
		return NULL;
	while (curRoot->LChild)
		curRoot = curRoot->LChild;
	return curRoot;
}

//刪除數(shù)據(jù)
Node *deleteNode(Node *curRoot, Ty data)
{
	//刪除數(shù)據(jù)有四個(gè)大情況
	if (curRoot == NULL)	  //當(dāng)前節(jié)點(diǎn)是空的
		return NULL;		  //刪除了個(gè)寂寞直接結(jié)束掉整個(gè)函數(shù)
	if (data < curRoot->data) //要?jiǎng)h除的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)小
	{
		//往左邊跑
		curRoot->LChild = deleteNode(curRoot->LChild, data);
		//獲取新高度
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		//判斷需不需要調(diào)整
		if (HEIGHT(curRoot->RChild) - HEIGHT(curRoot->LChild) == 2)
			curRoot = HEIGHT(curRoot->RChild->LChild) > HEIGHT(curRoot->RChild->RChild) ? RL_Rotation(curRoot) : RR_Rotation(curRoot);
	}
	else if (data > curRoot->data) //要?jiǎng)h除的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大
	{
		//往右邊跑
		curRoot->RChild = deleteNode(curRoot->RChild, data);
		curRoot->height = GET_NEW_HEIGHT(curRoot);
		if (HEIGHT(curRoot->LChild) - HEIGHT(curRoot->RChild) == 2)
			curRoot = HEIGHT(curRoot->LChild->RChild) > HEIGHT(curRoot->LChild->LChild) ? LR_Rotation(curRoot) : LL_Rotation(curRoot);
	}
	else
	{ //要?jiǎng)h除的數(shù)據(jù)和當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)一樣大
		//針對于curRoot這個(gè)節(jié)點(diǎn)做刪除操作
		//主要有兩個(gè)主要的情況
		if (curRoot->LChild && curRoot->RChild) // curRoot有左子樹和右子樹
		{
			//先判斷左右子樹的高度，將高度比較高的子樹的節(jié)點(diǎn)拿到上面來
			if (HEIGHT(curRoot->LChild) > HEIGHT(curRoot->RChild))
			{ //左子樹的高度比右子樹的高度高
				//找到左子樹的最大節(jié)點(diǎn)
				Node *max = maxNode(curRoot->LChild);
				//找到之后就將max的數(shù)據(jù)替換curRoot的數(shù)據(jù)
				curRoot->data = max->data;
				//賦值完成之后繼續(xù)遞歸，然后釋放掉max對應(yīng)的節(jié)點(diǎn)，不能直接在這里釋放，因?yàn)橐{(diào)整樹的高度
				curRoot->LChild = deleteNode(curRoot->LChild, max->data);
			}
			else
			{ //左子樹的高度小于等于右子樹的高度
				//找到右子樹的最小節(jié)點(diǎn)
				Node *min = minNode(curRoot->RChild);
				curRoot->data = min->data;
				curRoot->RChild = deleteNode(curRoot->RChild, min->data);
			}
		}
		else //上一種情況的否定，即curRoot沒有子樹或者只有一邊
		{
			//釋放內(nèi)存
			Node *temp = curRoot;
			// curRoot拿到存在的子樹
			curRoot = curRoot->LChild ? curRoot->LChild : curRoot->RChild;
			free(temp);
		}
	}

	return curRoot; //刪除完成之后就返回當(dāng)前節(jié)點(diǎn)
}

int main()
{
	AVLTree *tree = NULL;
	for (int i = 1; i < 10; i++)
		tree = insertNode(tree, i);
	show_pre(tree); //前序打印樹
	printf("----------------------------\n");
	//刪除6這個(gè)節(jié)點(diǎn)
	tree = deleteNode(tree, 6);
	show_pre(tree);
	printf("程序結(jié)束\n");
	return 0;
}