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

typedef struct TreeNode
{
	int data;
	struct TreeNode* left;
	struct TreeNode* right;
	int hight;
}TreeNode;

TreeNode* create_node(int data)
{
	TreeNode* node = malloc(sizeof(TreeNode));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	node->hight = 1;
	return node;
}

int hight_tree(TreeNode* root)
{
	if(NULL == root)
		return 0;
	return root->hight;
}

void count_hight(TreeNode* root)
{
	if(NULL == root)
		return;
	int lh = hight_tree(root->left);
	int rh = hight_tree(root->right);
	root->hight = lh>rh ? lh+1 : rh+1;
}

void _add_tree(TreeNode** root,TreeNode* node)
{
	if(NULL == *root)
	{
		*root = node;
		return;
	}

	if(node->data < (*root)->data)
		_add_tree(&(*root)->left,node);
	else
		_add_tree(&(*root)->right,node);
	count_hight(*root);
}

void add_tree(TreeNode** root,int data)
{
	_add_tree(root,create_node(data));
}

void _ldr_show(TreeNode* root)
{
	if(NULL == root)
		return;
	_ldr_show(root->left);
	printf("%d ",root->data);
	_ldr_show(root->right);
}

void ldr_show(TreeNode* root)
{
	_ldr_show(root);
	printf("\n");
}


void right_rotate(TreeNode** root)
{
	TreeNode* A = *root;
	TreeNode* B = A->left;
	TreeNode* t2 = B->right;

	*root = B;
	B->right = A;
	A->left = t2;

	count_hight(A);
	count_hight(B);
}

void left_rotate(TreeNode** root)
{
	TreeNode* A = *root;
	TreeNode* B = A->right;
	TreeNode* t2 = B->left;

	*root = B;
	B->left = A;
	A->right = t2;
	count_hight(A);
	count_hight(B);
}

void avl_tree(TreeNode** root)
{
	if(NULL==*root || (NULL==(*root)->left && NULL==(*root)->right))
		return;

	avl_tree(&(*root)->left);
	avl_tree(&(*root)->right);

	int avl = hight_tree((*root)->left)-hight_tree((*root)->right);
	if(avl > 1)
	{
		if(0 < hight_tree((*root)->left->left) - hight_tree((*root)->left->right))
		{
			/*
				   A		以B为轴向右旋转		
				  / \
				 B  t1				 B
				/ \                /   \
			   C  t2              C     A
			  / \                / \   / \
			 t4 t3              t4 t3 t2 t1 
			*/
			right_rotate(root);
		}
		else
		{
			/*
			  A　						A
			 / \   以C为轴向左旋转　　 / \
			B   t1                    C  t1
		   / \                       / \
		  t2  C                     B  t4
		     / \                   / \
			t3 t4                 t2  t3
			*/
			left_rotate(&(*root)->left);
			right_rotate(root);
		}
		avl_tree(root);
	}
	else if(avl < -1)
	{
		if(0 > hight_tree((*root)->right->left) - hight_tree((*root)->right->right))
		{
			/*
			     A			以B为轴向左旋转
		    	/ \
			   t1  B					 B
			      / \				   /   \
			     t2  C                A     C 
                    / \              / \   / \
				   t3  t4           t1 t2 t3 t4
			*/
			left_rotate(root);
		}
		else
		{
			/*
				A							A
			   / \		以C为轴向右旋转    / \
			  t1  B                       t1  C
				 / \                         / \
				C   t2                     t3   B
			   / \                             / \
			  t3 t4                           t4 t2 
		    */
			right_rotate(&(*root)->right);
			left_rotate(root);
		}
		avl_tree(root);
	}
}

bool blance_tree(TreeNode* root)
{
	if(NULL == root)
		return true;
	int lh = hight_tree(root->left);
	int rh = hight_tree(root->right);
	return abs(lh-rh)<2 && blance_tree(root->left) && blance_tree(root->right);
}

int main(int argc,const char* argv[])
{
	TreeNode* root = NULL;
	for(int i=10; i>0; i--)
	{
		add_tree(&root,i);
	}
	ldr_show(root);
	printf("is blance %d\n",blance_tree(root));
	avl_tree(&root);
	printf("-----------------\n");
	printf("is blance %d\n",blance_tree(root));
	ldr_show(root);
}